資訊專欄INFORMATION COLUMN
什么是樹
現(xiàn)實(shí)中樹隨處可見(jiàn)；在計(jì)算機(jī)世界，樹就是一種分層結(jié)構(gòu)的抽象模型。
如下圖所示：
樹結(jié)構(gòu)的可以用在很多情景，就如下圖公司的組織架構(gòu)，用“樹”就可以表達(dá)出來(lái)，如下圖：
組織架構(gòu)只是其中之一，比如族譜、省市等用樹的結(jié)構(gòu)形式展現(xiàn)是完全可以。
樹的術(shù)語(yǔ)
樹有很多的術(shù)語(yǔ)，如下圖：
樹：n(n≥0)個(gè)節(jié)點(diǎn)所構(gòu)成的有限集合，當(dāng)n=0時(shí)，稱為空樹；
節(jié)點(diǎn)的度：節(jié)點(diǎn)的子樹個(gè)數(shù)，例如B節(jié)點(diǎn)的度就是2，A節(jié)點(diǎn)的度就是3；
樹的度：樹的所有節(jié)點(diǎn)中最大的度數(shù)，例如上圖中，樹的度是3；
葉子節(jié)點(diǎn)：度為0的節(jié)點(diǎn)，也叫葉節(jié)點(diǎn)；
子節(jié)點(diǎn)：如上圖；
兄弟節(jié)點(diǎn)：如上圖；
根節(jié)點(diǎn)：如上圖；
樹的深度：樹中所有結(jié)點(diǎn)中的最大層次，例如上圖中樹的深度就是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)的通道，例如A→H的路徑就是A D H；
路徑長(zhǎng)度：一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的距離，例如A→H的路徑就是3。
JavaScript中的樹
樹結(jié)構(gòu)可以作為最常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)之一，還有很多其他的結(jié)構(gòu)如DOM樹、級(jí)聯(lián)選擇、樹形組件等等；
JavaScript沒(méi)有這樣的結(jié)構(gòu)，開(kāi)發(fā)我們的大腦，想到可以通過(guò)對(duì)象和數(shù)組來(lái)模擬一個(gè)樹，
例如下面這段代碼：
const tree = {
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)先
所謂的深度優(yōu)先遍歷算法，就是盡可能深的去搜索樹的分支，它的遍歷順序如下圖：
實(shí)現(xiàn)思路如下：
訪問(wèn)根節(jié)點(diǎn)；
對(duì)根節(jié)點(diǎn)的children持續(xù)進(jìn)行深度優(yōu)先遍歷（遞歸）；
實(shí)現(xiàn)代碼如下：
function dfs(root) {
console.log(root.value)
root.children && root.children.forEach(dfs) // 與下面一致
// if (root.children) {
// root.children.forEach(child => {
// dfs(child)
// })
// }
}
dfs(tree) // 這個(gè)tree就是前面定義的那個(gè)樹
/* 結(jié)果
A
B
E
F
C
G
D
H
I
*/上述展示我們想要的表示，思路沒(méi)什么問(wèn)題。
廣度優(yōu)先
所謂的廣度優(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)代碼如下：
function bfs(root) {
// 1. 新建隊(duì)列 跟節(jié)點(diǎn)入隊(duì)
const q = [root]
// 4 重復(fù)執(zhí)行
while (q.length > 0) {
const node = q.shift() // 2 隊(duì)頭出隊(duì)
console.log(node.value)
// 3 隊(duì)頭 children 依次入隊(duì)
node.children &&
node.children.forEach(child => {
q.push(child)
})
}
}
bfs(tree)
/* 結(jié)果
A
B
C
D
E
F
G
H
I
*/上述展示我們想要的表示，算法沒(méi)什么問(wèn)題。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/127785.html
摘要：通過(guò)深度優(yōu)先遍歷兩棵樹，每層節(jié)點(diǎn)進(jìn)行對(duì)比，記錄下每個(gè)節(jié)點(diǎn)的差異。所以可以對(duì)那棵樹也進(jìn)行深度優(yōu)先遍歷，遍歷的時(shí)候從步驟二生成的對(duì)象中找出當(dāng)前遍歷的節(jié)點(diǎn)差異，然后進(jìn)行操作。 實(shí)現(xiàn)虛擬(Virtual) Dom 把一個(gè)div元素的屬性打印出來(lái)，如下： showImg(https://segmentfault.com/img/bVbnPe1?w=1239&h=336); 可以看到僅僅是第一層，...
摘要：本文所實(shí)現(xiàn)的完整代碼存放在。這就是所謂的算法。兩個(gè)樹的完全的算法是一個(gè)時(shí)間復(fù)雜度為的問(wèn)題。如果有差異的話就記錄到一個(gè)對(duì)象里面。如和的不同，會(huì)被所替代。這牽涉到兩個(gè)列表的對(duì)比算法，需要另外起一個(gè)小節(jié)來(lái)討論。 作者：戴嘉華 轉(zhuǎn)載請(qǐng)注明出處并保留原文鏈接（ https://github.com/livoras/blog/issues/13 ）和作者信息。 目錄： 1 前言 2 對(duì)前端應(yīng)用狀...
摘要：存在好幾種方式來(lái)表示這種數(shù)據(jù)結(jié)構(gòu)。下面的示意圖展示了鄰接表數(shù)據(jù)結(jié)構(gòu)。在關(guān)聯(lián)矩陣中矩陣的行表示頂點(diǎn)列表示邊。廣度優(yōu)先搜索算法和深度優(yōu)先搜索算法基本上是相同的只有一點(diǎn)不同那就是待訪問(wèn)頂點(diǎn)列表的數(shù)據(jù)結(jié)構(gòu)。 1 樹 一個(gè)樹結(jié)構(gòu)包含一系列存在父子關(guān)系的節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)都有一個(gè)父節(jié)點(diǎn)(除了頂部的第一個(gè)節(jié)點(diǎn))以及零個(gè)或多個(gè)子節(jié)點(diǎn)。位于樹頂部的節(jié)點(diǎn)叫作根節(jié)點(diǎn)(11)。它沒(méi)有父節(jié)點(diǎn)。樹中的每個(gè)元素都叫作...
摘要：算法之深度優(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)，...
閱讀 566·2023-03-27 18:33
閱讀 755·2023-03-26 17:27
閱讀 656·2023-03-26 17:14
閱讀 608·2023-03-17 21:13
閱讀 541·2023-03-17 08:28
閱讀 1829·2023-02-27 22:32
閱讀 1324·2023-02-27 22:27
閱讀 2207·2023-01-20 08:28
