遍歷多叉樹（遞歸、非遞歸廣度優(yōu)先、深度優(yōu)先）

wing324 發(fā)布于2019-08-22 10:57 / 1271人閱讀

簡(jiǎn)單的遍歷一個(gè)樹形結(jié)構(gòu)數(shù)據(jù)的幾種方法、非遞歸方法效率最好。

(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: []
                }
            ]
       }
    ];

    //遞歸實(shí)現(xiàn)
    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("------------- 遞歸實(shí)現(xiàn) ------------------");
    parseTreeJson(treeNodes);

    //非遞歸廣度優(yōu)先實(shí)現(xiàn)
    var iterator1 = function (treeNodes) {
        if (!treeNodes || !treeNodes.length) return;

        var stack = [];

        //先將第一層節(jié)點(diǎn)放入棧
        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);

            //如果該節(jié)點(diǎn)有子節(jié)點(diǎn)，繼續(xù)添加進(jìn)入棧底
            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("------------- 非遞歸廣度優(yōu)先實(shí)現(xiàn) ------------------");
    iterator1(treeNodes);

    //非遞歸深度優(yōu)先實(shí)現(xiàn)
    var iterator2 = function (treeNodes) {
        if (!treeNodes || !treeNodes.length) return;

        var stack = [];

        //先將第一層節(jié)點(diǎn)放入棧
        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);

            //如果該節(jié)點(diǎn)有子節(jié)點(diǎn)，繼續(xù)添加進(jìn)入棧頂
            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("------------- 非遞歸深度優(yōu)先實(shí)現(xiàn) ------------------");
    iterator2(treeNodes);
})(window);