一文掌握JavaScript樹結構深度優先演算法

本篇文章為大家帶來了關於javascript的相關知識，主要介紹了JavaScript樹結構深度優先演算法，樹結構可以說是前端中最常見的資料結構之一，比如說DOM樹、級聯選擇、樹狀組件，下面一起來看一下，希望對大家有幫助。

【相關推薦：javascript影片教學、web前端】

什麼是樹

在現實生活中，相信每個人對樹都很熟悉，不管是柳樹、楊樹還是桃樹，可以說樹在我們生活中隨處可見；在電腦世界，樹是一種分層結構的抽像模型，

如下：

樹結構的應用有很多，就例如公司的組織架構，就可以用樹來表示​​，如下圖：

除了組織架構，像族譜、省市等都可以使用樹狀結構來表示。

樹的術語

樹有很多的術語，如下圖：

• 樹：n(n≥0)個節點所構成的有限集合，當n=0時，稱為空樹；
• 節點的度：節點的子樹數，例如B節點的度數就是2，A節點的度數就是3；
• ##樹的度數：樹的所有節點中最大的度數，例如上圖中，樹的度數是3；
• 葉子節點：度為0的節點，也叫葉節點;
• 子節點：如上圖；
• 兄弟節點：如上圖；
##根節點
• ：如上圖；
樹的深度
• ：樹中所有結點中的最大層次，例如上圖樹的深度就是3;
節點的層次
• ：例如E節點的層次就是3，節點的層次就是父節點層次1，根節點的層次為1；
路徑
• ：一個節點到另一個節點的通道，例如A→H的路徑就是A D H;##路徑長度
：
• 一個節點到另一個節點的距離，例如A→H的路徑就是3。 JavaScript中的樹

樹結構可以說是前端中最常見的資料結構之一，比如說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影片教學

、

web前端】

以上是一文掌握JavaScript樹結構深度優先演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！