跳至主要内容

Tree Traversal

如果你對於樹狀結構還不熟，推薦先了解 Tree。

Tree Traversal 指的是 「不重複地拜訪樹狀結構中所有節點」 的過程。

需要透過特定的順序，將樹裡面的每個節點都瀏覽過一遍（例如：列印節點、尋找特定值、或計算總和）。

主要分為兩大思維方向：

  1. 廣度優先搜尋（BFS, Breadth-First Search）：一層一層地看，把同一層的節點全部看完，再進入下一層。
  2. 深度優先搜尋（DFS, Depth-First Search）：沿著一條路徑一直往下鑽到最深處，碰到死胡同再折返回來走下一條。

Breadth First Search (BFS)​

從 Root 開始，由上到下、由左到右，一層一層地拜訪，有些人也會把這種搜尋方式稱為 Level-order Traversal。

適合用來尋找最短路徑，例如在社交網路中找出你和某個人的最短朋友關係鏈。

Tree
         10
      6     15
    3  8      20

BFS 遍歷結果 [10, 6, 15, 3, 8, 20]
class Node {
  constructor(val) {
    this.val = val;
	this.left = null;
	this.right = null;
  }
}

class Tree {
  constructor() {
  	this.root = null;
  }
  
  // 關注在 BFS，忽略其餘 method

  BFS() {
    if (!this.root) return [];

    let queue = [this.root]     // 儲存要造訪的 node
    const visited = []          // 儲放已經造訪過的 node 值

    while (queue.length > 0) {
      const next_queue = []     // 儲存下一層要造訪的 node
                                // 也可以只用一個單一 Queue 實作，不定義 next_queue
                                // 一邊從前面取出（shift）、一邊往後面塞入（push）。
      for (let node of queue) {
        visited.push(node.val);
        node.left && next_queue.push(node.left);
        node.right && next_queue.push(node.right);
      }
      queue = next_queue        // 指向下一層
    }
    return visited;
  }
}

Depth First Search (DFS)​

分為三種：

  • PreOrder
  • PostOrder
  • InOrder

以下用 recursion 實作，但也可以用 stack 實作。

PreOrder​

先處理當前節點，再遞迴走訪左子樹，最後遞迴走訪右子樹。

適合用來複製一棵樹，或是用來序列化（Serialize）樹狀結構，因為 Root 永遠在最前面。

         10
      6     15
    3  8      20

PreOrder 結果 [10, 6, 3, 8, 15, 20]
class Tree {
  constructor() {
  	this.root = null;
  }
  
  ...

  DFSPreOrder() {
    const visited = [];
    function helper(node) {
      visited.push(node.val);       // 造訪 Node 時就先把 value 存起來
      node.left && helper(node.left);
      node.right && helper(node.right);
    }
    this.root && helper(this.root);
    return visited;
  }
}

PostOrder​

先遞迴走訪左子樹，再遞迴走訪右子樹，最後才處理當前節點。

適合用來刪除整棵樹，或是計算資料夾的大小（必須先知道所有子資料夾的大小，才能加總出父資料夾的大小）。

         10
      6     15
    3  8      20

PostOrder 結果 [3, 8, 6, 20, 15, 10]
class Tree {
  constructor() {
  	this.root = null;
  }
  
  ...

  DFSPostOrder() {
    const visited = [];
    function helper(node) {
      node.left && helper(node.left);
      node.right && helper(node.right);
      visited.push(node.val);   // 造訪 Node 的最後才存 value
    }
    this.root && helper(this.root);
    return visited;
  }
}

InOrder​

先遞迴走訪左子樹，再處理當前節點，最後遞迴走訪右子樹。

在 Binary Search Tree 中，InOrder 的輸出結果一定會是由小到大排序好的陣列！

         10
      6     15
    3  8      20

InOrder 結果 [3, 6, 8, 10, 15, 20]
class Tree {
  constructor() {
  	this.root = null;
  }
  
  ...

  DFSInOrder() {
    const visited = [];
    function helper(node) {
      node.left && helper(node.left);
      visited.push(node.val);       // 造訪完 Left child 後再將 Node value 存起來
      node.right && helper(node.right);
    }
    this.root && helper(this.root);
    return visited;
  }
}

複雜度​

  • 時間複雜度：無論是 DFS 還是 BFS，所有的 Node 都剛好被拜訪一次，因此時間複雜度皆為 O(N)（N 為節點總數）。
  • 空間複雜度：
    • DFS
      • 取決於樹的高度（也就是 Recursion Call Stack 的深度）。
      • 最壞情況（樹長成一條直線）是 O(N)，最好情況（完全平衡樹）是 $O(log N)$。
    • BFS
      • 取決於樹中「最寬的那一層」有多少節點（Queue 裡面最多會裝那一層的所有節點）。
      • 在完全二元樹中，最底層約佔總節點的一半，因此最壞情況空間複雜度為 O(N)。
最後於 更新