JS數(shù)據(jù)結(jié)構(gòu)描述之廣度遍歷和深度遍歷

printempw 發(fā)布于2019-08-20 15:35 / 1619人閱讀

摘要：一數(shù)據(jù)模型二遞歸實現(xiàn)遞歸實現(xiàn)三非遞歸廣度優(yōu)先實現(xiàn)先將第一層節(jié)點放入棧如果該節(jié)點有子節(jié)點，繼續(xù)添加進入棧底非遞歸廣度優(yōu)先實現(xiàn)四非遞歸深度優(yōu)先實現(xiàn)先將第一層節(jié)點放入棧如果該節(jié)點有子節(jié)點，繼續(xù)添加進入棧頂非遞歸深度優(yōu)先實現(xiàn)

文章來源：http://www.html-js.com/articl...

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

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

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

三：非遞歸廣度優(yōu)先實現(xiàn)

var iterator1 = function (treeNodes) {
    if (!treeNodes || !treeNodes.length) return;

    var stack = [];

    //先將第一層節(jié)點放入棧
    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é)點有子節(jié)點，繼續(xù)添加進入棧底
        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)先實現(xiàn) ------------------");
iterator1(treeNodes);

四：非遞歸深度優(yōu)先實現(xiàn)

 var iterator2 = function (treeNodes) {
        if (!treeNodes || !treeNodes.length) return;

        var stack = [];

        //先將第一層節(jié)點放入棧
        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é)點有子節(jié)點，繼續(xù)添加進入棧頂
            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)先實現(xiàn) ------------------");
    iterator2(treeNodes);
})(window);

GPU云服務器云服務器廣度遍歷廣度優(yōu)先遍歷 js 遍歷數(shù)據(jù) 圖的深度遍歷

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/82360.html

JS算法之深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS)

摘要：算法之深度優(yōu)先遍歷和廣度優(yōu)先遍歷背景在開發(fā)頁面的時候，我們有時候會遇到這種需求在頁面某個節(jié)點中遍歷，找到目標節(jié)點，我們正常做法是利用選擇器，或者，但在本文，我們從算法的角度去查找節(jié)點，同時理解一下深度優(yōu)先遍歷和廣度優(yōu)先遍歷的原理。 JS算法之深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS) 背景在開發(fā)頁面的時候，我們有時候會遇到這種需求：在頁面某個dom節(jié)點中遍歷，找到目標dom節(jié)點，...

roadtogeek 2019-08-23 16:33 評論0 收藏0
js 中二叉樹的深度遍歷與廣度遍歷(遞歸實現(xiàn)與非遞歸實現(xiàn))

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

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

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

ghnor 2019-08-19 17:52 評論0 收藏0
實現(xiàn)深度遍歷和廣度遍歷(遞歸與非遞歸版本)

摘要：先畫個樹，然后解釋何為深度，何為廣度第一層子集第二層子集第二層子集第三層，子集第三層第四層圖就不畫太復雜了，最高四層的結(jié)構(gòu)，如果換成的形式的話可以理解成第一層第二層先畫個樹，然后解釋何為深度，何為廣度第一層子集 | ...

Betta 2019-08-26 10:09 評論0 收藏0
圖的JS實現(xiàn)

摘要：圖的實現(xiàn)如下采用鄰接表結(jié)構(gòu)實現(xiàn)。由于本次示例的是無向圖，因此每個頂點都互相增加為鄰接點。然而由于本次示例的圖為無向圖，會出現(xiàn)重復遍歷的情況，例如頂點的鄰接點有，的鄰接點有。圖的定義圖就是由若干個頂點和邊連接起來的一種結(jié)構(gòu)。很多東西都可以用圖來說明，例如人際關系，或者地圖。其中圖還分為有向圖和無向圖。如下就是有向圖圖的數(shù)據(jù)結(jié)構(gòu) 對于圖這種關系，可以通過兩種方式來存儲。領接表將...

LeanCloud 2019-08-21 17:00 評論0 收藏0