Binary Tree —  Traversal

發表於 更新於 分類於
Traversal翻譯成中文就是遍歷的意思，如果要遍歷tree的每個節點的話，會有兩種方式，Breadth-First Tree Traversal和Depth-First Tree Traversal。

Traversal 翻譯成中文就是遍歷的意思，如果要遍歷 tree 的每個節點的話，會有兩種方式，Breadth-First Tree Traversal 和 Depth-First Tree Traversal。

Breadth-First Tree Traversal

Breadth-First Tree Traversal 也被稱作 Level Order Tree Traversal，利用廣度優先搜尋(Breadth-First Search，BFS)的方式來遍歷每個節點，概念非常容易理解，就是將每一層的節點由左至右依序取出。

甚麼是廣度優先搜尋?

從某個節點出發，接下來走訪相鄰節點，同一層的都走訪完了就往下一層

假設我們現在有顆 Binary Tree 如下圖

用廣度優先搜尋的方式走訪的步驟為:

  1. 第 1 層 取出 10
  2. 第 2 層 取出 8, 11
  3. 第 3 層 取出 5, 9 ,15
  4. 第 4 層 取出 2, 13, 19

最後取得陣列 [10, 8, 11, 5, 9, 15, 2, 13, 19]

用 js 實作 Breadth-First Tree Traversal:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bftt(node) {
    if (node === null) return;
    this.queue.push(node);
    for (let i = 0; i < this.queue.length; i++) {
        let currentNode = this.queue[i];
        if (currentNode === null) continue;
        if (currentNode.left !== null) {
            this.queue.push(currentNode.left);
        }
        if (currentNode.right !== null) {
            this.queue.push(currentNode.right);
        }
    }
}

tree.bftt(tree.root);

Depth-First Tree Traversal

採用的是深度優先搜尋(Depth-First-Search，DFS)的方式來遍歷節點，Depth-First Tree Traversal 又分為三種，這三種非常類似，但遍歷的順序不同。

  • preorder —  前序
  • inorder —  中序
  • postorder —  後序

深度優先搜尋

深度優先搜尋演算法（英語：Depth-First-Search，DFS）是一種用於遍歷或搜尋樹或圖的演算法。這個演算法會儘可能深的搜尋樹的分支。當節點 v 的所在邊都己被探尋過，搜尋將回溯到發現節點 v 的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重複以上過程，整個行程反覆進行直到所有節點都被存取為止。這種演算法不會根據圖的結構等資訊調整執行策略(引用自 wikipedia)

看完維基百科的解釋真的是似懂非懂，這邊我會想像是摸著牆在走迷宮，發現走到底了，就回頭找另一道牆繼續探索，只是靠牆的順序有所差異(先靠左或是先靠右)。

1. PreOrder(root, left, right)

順序: 根節點 → 左節點 → 右節點

實際用 PreOrder 走訪一次 Binary Tree 的話，順序如下圖

用 js 實作 PreOrder

1
2
3
4
5
6
7
8
9
preOrder(node) {
    if (node === null) return;
    this.queue.push(node.value);
    //用遞迴來遍歷節點
    this.preOrder(node.left);
    this.preOrder(node.right);
}

tree.preOrder(tree.root);

2.InOrder(left, root, right)

順序: 左節點 → 根節點 → 右節點

實際用 InOrder 的方式走訪一次二元樹的話順序如下圖

用 js 實作 InOrder

1
2
3
4
5
6
7
8
9
inOrder(node) {
    if (node === null) return;
    //用遞迴來遍歷節點
    this.inOrder(node.left);
    this.queue.push(node.value);
    this.inOrder(node.right);
}

tree.inOrder(tree.root);

3. PostOrder(left, right, root)

順序: 左節點 → 右節點 → 根節點

實際用 PostOrder 走訪一次 Binary Tree 的話順序如下圖

用 js 實作 PostOrder

1
2
3
4
5
6
7
8
9
postOrder(node) {
    if (node === null) return;
    //用遞迴來遍歷節點
    this.postOrder(node.left);
    this.postOrder(node.right);
    this.queue.push(node.value);
}

tree.postOrder(tree.root);

下面這張圖簡易的說明了 BFS 和 DFS 兩者的差異

如何在 Binary tree 中找到指定的值?

第一種方式使用遞迴，利用 Binary tree 的特性(當前節點的右子節點會比自己大 ，左子節點會比自己小)，如果目標值比當前節點還大的話就把當前節點的右節點作為參數傳入函式，反之就把左節點傳入，不斷呼叫自己，直到找到節點或是找不到就中止遞迴。

1
2
3
4
5
6
7
8
9
10
11
const searchRecursively = (node, target) => {
  if (node === null || target === node.value) return node;
  if (target < node.value) {
    return searchRecursively(node.left, target);
  }
  if (target > node.value) {
    return searchRecursively(node.right, target);
  }
};

searchRecursively(tree.root, 13);

執行結果如下，找得到就回傳該節點，若找不到就回傳 null

第二種方式用迴圈，假如目標值比當前節點還大的話，就把當前節點移動到右邊的子節點，反之則移動到左邊的節點，直到找到值或是找不到就跳出迴圈。

1
2
3
4
5
6
7
8
9
10
11
12
const searchIteratively = (node, target) => {
  while (node !== null && target !== node.value) {
    if (target < node.value) {
      node = node.left;
    } else {
      node = node.right;
    }
  }
  return node;
};

searchIteratively(tree.root, 8);

執行結果如下，找得到就回傳該節點，若找不到就回傳 null

Binary Tree — Traversal 完整的程式碼如下(包含 tree 的建立)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
    this.queue = [];
  }
  insertNode(value) {
    let current = new TreeNode(value);
    let target = null;
    let nowPos = this.root;
    while (nowPos !== null) {
      target = nowPos;
      if (current.value < nowPos.value) {
        nowPos = nowPos.left;
      } else {
        nowPos = nowPos.right;
      }
    }
    if (target === null) {
      this.root = current;
    } else if (current.value < target.value) {
      target.left = current;
    } else {
      target.right = current;
    }
  }
  bftt(node) {
    if (node === null) return;
    this.queue.push(node);
    for (let i = 0; i < this.queue.length; i++) {
      let currentNode = this.queue[i];
      if (currentNode === null) continue;
      if (currentNode.left !== null) {
        this.queue.push(currentNode.left);
      }
      if (currentNode.right !== null) {
        this.queue.push(currentNode.right);
      }
    }
  }
  preOrder(node) {
    if (node === null) return;
    this.queue.push(node.value);
    //用遞迴來遍歷節點
    this.preOrder(node.left);
    this.preOrder(node.right);
  }

  inOrder(node) {
    if (node === null) return;
    //用遞迴來遍歷節點
    this.inOrder(node.left);
    this.queue.push(node.value);
    this.inOrder(node.right);
  }

  postOrder(node) {
    if (node === null) return;
    //用遞迴來遍歷節點
    this.postOrder(node.left);
    this.postOrder(node.right);
    this.queue.push(node.value);
  }
}

let tree = new BinarySearchTree();
tree.insertNode(10);
tree.insertNode(8);
tree.insertNode(11);
tree.insertNode(5);
tree.insertNode(9);
tree.insertNode(15);
tree.insertNode(2);
tree.insertNode(19);
tree.insertNode(13);

console.log("BST", tree);

tree.bftt(tree.root);
tree.preOrder(tree.root);
tree.inOrder(tree.root);
tree.postOrder(tree.root);
console.log(tree.queue);

時間複雜度

👍 在最差的情況下，時間複雜度是 O(n)

👎 在最佳的情況下，時間複雜度是 O(1)

🤚 在平均情況下，時間複雜度為 O(log n)

不管是 Tree Traversal 或是在 tree 中尋找特定的值都是 leetcode 蠻常見的考題，只要可以掌握這些核心觀念，在解題的時候就會比較得心應手。

參考資料:Tree Traversals