---
tags: DSA in JavaScript
---
# Ch.23 Tree Traversal

樹狀結構若要使用陣列來顯示當前狀態有非常多種方法，但是基本上分為兩大類，會依照不同的使用情境斟酌使用。

- 廣度優先搜尋 (Breath-first Search)
- 深度優先搜尋 (Depth-first Search)

## 廣度優先搜尋

遍歷完一層的所有節點才會移動至下一層，會使用到 queue 結構，queue 可以使用陣列或串列實作，這邊先展示使用串列的 queue。

// 這個方法可以使用在每個二元樹，這邊是放在上一篇的二元搜尋樹裡面
breathFirstSearch () {
  // 1. 準備一個 result 陣列，儲存節點的值
  const result = []
  // 2. 準備 queue 來儲存之後要放進 result 的節點
  const q = new Queue()
  // 3. 先將 root 放進 queue 裡面
  q.enqueue(this.root)
  // 4. 持續以下操作直到 queue 裡面沒有任何節點
  while (q.size) {
    // 4-1. 排除 queue 裡面的節點，將該節點設為 curr
    const curr = q.dequeue()
    // 4-2. 將 curr 的值存入 result
    result.push(curr.value)
    // 4-3. 如果 curr 在樹中有左/右子節點，將該節點放入 queue 裡面
    if (curr.left) q.enqueue(curr.left)
    if (curr.right) q.enqueue(curr.right)
  }
  // 5. 回傳搜尋結果
  return result
}

## 深度優先搜尋

先將其中一個節點遍歷到最深處後，再遍歷下一個節點。
此處會使用遞迴方法，實作過程較為抽象，可能需要其他視覺化網站來輔助理解。
依據儲存值與呼叫遞迴函式的執行順序，又分為 preOrder、postOrder 與 inOrder 三種

- preOrder：存 → 左 → 右
- postOrder：左 → 右 → 存
- inOrder：左 → 存 → 右

// 此處使用 preOrder 作為示範，不同之處在於 traversing 函式內部程式碼的執行順序
depthFirstSearch () {
  const result = []
  const curr = this.root

  // 在方法內額外實作輔助函式
  function traversing (node) {
    result.push(node.value)                // 存：將該節點的值存進 result 內
    if (node.left) traversing(node.left)   // 左：遍歷左側子節點
    if (node.right) traversing(node.right) // 右：遍歷右側子節點
  }

  traversing(curr)
  return result
}

## 使用時機

- 若是使用於搜尋特定節點的話，深度優先搜尋比起廣度優先搜尋花費較少空間
- InOrder 方法常用於二元搜尋樹，因為送出的結果是已經排序完成的陣列
- PreOrder 方法常用於「輸出」所有樹狀結點，讓結構更容易複製或重建