JavaScript 中的樹型資料結構

語言: CN / TW / HK

實現和遍歷技術

本文已參與「掘力星計劃」,贏取創作大禮包,挑戰創作激勵金。

作者:Anish Kumar 譯者:同學小強 來源:stackfull

Tree 是一種有趣的資料結構,它在各個領域都有廣泛的應用,例如:

  • DOM 是一種樹型資料結構
  • 我們作業系統中的目錄和檔案可以表示為樹
  • 家族層次結構可以表示為一棵樹

樹有很多變體(如堆、 BST 等) ,可用於解決與排程、影象處理、資料庫等相關的問題。許多複雜的問題可能看起來和樹沒有關係,但是實際上可以表示為一個問題。我們還將討論這些問題(在本系列後面的部分中) ,看看樹是如何使看似複雜的問題更容易理解和解決的。

引言

為二叉樹實現一個節點是非常簡單的。

js function Node(value){ this.value = value this.left = null this.right = null } // usage const root = new Node(2) root.left = new Node(1) root.right = new Node(3)

因此,這幾行程式碼將為我們建立一個二叉樹,它看起來像這樣:

js 2 / \ / \ 1 3 / \ / \ null null null null

這很簡單。現在,我們如何使用這個呢?

遍歷

讓我們從試圖遍歷這些連線的樹節點(或整顆樹)開始。就像我們可以迭代一個數組一樣,如果我們也可以“迭代”樹節點就更好了。然而,樹並不是像陣列那樣的線性資料結構,因此遍歷這些資料結構的方法不止一種。我們可以將遍歷方法大致分為以下幾類:

  • 廣度優先遍歷
  • 深度優先遍歷

廣度優先搜尋/遍歷(BFS)

在這種方法中,我們逐層遍歷樹。我們將從根開始,然後覆蓋所有的子級,然後我們覆蓋所有的二級子級,以此類推。例如,對於上面的樹,遍歷會得到如下結果:

js 2, 1, 3

下面是一個略微複雜的樹的例子,使得這個更容易理解:

要實現這種形式的遍歷,我們可以使用一個佇列(先進先出)資料結構。下面是整個演算法的樣子:

  • 初始化一個包含 root 的佇列
  • 從佇列中刪除第一項
  • 將彈出項的左右子項推入佇列
  • 重複步驟2和3,直到佇列為空

下面是這個演算法實現後的樣子:

```js function walkBFS(root){ if(root === null) return

const queue = [root] while(queue.length){ const item = queue.shift() // do something console.log(item)

  if(item.left) queue.push(item.left)
  if(item.right) queue.push(item.right)

} } ```

我們可以稍微修改上面的演算法來返回一個二維陣列,其中每個內部陣列代表一個包含元素的層級:

```js function walkBFS(root){ if(root === null) return

const queue = [root], ans = []

while(queue.length){ const len = queue.length, level = [] for(let i = 0; i < len; i++){ const item = queue.shift() level.push(item) if(item.left) queue.push(item.left) if(item.right) queue.push(item.right) } ans.push(level) } return ans } ```

深度優先搜尋/遍歷(DFS)

在 DFS 中,我們取一個節點並繼續探索它的子節點,直到深度到達完全耗盡。這可以通過以下方法之一來實現:

js root node -> left node -> right node // pre-order traversal left node -> root node -> right node // in-order traversal left node -> right node -> root node // post-order traversal

所有這些遍歷技術都可以迭代和遞迴方式實現,讓我們進入實現細節:

前序遍歷

下面是一顆樹的前序遍歷的樣子:

js root node -> left node -> right node

訣竅: 我們可以使用這個簡單的技巧手動地找出任何樹的前序遍歷: 從根節點開始遍歷整個樹,保持自己在左邊。

實現: 讓我們深入研究這種遍歷的實際實現。 遞迴方法 相當直觀。

```js function walkPreOrder(root){ if(root === null) return

// do something here console.log(root.val)

// recurse through child nodes if(root.left) walkPreOrder(root.left) if(root.right) walkPreOrder(root.right) } ```

前序遍歷的迭代方法與 BFS 非常相似,不同之處在於我們使用堆疊而不是佇列,並且我們首先將右邊的子元素放入堆疊:

```js function walkPreOrder(root){ if(root === null) return

const stack = [root] while(stack.length){ const item = stack.pop()

  // do something
  console.log(item)

  // Left child is pushed after right one, since we want to print left child first hence it must be above right child in the stack
  if(item.right) stack.push(item.right)
  if(item.left) stack.push(item.left)

} } ```

中序遍歷

下面是一顆樹的中序遍歷的樣子:

js left node -> root node -> right node

訣竅: 我們可以使用這個簡單的技巧手動地找出任何樹的中序遍歷: 在樹的底部水平放置一個平面鏡像,並對所有節點進行投影。

實現:

遞迴:

```js function walkInOrder(root){ if(root === null) return

if(root.left) walkInOrder(root.left)

// do something here console.log(root.val)

if(root.right) walkInOrder(root.right) } ```

迭代: 這個演算法起初可能看起來有點神祕。但它相當直觀的。讓我們這樣來看: 在中序遍歷中,最左邊的子節點首先被列印,然後是根節點,然後是右節點。所以我們首先想到的是:

```js const curr = root

while(curr){ while(curr.left){ curr = curr.left // get to leftmost child }

console.log(curr) // print it

curr = curr.right // now move to right child } ```

在上述方法中,我們無法回溯,即返回到最左側節點的父節點,所以我們需要一個堆疊來記錄它們。因此,我們修訂後的方法可能看起來如下:

```js const stack = [] const curr = root

while(stack.length || curr){ while(curr){ stack.push(curr) // keep recording the trail, to backtrack curr = curr.left // get to leftmost child } const leftMost = stack.pop() console.log(leftMost) // print it

curr = leftMost.right // now move to right child } ```

現在我們可以使用上面的方法來制定最終的迭代演算法:

```js function walkInOrder(root){ if(root === null) return

const stack = [] let current = root

while(stack.length || current){ while(current){ stack.push(current) current = current.left } const last = stack.pop()

  // do something
  console.log(last)

  current = last.right

} } ```

後序遍歷

下面是一顆樹的後序遍歷的樣子:

js left node -> right node -> root node

訣竅:

對於任何樹的快速手動後序遍歷:一個接一個地提取所有最左邊的葉節點。

實現:

讓我們深入研究這種遍歷的實際實現。

遞迴:

```js function walkPostOrder(root){ if(root === null) return

if(root.left) walkPostOrder(root.left) if(root.right) walkPostOrder(root.right)

// do something here console.log(root.val)

} ```

迭代:我們已經有了用於前序遍歷的迭代演算法。 我們可以用那個嗎? 由於後序遍歷似乎只是前序遍歷的逆序。 讓我們來看看:

```js // PreOrder: root -> left -> right

// Reverse of PreOrder: right -> left -> root

// But PostOrder is: left -> right -> root ```

這裡有一個細微的區別。但是我們可以通過稍微修改前序演算法,然後對其進行逆序,從而得到後序結果。總體演算法如下:

```js // record result using root -> right -> left

// reverse result left -> right -> root ```

  • 使用與上面的迭代前序演算法類似的方法,使用臨時堆疊
  • 唯一的例外是我們使用 root-> right-> left 而不是 root-> left-> right

  • 將遍歷序列記錄在一個數組結果

  • 結果的逆序給出了後序遍歷

```js function walkPostOrder(root){ if(root === null) return []

const tempStack = [root], result = []

while(tempStack.length){ const last = tempStack.pop()

  result.push(last)

  if(last.left) tempStack.push(last.left)
  if(last.right) tempStack.push(last.right)
}

return result.reverse()

} ```

額外:JavaScript 提示

如果我們可以通過以下方式遍歷樹該多好:

js for(let node of walkPreOrder(tree) ){ console.log(node) }

看起來真的很好,而且很容易閱讀,不是嗎? 我們所要做的就是使用一個 walk 函式,它會返回一個迭代器。

以下是我們如何修改上面的 walkPreOrder 函式,使其按照上面共享的示例執行:

```js function* walkPreOrder(root){ if(root === null) return

const stack = [root] while(stack.length){ const item = stack.pop() yield item if(item.right) stack.push(item.right) if(item.left) stack.push(item.left) } } ```

推薦理由

本文(配有多圖)介紹了樹結構在 JavaScript 語言裡面如何遍歷,寫得淺顯易懂,解釋了廣度優先、深度優先等多種方法的實現,翻譯難免有出入,歡迎斧正!

原文:https://stackfull.dev/tree-data-structure-in-javascript

往期精彩

不用遞迴生成無限層級的樹

基於qiankun微前端實戰部署

歡迎在評論區討論,掘金官方將在掘力星計劃活動結束後,在評論區抽送100份掘金周邊,抽獎詳情見活動文章