JavaScript樹結(jié)構(gòu)深度優(yōu)先算法實(shí)例分析

這篇文章主要介紹了JavaScript樹結(jié)構(gòu)深度優(yōu)先算法實(shí)例分析的相關(guān)知識(shí)，內(nèi)容詳細(xì)易懂，操作簡(jiǎn)單快捷，具有一定借鑒價(jià)值，相信大家閱讀完這篇JavaScript樹結(jié)構(gòu)深度優(yōu)先算法實(shí)例分析文章都會(huì)有所收獲，下面我們一起來(lái)看看吧。

什么是樹

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

如下圖所示：

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

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

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

JavaScript中并沒(méi)有提供樹這個(gè)數(shù)據(jù)結(jié)構(gòu)，但是我們可以通過(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
*/

可以看到，和圖中的順序是一致的，也就是說(shuō)我們的算法沒(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
*/

關(guān)于“JavaScript樹結(jié)構(gòu)深度優(yōu)先算法實(shí)例分析”這篇文章的內(nèi)容就介紹到這里，感謝各位的閱讀！相信大家對(duì)“JavaScript樹結(jié)構(gòu)深度優(yōu)先算法實(shí)例分析”知識(shí)都有一定的了解，大家如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。