學習目標

  • 理解二元樹的基本結構
  • 掌握三種深度優先走訪方法（前序、中序、後序）
  • 理解層序走訪（廣度優先）
  • 能夠根據走訪結果重建二元樹
  • 掌握走訪的遞迴和迭代實作

1. 二元樹的基本概念

1.1 什麼是二元樹？

二元樹 (Binary Tree) 是一種樹狀資料結構，其中每個節點最多有兩個子節點，分別稱為左子節點和右子節點。

1.2 二元樹的術語

  • 根節點 (Root): 樹的頂端節點
  • 葉節點 (Leaf): 沒有子節點的節點
  • 內部節點 (Internal Node): 有子節點的節點
  • 父節點 (Parent): 一個節點的上層節點
  • 子節點 (Child): 一個節點的下層節點
  • 兄弟節點 (Sibling): 有相同父節點的節點
  • 深度 (Depth): 從根節點到該節點的路徑長度
  • 高度 (Height): 從該節點到最遠葉節點的路徑長度

1.3 二元樹的範例

        1
       / \
      2   3
     / \   \
    4   5   6

在這個樹中： - 根節點: 1 - 葉節點: 4, 5, 6 - 節點 2 的左子節點: 4 - 節點 2 的右子節點: 5

2. 樹的走訪 (Tree Traversal)

2.1 什麼是走訪？

走訪 (Traversal) 是指按照某種順序訪問樹中的每個節點，且每個節點只訪問一次。

2.2 走訪的分類

  • 深度優先 (Depth-First): 先深入到底部，再回溯
  • 前序走訪 (Preorder)
  • 中序走訪 (Inorder)
  • 後序走訪 (Postorder)
  • 廣度優先 (Breadth-First): 一層一層地訪問
  • 層序走訪 (Level-order)

3. 深度優先走訪

3.1 前序走訪 (Preorder Traversal)

定義

順序: 根 → 左子樹 → 右子樹

遞迴演算法

Preorder(node):
    如果 node 為空，返回
    訪問 node
    Preorder(node.left)
    Preorder(node.right)

範例

對於以下樹：

        1
       / \
      2   3
     / \   \
    4   5   6

走訪過程: 1. 訪問根節點 1 2. 走訪左子樹（以 2 為根） - 訪問 2 - 走訪左子樹（以 4 為根） - 訪問 4 - （無左子樹） - （無右子樹） - 走訪右子樹（以 5 為根） - 訪問 5 - （無左子樹） - （無右子樹） 3. 走訪右子樹（以 3 為根） - 訪問 3 - （無左子樹） - 走訪右子樹（以 6 為根） - 訪問 6 - （無左子樹） - （無右子樹）

結果: 1, 2, 4, 5, 3, 6

C 語言實作

void preorder(struct Node* node) {
    if (node == NULL) return;

    printf("%d ", node->data);  // 訪問節點
    preorder(node->left);        // 走訪左子樹
    preorder(node->right);       // 走訪右子樹
}

3.2 中序走訪 (Inorder Traversal)

定義

順序: 左子樹 → 根 → 右子樹

遞迴演算法

Inorder(node):
    如果 node 為空，返回
    Inorder(node.left)
    訪問 node
    Inorder(node.right)

範例

對於同樣的樹：

        1
       / \
      2   3
     / \   \
    4   5   6

走訪過程: 1. 走訪左子樹（以 2 為根） - 走訪左子樹（以 4 為根） - （無左子樹） - 訪問 4 - （無右子樹） - 訪問 2 - 走訪右子樹（以 5 為根） - （無左子樹） - 訪問 5 - （無右子樹） 2. 訪問根節點 1 3. 走訪右子樹（以 3 為根） - （無左子樹） - 訪問 3 - 走訪右子樹（以 6 為根） - （無左子樹） - 訪問 6 - （無右子樹）

結果: 4, 2, 5, 1, 3, 6

C 語言實作

void inorder(struct Node* node) {
    if (node == NULL) return;

    inorder(node->left);         // 走訪左子樹
    printf("%d ", node->data);   // 訪問節點
    inorder(node->right);        // 走訪右子樹
}

重要特性

對於二元搜尋樹 (BST)，中序走訪的結果是遞增排序的序列。

3.3 後序走訪 (Postorder Traversal)

定義

順序: 左子樹 → 右子樹 → 根

遞迴演算法

Postorder(node):
    如果 node 為空，返回
    Postorder(node.left)
    Postorder(node.right)
    訪問 node

範例

對於同樣的樹：

        1
       / \
      2   3
     / \   \
    4   5   6

走訪過程: 1. 走訪左子樹（以 2 為根） - 走訪左子樹（以 4 為根） - （無左子樹） - （無右子樹） - 訪問 4 - 走訪右子樹（以 5 為根） - （無左子樹） - （無右子樹） - 訪問 5 - 訪問 2 2. 走訪右子樹（以 3 為根） - （無左子樹） - 走訪右子樹（以 6 為根） - （無左子樹） - （無右子樹） - 訪問 6 - 訪問 3 3. 訪問根節點 1

結果: 4, 5, 2, 6, 3, 1

C 語言實作

void postorder(struct Node* node) {
    if (node == NULL) return;

    postorder(node->left);        // 走訪左子樹
    postorder(node->right);       // 走訪右子樹
    printf("%d ", node->data);   // 訪問節點
}

重要應用

後序走訪常用於： - 刪除樹（先刪除子節點，再刪除父節點） - 計算表達式的值（後序表示法）

3.4 三種走訪的記憶方法

記憶口訣: - 前序: 根在前 → 根、左、右 - 中序: 根在中 → 左、根、右 - 後序: 根在後 → 左、右、根

4. 層序走訪 (Level-order Traversal)

4.1 定義

層序走訪（也稱為廣度優先走訪）是按照層級從上到下、從左到右訪問節點。

4.2 演算法

使用佇列 (Queue) 來實現：

LevelOrder(root):
    如果 root 為空，返回
    建立佇列 Q
    將 root 加入 Q
    當 Q 不為空：
        取出 Q 的頭部節點 node
        訪問 node
        如果 node.left 不為空，將 node.left 加入 Q
        如果 node.right 不為空，將 node.right 加入 Q

4.3 範例

對於同樣的樹：

        1
       / \
      2   3
     / \   \
    4   5   6

走訪過程: 1. 訪問層級 0: 1 2. 訪問層級 1: 2, 3 3. 訪問層級 2: 4, 5, 6

結果: 1, 2, 3, 4, 5, 6

4.4 C 語言實作

void levelOrder(struct Node* root) {
    if (root == NULL) return;

    struct Queue* q = createQueue();
    enqueue(q, root);

    while (!isEmpty(q)) {
        struct Node* node = dequeue(q);
        printf("%d ", node->data);

        if (node->left != NULL)
            enqueue(q, node->left);
        if (node->right != NULL)
            enqueue(q, node->right);
    }
}

5. 走訪結果比較

對於以下樹：

        1
       / \
      2   3
     / \   \
    4   5   6
走訪方式 結果
前序 1, 2, 4, 5, 3, 6
中序 4, 2, 5, 1, 3, 6
後序 4, 5, 2, 6, 3, 1
層序 1, 2, 3, 4, 5, 6

6. 根據走訪結果重建二元樹

6.1 前序 + 中序

已知: - 前序: 1, 2, 4, 5, 3, 6 - 中序: 4, 2, 5, 1, 3, 6

重建過程: 1. 前序的第一個元素是根節點: 1 2. 在中序中找到 1，左側是左子樹，右側是右子樹 - 左子樹中序: 4, 2, 5 - 右子樹中序: 3, 6 3. 根據左子樹長度，在前序中分割 - 左子樹前序: 2, 4, 5 - 右子樹前序: 3, 6 4. 遞迴重建左右子樹

6.2 後序 + 中序

已知: - 後序: 4, 5, 2, 6, 3, 1 - 中序: 4, 2, 5, 1, 3, 6

重建過程: 1. 後序的最後一個元素是根節點: 1 2. 在中序中找到 1，分割左右子樹 3. 遞迴重建

注意: 無法僅用前序和後序唯一確定一棵樹（除非是滿二元樹）。

7. 複雜度分析

7.1 時間複雜度

所有走訪方法的時間複雜度都是 O(n)，其中 n 是節點數量，因為每個節點只訪問一次。

7.2 空間複雜度

  • 遞迴實作: O(h)，其中 h 是樹的高度（遞迴呼叫堆疊）
  • 層序走訪（迭代）: O(w)，其中 w 是樹的最大寬度（佇列大小）

8. 實際應用

8.1 前序走訪

  • 複製樹
  • 計算目錄大小
  • 前序表示法（波蘭表示法）

8.2 中序走訪

  • 二元搜尋樹的排序輸出
  • 中序表示法（中綴表示法）

8.3 後序走訪

  • 刪除樹
  • 後序表示法（逆波蘭表示法）
  • 計算目錄大小

8.4 層序走訪

  • 列印樹的結構
  • 尋找特定層級的節點

9. 練習題

練習題 1

對於以下樹，寫出四種走訪的結果：

        A
       / \
      B   C
     /   / \
    D   E   F

解答：

  • 前序: A, B, D, C, E, F
  • 中序: D, B, A, E, C, F
  • 後序: D, B, E, F, C, A
  • 層序: A, B, C, D, E, F

練習題 2

已知前序走訪為 1, 2, 4, 3, 5，中序走訪為 4, 2, 1, 5, 3，請重建這棵樹。

解答：

  1. 根節點: 1（前序第一個）
  2. 在中序中找到 1: - 左子樹中序: 4, 2 - 右子樹中序: 5, 3
  3. 左子樹前序: 2, 4（長度 2） - 根: 2 - 左: 4
  4. 右子樹前序: 3, 5（長度 2） - 根: 3 - 左: 5

重建的樹:

        1
       / \
      2   3
     /   /
    4   5

練習題 3

為什麼中序走訪二元搜尋樹會得到排序結果？

解答： 因為二元搜尋樹的性質是：左子樹的所有節點值 < 根節點值 < 右子樹的所有節點值。中序走訪的順序是「左 → 根 → 右」，所以會先輸出所有小於根的值，然後是根，最後是所有大於根的值，結果就是遞增排序的。

10. 考試重點提醒

  1. 三種深度優先走訪: 要能清楚區分前序、中序、後序的順序
  2. 逐步過程: 要能詳細展示走訪的每一步
  3. 重建樹: 掌握用前序+中序或後序+中序重建樹的方法
  4. 實作: 理解遞迴和迭代的實作方式
  5. 應用: 了解不同走訪方式的實際應用場景