遍歷多叉樹（遞歸、非遞歸廣度優先、深度優先）

wing324 發布于2019-08-22 10:57 / 1274人閱讀

簡單的遍歷一個樹形結構數據的幾種方法、非遞歸方法效率最好。

(function (window, undefined) {
    var treeNodes = [
       {
            id: 1,
            name: "1",
            children: [
                 {
                      id: 11,
                      name: "11",
                      children: [
                           {
                                id: 111,
                                name: "111",
                                children:[]
                           },
                           {
                                id: 112,
                                name: "112"
                           }
                      ]
                 },
                 {
                      id: 12,
                      name: "12",
                      children: []
                 }
            ],
            users: []
       },
       {
            id: 2,
            name: "2",
            children: [
                {
                    id: 22,
                    name: "22",
                    children: []
                }
            ]
       }
    ];

    //遞歸實現
    var parseTreeJson = function(treeNodes){
       if (!treeNodes || !treeNodes.length) return;

       for (var i = 0, len = treeNodes.length; i < len; i++) {

            var childs = treeNodes[i].children;

            console.log(treeNodes[i].id);

            if(childs && childs.length > 0){
                 parseTreeJson(childs);
            }
       }
    };

    console.log("------------- 遞歸實現 ------------------");
    parseTreeJson(treeNodes);

    //非遞歸廣度優先實現
    var iterator1 = function (treeNodes) {
        if (!treeNodes || !treeNodes.length) return;

        var stack = [];

        //先將第一層節點放入棧
        for (var i = 0, len = treeNodes.length; i < len; i++) {
            stack.push(treeNodes[i]);
        }

        var item;

        while (stack.length) {
            item = stack.shift();

            console.log(item.id);

            //如果該節點有子節點，繼續添加進入棧底
            if (item.children && item.children.length) {
                //len = item.children.length;

                // for (i = 0; i < len; i++) {
                //  stack.push(item.children[i]);
                // }

                stack = stack.concat(item.children);
            }
        }
    };

    console.log("------------- 非遞歸廣度優先實現 ------------------");
    iterator1(treeNodes);

    //非遞歸深度優先實現
    var iterator2 = function (treeNodes) {
        if (!treeNodes || !treeNodes.length) return;

        var stack = [];

        //先將第一層節點放入棧
        for (var i = 0, len = treeNodes.length; i < len; i++) {
            stack.push(treeNodes[i]);
        }

        var item;

        while (stack.length) {
            item = stack.shift();

            console.log(item.id);

            //如果該節點有子節點，繼續添加進入棧頂
            if (item.children && item.children.length) {
                // len = item.children.length;

                // for (; len; len--) {
                //  stack.unshift(item.children[len - 1]);
                // }
                stack = item.children.concat(stack);
            }
        }
    };

    console.log("------------- 非遞歸深度優先實現 ------------------");
    iterator2(treeNodes);
})(window);

GPU云服務器云服務器非遞歸二叉樹遍歷廣度優先遍歷非遞歸遍歷廣度優先搜索

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/91521.html

面試題：給你個id，去拿到name，多叉樹遍歷

前天面試遇到一個多叉樹面試的題目，在這里分享記錄一下。題目：一個樹形的數據(如下數據)，面試官給你一個id，然后拿到對應的name? 數據結構大概是這個樣子 var cityData = [ { id: 1, name: 廣東省, children: [ { id: 11, ...

jayce 2019-08-22 16:18 評論0 收藏0
JS中的二叉樹遍歷

摘要：一個二叉樹的例子廣度優先遍歷廣度優先遍歷是從二叉樹的第一層根結點開始，自上至下逐層遍歷在同一層中，按照從左到右的順序對結點逐一訪問。有的書里將二叉樹的遍歷只講了上面三種遞歸遍歷。二叉樹是由根節點，左子樹，右子樹組成，左子樹和友子樹分別是一個二叉樹。這篇文章主要在JS中實現二叉樹的遍歷。一個二叉樹的例子 var tree = { value: 1, left: { ...

ghnor 2019-08-19 17:52 評論0 收藏0
js 中二叉樹的深度遍歷與廣度遍歷(遞歸實現與非遞歸實現)

摘要：樹中結點的最大層次稱為樹的深度或高度。二叉樹有深度遍歷和廣度遍歷，深度遍歷有前序中序和后序三種遍歷方法。二叉樹的前序遍歷可以用來顯示目錄結構等中序遍歷可以實現表達式樹，在編譯器底層很有用后序遍歷可以用來實現計算目錄內的文件及其信息等。樹的簡介棧、隊列、鏈表等數據結構，都是順序數據結構。而樹是非順序數據結構。樹型結構是一類非常重要的非線性結構。直觀地，樹型結構是以分支關系定義的層次結...

Yuanf 2019-08-23 11:38 評論0 收藏0
二叉樹遍歷

摘要：前言本篇文章是在二叉排序樹的基礎上進行遍歷查找與刪除結點。接下來我們根據構造的這顆二叉樹進行相應遍歷查找與刪除操作。遍歷二叉樹二叉樹的遍歷分為深度優先遍歷和廣度優先遍歷。中序遍歷二叉排序樹，得到的數組是有序的且是升序的。前言本篇文章是在二叉排序樹的基礎上進行遍歷、查找、與刪除結點。那么首先來看一下什么是二叉排序樹？二叉排序樹定義二叉排序樹，又稱二叉查找樹、二叉搜索樹。若...

aboutU 2019-08-26 13:54 評論0 收藏0