成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

實(shí)現(xiàn)深度遍歷和廣度遍歷(遞歸與非遞歸版本)

Betta / 3033人閱讀

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

先畫個(gè)樹(shù)，然后解釋 何為深度， 何為廣度

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

圖就不畫太復(fù)雜了，最高四層的結(jié)構(gòu)，如果換成html的形式的話可以理解成

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

    
    
 ------------第一層2

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

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

廣度比較符合正常人的思維，就像復(fù)習(xí)的時(shí)候，
1.先把整本書捋一遍，然后畫重點(diǎn)，
2.捋完之后看重點(diǎn)，重點(diǎn)內(nèi)容里面有一些具體時(shí)間，再整理出來(lái)，
3.最后重點(diǎn)背誦時(shí)間
廣度遍歷需要手動(dòng)去終結(jié)（判斷還有沒(méi)有整理內(nèi)容了）

根據(jù)js單線程的原理，深度很好實(shí)現(xiàn)，因?yàn)檠h(huán)遞歸默認(rèn)就是深度遍歷
把剛剛的圖 寫成一個(gè)數(shù)組

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

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

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

function checkN(nodeX) {
    var node_ = []; // 用來(lái)存儲(chǔ)子集
    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

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

應(yīng)一個(gè)大佬朋友，也是我高中同學(xué)的要求，寫了一個(gè)非遞歸版本

這個(gè)是深度優(yōu)先的.....

 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

這個(gè)是廣度優(yōu)先的

 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

這兩個(gè)代碼的相似度幾乎是百分之九十，唯一的區(qū)別就是先進(jìn)先出（廣度優(yōu)先），和先進(jìn)后出（深度優(yōu)先）

先進(jìn)先出的話，后來(lái)者就排到其后面，先進(jìn)后出，后來(lái)者就排到其前面
那么唯一的區(qū)別就是 processList = [...a.childrens, ...processList]; 還是 processList = [...processList,...a.childrens];

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

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

相關(guān)文章

  • js 中二叉樹(shù)的深度遍歷與廣度遍歷(遞歸實(shí)現(xiàn)與非遞歸實(shí)現(xiàn))

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

    Yuanf 評(píng)論0 收藏0

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

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

    roadtogeek 評(píng)論0 收藏0

  • 二叉樹(shù)遍歷

    摘要：前言本篇文章是在二叉排序樹(shù)的基礎(chǔ)上進(jìn)行遍歷查找與刪除結(jié)點(diǎn)。接下來(lái)我們根據(jù)構(gòu)造的這顆二叉樹(shù)進(jìn)行相應(yīng)遍歷查找與刪除操作。遍歷二叉樹(shù)二叉樹(shù)的遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷。中序遍歷二叉排序樹(shù)，得到的數(shù)組是有序的且是升序的。 前言 本篇文章是在二叉排序樹(shù)的基礎(chǔ)上進(jìn)行遍歷、查找、與刪除結(jié)點(diǎn)。 那么首先來(lái)看一下什么是二叉排序樹(shù)？ 二叉排序樹(shù) 定義 二叉排序樹(shù)，又稱二叉查找樹(shù)、二叉搜索樹(shù)。 若...

    aboutU 評(píng)論0 收藏0

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

    摘要：一數(shù)據(jù)模型二遞歸實(shí)現(xiàn)遞歸實(shí)現(xiàn)三非遞歸廣度優(yōu)先實(shí)現(xiàn)先將第一層節(jié)點(diǎn)放入棧如果該節(jié)點(diǎn)有子節(jié)點(diǎn)，繼續(xù)添加進(jìn)入棧底非遞歸廣度優(yōu)先實(shí)現(xiàn)四非遞歸深度優(yōu)先實(shí)現(xiàn)先將第一層節(jié)點(diǎn)放入棧如果該節(jié)點(diǎn)有子節(jié)點(diǎn)，繼續(xù)添加進(jìn)入棧頂非遞歸深度優(yōu)先實(shí)現(xiàn) 文章來(lái)源：http://www.html-js.com/articl... 簡(jiǎn)單的遍歷一個(gè)樹(shù)形結(jié)構(gòu)數(shù)據(jù)的幾種方法、非遞歸方法效率最好。 一：數(shù)據(jù)模型: (function...

    printempw 評(píng)論0 收藏0

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

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

    wing324 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<