實現深度遍歷和廣度遍歷(遞歸與非遞歸版本)

Betta 發布于2019-08-26 10:09 / 3000人閱讀

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

先畫個樹，然后解釋何為深度，何為廣度

                            第一層  子集
                                    |
                        __________________________
                        |                        |
                第二層1 子集             第二層2 子集       
                        |                        | 
                -----------------
                第三層11，子集       第三層12   
                         |
                    第四層111

圖就不畫太復雜了，最高四層的結構，如果換成html的形式的話可以理解成

------第一層
    ----------第二層1
         -----------第三層 11
             -----------第四層 111
        
        
        ---------------第三層 12
        
    
    
     ------------第一層2

深度遍歷，就是從第一層開始 -》 1 -》 11 -》111 -》 12 -》 2
這個意思就是，如果有下一級優先探索下一級的，沒有了話，再去探索兄弟層級（以此類推）
就是做一道菜，需要菜和調料，調料是需要調制的，比如調料需要雞汁和糖，雞汁又需要調制，那么正常流程就是，
1、開始做菜 -》開始調料 -》雞汁 -》調制雞汁的材料
2、等這些弄完了，再去加糖，完成調料步驟
3、糖加完了，再去切菜，完成做菜步驟
這個就是一個深度的過程

而廣度遍歷則相反，順序應該是 -> 1-> 2 -> 11 -> 12 -> 111
意思就是有兄弟層級優先解析兄弟層級，然后解析下一層級

廣度比較符合正常人的思維，就像復習的時候，
1.先把整本書捋一遍，然后畫重點，
2.捋完之后看重點，重點內容里面有一些具體時間，再整理出來，
3.最后重點背誦時間
廣度遍歷需要手動去終結（判斷還有沒有整理內容了）

根據js單線程的原理，深度很好實現，因為循環遞歸默認就是深度遍歷
把剛剛的圖寫成一個數組

const arr = [
     {
         name: "1",
         childrens: [
             {
                 name: "11",
                 childrens: [
                     {
                         name: "111"
                     }
                 ]
             },

             {
                 name: "12"
             }
         ]
     },

     {
         name: "2"
     }
]

我多加了一些換行，方便看清楚

深度遍歷

function check(nodeArr) {
    nodeArr.forEach(node => {
        console.log(node.name)
        if(node.childrens) {
            check(node.childrens)
        }
    })
}
check(arr) //
1
11
111
12
2

這段代碼很好理解，如果有子集，將子集和父集做同樣處理，或者說，作為一個新的參數給check這個方法。

廣度遍歷
廣度遍歷的話需要一個容器去記錄子集，等此層級的兄弟集處理完成，再去處理子集，子集的處理也以此類推
先上代碼

function checkN(nodeX) {
    var node_ = []; // 用來存儲子集
    nodeX.forEach(node => {
        console.log(node.name);
        if(node.childrens) {
            node_ = [...node_, ...node.childrens];
        }
    })
    if(node_[0])
        checkN(node_);
}
checkN(arr) //
1
2
11
12
111

具體內容就這些了，這兩個算法我剛剛自己想著寫的，不知道和一些比較正式的文章算法是不是略有出入，我也懶得去看了

應一個大佬朋友，也是我高中同學的要求，寫了一個非遞歸版本

這個是深度優先的.....

 function check_(nodeArr) {
     let processList = nodeArr;
     while(processList[0]) {
         const a = processList.shift();
         if(a.childrens) 
             processList = [...a.childrens, ...processList];
         console.log(a.name);        
     }
 }
 check_(arr);// 
1
11
111
12
2

這個是廣度優先的

 function checkX_(nodeArr) {
     let processList = nodeArr;
     while(processList[0]) {
         const a = processList.shift();
         if(a.childrens) {
             processList = [...processList,...a.childrens];
         }
             console.log(a.name);        
     }
 }

checkX_(arr);// 
1
2
11
12
111

這兩個代碼的相似度幾乎是百分之九十，唯一的區別就是先進先出（廣度優先），和先進后出（深度優先）

先進先出的話，后來者就排到其后面，先進后出，后來者就排到其前面
那么唯一的區別就是 processList = [...a.childrens, ...processList]; 還是 processList = [...processList,...a.childrens];

GPU云服務器云服務器非遞歸遍歷遞歸遍歷java java遞歸遍歷樹 php 遞歸遍歷樹

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

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

js 中二叉樹的深度遍歷與廣度遍歷(遞歸實現與非遞歸實現)

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

Yuanf 2019-08-23 11:38 評論0 收藏0
JS算法之深度優先遍歷(DFS)和廣度優先遍歷(BFS)

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

roadtogeek 2019-08-23 16:33 評論0 收藏0
二叉樹遍歷

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

aboutU 2019-08-26 13:54 評論0 收藏0
JS數據結構描述之廣度遍歷和深度遍歷

摘要：一數據模型二遞歸實現遞歸實現三非遞歸廣度優先實現先將第一層節點放入棧如果該節點有子節點，繼續添加進入棧底非遞歸廣度優先實現四非遞歸深度優先實現先將第一層節點放入棧如果該節點有子節點，繼續添加進入棧頂非遞歸深度優先實現文章來源：http://www.html-js.com/articl... 簡單的遍歷一個樹形結構數據的幾種方法、非遞歸方法效率最好。一：數據模型: (function...

printempw 2019-08-20 15:35 評論0 收藏0
遍歷多叉樹（遞歸、非遞歸廣度優先、深度優先）

簡單的遍歷一個樹形結構數據的幾種方法、非遞歸方法效率最好。 (function (window, undefined) { var treeNodes = [ { id: 1, name: 1, children: [ { i...

wing324 2019-08-22 10:57 評論0 收藏0