這篇文章主要介紹了JavaScript樹結構深度優先算法實例分析的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇JavaScript樹結構深度優先算法實例分析文章都會有所收獲，下面我們一起來看看吧。
在現實生活中，相信每個人對樹都很熟悉，不管是柳樹、楊樹還是桃樹，可以說樹在我們生活中隨處可見；在計算機世界，樹是一種分層結構的抽象模型，
如下圖所示：
樹結構的應用有很多，就比如公司的組織架構，就可以用樹來表示，如下圖：
除了組織架構，像族譜、省市等都可以使用樹結構來表示。
樹有很多的術語，如下圖：
樹：n(n≥0)個節點所構成的有限集合，當n=0時，稱為空樹；
節點的度：節點的子樹個數，例如B節點的度就是2，A節點的度就是3；
樹的度：樹的所有節點中最大的度數，例如上圖中，樹的度是3；
葉子節點：度為0的節點，也叫葉節點；
子節點：如上圖；
兄弟節點：如上圖；
根節點：如上圖；
樹的深度：樹中所有結點中的最大層次，例如上圖中樹的深度就是3；
節點的層次：例如E節點的層次就是3，節點的層次就是父節點層次+1，根節點的層次為1；
路徑：一個節點到另一個節點的通道，例如A→H的路徑就是A D H；
路徑長度：一個節點到另一個節點的距離，例如A→H的路徑就是3。
樹結構可以說是前端中最常見的數據結構之一，比如說DOM樹、級聯選擇、樹形組件等等；
JavaScript中并沒有提供樹這個數據結構，但是我們可以通過對象和數組來模擬一個樹，
例如下面這段代碼：
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 },
],
},
],
}所謂的深度優先遍歷算法，就是盡可能深的去搜索樹的分支，它的遍歷順序如下圖：
實現思路如下：
訪問根節點；
對根節點的children持續進行深度優先遍歷（遞歸）；
實現代碼如下：
function dfs(root) {
console.log(root.value)
root.children && root.children.forEach(dfs) // 與下面一致
// if (root.children) {
// root.children.forEach(child => {
// dfs(child)
// })
// }
}
dfs(tree) // 這個tree就是前面定義的那個樹
/* 結果
A
B
E
F
C
G
D
H
I
*/可以看到，和圖中的順序是一致的，也就是說我們的算法沒有問題。
所謂的廣度優先就是依次訪問離根節點近的節點，它的遍歷順序如下圖：
實現思路如下：
創建要給隊列，把根節點入隊；
把隊頭出隊并訪問；
把隊頭的children依次入隊；
重復執行2、3步，直到隊列為空。
實現代碼如下：
function bfs(root) {
// 1. 新建隊列 跟節點入隊
const q = [root]
// 4 重復執行
while (q.length > 0) {
const node = q.shift() // 2 隊頭出隊
console.log(node.value)
// 3 隊頭 children 依次入隊
node.children &&
node.children.forEach(child => {
q.push(child)
})
}
}
bfs(tree)
/* 結果
A
B
C
D
E
F
G
H
I
*/關于“JavaScript樹結構深度優先算法實例分析”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“JavaScript樹結構深度優先算法實例分析”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
