JS數據結構描述之廣度遍歷和深度遍歷

printempw 發布于2019-08-20 15:35 / 1610人閱讀

摘要：一數據模型二遞歸實現遞歸實現三非遞歸廣度優先實現先將第一層節點放入棧如果該節點有子節點，繼續添加進入棧底非遞歸廣度優先實現四非遞歸深度優先實現先將第一層節點放入棧如果該節點有子節點，繼續添加進入棧頂非遞歸深度優先實現

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

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

一：數據模型:

(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云服務器云服務器廣度遍歷廣度優先遍歷 js 遍歷數據圖的深度遍歷

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

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

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

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

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

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

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

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

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

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

Betta 2019-08-26 10:09 評論0 收藏0
圖的JS實現

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

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