一文掌握J(rèn)avaScript樹(shù)結(jié)構(gòu)深度優(yōu)先算法

第一文掌握J(rèn)avaScript樹(shù)結(jié)構(gòu)深度優(yōu)先算法在現(xiàn)實(shí)生活中，相信每個(gè)人對(duì)樹(shù)都很熟悉，不管是柳樹(shù)、楊樹(shù)還是桃樹(shù)，可以說(shuō)樹(shù)在我們生活中隨處可見(jiàn)；在計(jì)算機(jī)世界，樹(shù)是一種分層結(jié)構(gòu)的抽象模型，

如下圖所示：

樹(shù)結(jié)構(gòu)的應(yīng)用有很多，就比如公司的組織架構(gòu)，就可以用樹(shù)來(lái)表示，如下圖：

除了組織架構(gòu)，像族譜、省市等都可以使用樹(shù)結(jié)構(gòu)來(lái)表示。

樹(shù)有很多的術(shù)語(yǔ)，如下圖：

樹(shù)：n(n0)個(gè)節(jié)點(diǎn)所構(gòu)成的有限集合，當(dāng)n=0時(shí)，稱(chēng)為空樹(shù)；

節(jié)點(diǎn)的度：節(jié)點(diǎn)的子樹(shù)個(gè)數(shù)，例如B節(jié)點(diǎn)的度就是2，A節(jié)點(diǎn)的度就是3；

樹(shù)的度：樹(shù)的所有節(jié)點(diǎn)中最大的度數(shù)，例如上圖中，樹(shù)的度是3；

葉子節(jié)點(diǎn)：度為0的節(jié)點(diǎn)，也叫葉節(jié)點(diǎn)；

子節(jié)點(diǎn)：如上圖；

兄弟節(jié)點(diǎn)：如上圖；

根節(jié)點(diǎn)：如上圖；

樹(shù)的深度：樹(shù)中所有結(jié)點(diǎn)中的最大層次，例如上圖中樹(shù)的深度就是3；

節(jié)點(diǎn)的層次：例如E節(jié)點(diǎn)的層次就是3，節(jié)點(diǎn)的層次就是父節(jié)點(diǎn)層次+1，根節(jié)點(diǎn)的層次為1；

路徑：一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的通道，例如AH的路徑就是ADH；

路徑長(zhǎng)度：一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的距離，例如AH的路徑就是3。

JavaScript中的樹(shù)

樹(shù)結(jié)構(gòu)可以說(shuō)是前端中最常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)之一，比如說(shuō)DOM樹(shù)、級(jí)聯(lián)選擇、樹(shù)形組件等等；

JavaScript中并沒(méi)有提供樹(shù)這個(gè)數(shù)據(jù)結(jié)構(gòu)，但是我們可以通過(guò)對(duì)象和數(shù)組來(lái)模擬一個(gè)樹(shù)，

例如下面這段代碼：

consttree={

value:A,

children:[

value:B,

children:[

{value:E,children:null},

{value:F,children:null},

value:C,

children:[{value:G,children:null}],

value:D,

children:[

{value:H,children:null},

{value:I,children:null},

}

廣度優(yōu)先和深度優(yōu)點(diǎn)遍歷算法

所謂的深度優(yōu)先遍歷算法，就是盡可能深的去搜索樹(shù)的分支，它的遍歷順序如下圖：

實(shí)現(xiàn)思路如下：

訪問(wèn)根節(jié)點(diǎn)；

對(duì)根節(jié)點(diǎn)的children持續(xù)進(jìn)行深度優(yōu)先遍歷（遞歸）；

實(shí)現(xiàn)代碼如下：

functiondfs(root){

console.log(root.value)

root.childrenroot.children.forEach(dfs)//與下面一致

//if(root.children){

//root.children.forEach(child={

//dfs(child)

//})

//}

dfs(tree)//這個(gè)tree就是前面定義的那個(gè)樹(shù)

/*結(jié)果

*/

可以看到，和圖中的順序是一致的，也就是說(shuō)我們的算法沒(méi)有問(wèn)題。

所謂的廣度優(yōu)先就是依次訪問(wèn)離根節(jié)點(diǎn)近的節(jié)點(diǎn)，它的遍歷順序如下圖：

實(shí)現(xiàn)思路如下：

創(chuàng)建要給隊(duì)列，把根節(jié)點(diǎn)入隊(duì)；

把隊(duì)頭出隊(duì)并訪問(wèn)；

把隊(duì)頭的children依次入隊(duì)；

重復(fù)執(zhí)行2、3步，直到隊(duì)列為空。

實(shí)現(xiàn)代碼如下：

functionbfs(root){

//1.新建隊(duì)列跟節(jié)點(diǎn)入隊(duì)

constq=[root]

//4重復(fù)執(zhí)行

while(q.length0){

constnode=q.shift()//2隊(duì)頭出隊(duì)

console.log(node.value)

//3隊(duì)頭children依次入隊(duì)

node.children

node.children