【考試向】資料結構筆記（樹及二元樹）

歡迎你點入本篇文章！我是 LukeTseng，本系列文章主要整理自學資料結構的一些知識，如果你喜歡我的文章，麻煩您不吝嗇的在文章底下按下一顆愛心，或是追蹤我唷～

簡介（Introduction）

image

Image Source：https://zh.wikipedia.org/zh-tw/%E6%A0%91_(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84)

樹（Tree）資料結構是一種非線性資料結構，用來模擬具有階層性（Hierarchical）關係的資料。

一棵樹的基本構成由以下兩個要素組成：

  1. 節點（Node）：樹的基本組成單位，每個節點會包含資料（或鍵值），以及指向其子節點的指標。
  2. 邊（Edge / Link）：連接兩節點的線條，代表節點之間的關係，一棵有 $N$ 個節點的樹，必定會有 $N-1$ 條邊。

節點關係的術語

  1. 根節點（Root）：樹的最頂層節點，整棵樹只有一個根節點，且是唯一沒有父節點的節點。
    • 如上圖中的節點 A 即根節點。
  2. 父節點（Parent）：若一個節點向下連接到其他節點，該節點就是那些節點的父節點。
    • 如上圖中的節點 A 為 B、C 這兩個節點的父節點。
  3. 子節點（Child）：由父節點向下連接延伸出的節點。
    • 如上圖中的節點 B、C 是節點 A 的子節點。
  4. 兄弟節點（Sibling）：擁有同一個父節點的節點們互稱兄弟節點。
    • 如上圖中的節點 B、C 擁有共同父節點 A，因此 B、C 兩節點是兄弟節點。
  5. 葉節點（Leaf / External Node）：沒有任何子節點的終端節點（terminal node）（即位於樹的最底層分支末端）。
    • 如上圖中的節點 K、O、P 都沒有子節點，因而稱為葉節點。
  6. 內部節點（Internal Node）：除了葉節點以外的節點，也就是至少擁有一個子節點的節點。
  7. 祖先（Ancestor）節點與子孫（Descendant）節點：從根節點往下走到某特定節點的路徑上，經過的所有節點都是該節點的「祖先」；反之，某節點向下延伸出的所有節點都是它的「子孫」。
  8. 子樹（Subtree）：樹中的任何一個節點，連同它所有的後代節點，可以被看作是一棵獨立的小樹，稱為子樹。
    • 如上圖中的節點 C、G、L、M、O、H、N、P 可稱為一個子樹。

測量與屬性的術語

  1. 分支度（Degree）：一個節點所擁有的子節點（或子樹）數量。而「整棵樹的分支度」是指該樹中所有節點分支度的最大值（例如二元樹的最大分支度為 2）。
    • 如上圖中的節點 A 的分支度為 2，因為它有兩個子節點。
  2. 深度（Depth）：從根節點走到某特定節點所需要經過的邊數。根節點的深度通常定義為 0。
    • 如上圖中的節點 C 的深度為 1，因為從根節點到 C 只要經過一個邊；而節點 E 的深度為 2。
  3. 高度（Height）：從某特定節點走到最遠的葉節點所經過的最長路徑邊數。葉節點的高度通常定義為 0，整棵樹的高度就是根節點的高度。
    • 如上圖中的節點 A 的高度為 4（葉節點的高度是 0，往上爬依序是 0, 1, 2, 3, 4），即為整棵樹的高度。
  4. 階度（Level）：代表節點所在的階層位置。通常將根節點定義為 Level 1（有些定義為 Level 0），它的子節點為 Level 2，以此類推。

樹林（Forest）

樹林（Forest）是由零棵或多棵互不相交（Disjoint）的樹所構成的集合。

若將一棵樹的根節點（Root）移除，且不改變其餘節點的連結關係，那其底下原本互相獨立的各個子樹（Subtrees），就會共同形成一個樹林。

反之，若建立一個新的單一節點，並將一個樹林中所有樹的根節點都連向這個新節點作為它的子節點，這個樹林就會變成一棵單一的樹。

樹的種類

  • 二元樹（Binary Tree）：每個節點最多只有兩個子節點（左子節點與右子節點），此為大多數複雜樹狀結構的基礎。
  • 二元搜尋樹（Binary Search Tree, BST）：一種具有順序性質的二元樹。規定左子樹所有節點的值必須「小於」父節點，右子樹所有節點的值必須「大於」父節點，適合用於實作動態集合或字典。
  • 平衡樹（Balanced Trees）：為了解決一般 BST 在極端情況下（如依序插入遞增數列）會退化成鏈結串列（導致搜尋變為 $O(n)$）的問題，常見的實作有 AVL Tree 和紅黑樹（Red-Black Tree），它們會透過旋轉機制自動保持樹的高度平衡。
  • 堆積（Heap）：一種特殊的完全二元樹，分為最大堆積（父節點恆大於子節點）和最小堆積。常用於實作優先佇列（Priority Queue）與堆積排序法（Heap Sort）。
  • B 樹與 B+ 樹（B-Tree / B+ Tree）：一種多路搜尋樹，節點可以擁有超過兩個以上的子節點。被廣泛應用在關聯式資料庫（Database Indexing）與檔案系統中，專為減少磁碟 I/O 讀取次數而設計。
  • 字典樹 / 前綴樹（Trie）：專門用來儲存與搜尋字串的樹狀結構。利用字串的共同前綴來節省空間，在搜尋引擎的自動完成（Auto-complete）或網路 IP 路由匹配中極為常見。

樹的資料結構表示法

以下是 $N$ 元樹的資料結構表示法：

image

Image Source：筆者繪製。

可用 C 語言撰寫成這樣：

1
2
3
4
5
6
7
8
9
#include <stdio.h>
#include <stdlib.h>

// 定義 N 元樹的節點結構
typedef struct TreeNode {
    int data;                 // 節點儲存的資料
    int childCount;           // 記錄該節點有幾個子節點 (link 的數量)
    struct TreeNode** links;  // 指標陣列 :用來儲存 link1, link2... linkn
} TreeNode;

樹在記憶體實作上的指標計算

以 C 語言實作樹狀結構時，每個節點通常會預先宣告固定數量的指標（有些書會稱之為 LINK），指向子節點。

此時會產生「實際使用的指標」與「浪費掉的空指標」的計算問題。

假設有棵分支度（Degree）為 $k$ 的 $k$ 元樹（k-ary tree），且樹中總共有 $N$ 個節點：

  • 總指標數：每個節點都有 $k$ 個指標欄位，整棵樹總共有 $N \cdot k$ 個指標。
  • 已使用的指標數：這些指標的作用是連接子節點，也就是樹的邊數，而每個節點均被一個指標所指向，所以已使用的指標數恆為 $N-1$。

最後求得空指標數（總指標數減去已使用的指標數）：

因此會有 $Nk - N + 1$ 個指標（LINK）被浪費掉。

練習

設有一棵樹分支度為 6，且有 50 個節點，則該棵樹需要多少個指標（或稱 LINK）欄位，而實際上用了多少個，浪費多少個指標？

  1. 計算總共需要多少個指標欄位： $N \cdot k = 6 \cdot 50 = 300$
  2. 計算浪費多少個指標： $N(k - 1) + 1 = 50(6 - 1) + 1 = 251$
  3. 計算實際上用了多少個：
    • $300 - 251 = 49$
    • 或是 $N - 1 = 50 - 1 = 49$ （因為無論樹的分支度是多少，只要是一棵連通的單一樹，有 $N$ 個節點就必定只有 $N-1$ 條邊）

二元樹（Binary Tree）

二元樹是一種非線性且階層式（hierarchical）的資料結構。

二元樹是由節點（Node）組成的有限集合，該集合可為空（Empty），或者是由一個根節點（Root）以及兩棵互不相交的、分別稱為左子樹（Left Subtree）與右子樹（Right Subtree）的二元樹所組成。

限制：二元樹中的每一個節點，最多只能擁有兩個子節點（即分支度 Degree $\le 2$）。

下圖是一棵二元樹，可見每個節點僅有兩個子節點。

image

Image Source：https://www.geeksforgeeks.org/dsa/introduction-to-binary-tree/

二元樹與一般樹的不同

比較項目二元樹（Binary Tree）一般樹
最大分支度嚴格限制最多為 2。沒有限制，可為 0 到無限大。
子樹的次序具有排序順序的關係，嚴格區分左子樹與右子樹。即使某節點只有一個子節點，也必須明確指出它是左子節點還是右子節點。不區分左右次序。如果只有一個子節點，它就是該節點唯一的子節點，沒有左右之分。
空樹的允許可為完全沒有任何節點的空集合。傳統定義上不能為空，至少必須包含一個節點（根節點）。

不同型態的二元樹

左斜樹（Left Skewed Tree）與右斜樹（Right Skewed Tree）

  • 左斜樹：樹中的每一個非葉節點，都只有左子節點。
  • 右斜樹：樹中的每一個非葉節點，都只有右子節點。
  • 特性：
    • 這兩種樹的形狀會完全退化成一條直線，本質上等同於單向鏈結串列（Singly Linked List）。
    • 出現這兩種樹會導致樹的高度等於節點總數 $N$，使得搜尋資料的時間複雜度從對數時間 $O(\log n)$ 劣化為線性時間 $O(n)$。

image

Image Source：https://www.geeksforgeeks.org/dsa/types-of-binary-tree/

滿枝二元樹（Fully Binary Tree）

定義：一棵深度（或階度 level）為 $k$ 的二元樹，如果擁有剛好 $2^k - 1$ 個節點，這棵樹就是滿枝二元樹（假設根節點深度為 $1$ 的時候成立）。

特性：除了葉節點（leaf node）外，所有的內部節點（internal node）皆擁有 2 個子節點，不允許只有一個子節點。

image

Image Source：https://www.geeksforgeeks.org/dsa/what-is-full-binary-tree/

完整二元樹（Complete Binary Tree）

定義：一棵有 $n$ 個節點、深度為 $k$ 的二元樹，如果將它從上到下、從左至右依次編號（從 $1$ 到 $n$），其每個節點的位置，都能夠與同深度的「滿枝二元樹」中編號 $1$ 到 $n$ 的節點位置完全對應。

意思就是除了最底層之外，上面所有層級都被完全填滿；而在最底層的節點，必須嚴格遵守從左側開始連續填滿，中間不能有空隙的規則。

要辨別完整二元樹就是看他倒數第二層以上是否都有全部被填滿，如下圖中倒數第二層 Level 2 以上到 Level 0，全部都有兩個子節點，而 Level 3 中的 J 沒有兄弟節點。

image

Image Source：https://www.geeksforgeeks.org/dsa/difference-between-full-and-complete-binary-tree/

應用：完整二元樹適合用一維陣列來儲存（完全不浪費陣列空間），為實作堆積（Heap）與優先佇列（Priority Queue）的基礎。

二元樹的數學性質

  1. 第 $i$ 階度（Level）的最大節點數：在二元樹的第 $i$ 層中，最多有 $2^{i-1}$ 個節點（假設根節點在第 1 層， $i \ge 1$）。
  2. 階度 $k$ 的最大節點數：一棵階度為 $k$ 的二元樹，最多有 $2^k - 1$ 個節點（假設根節點在第 1 層， $i \ge 1$）。
  3. 葉節點與分支度（Degree）為 $2$ 的節點關係：對於任何一棵非空的二元樹，如果其葉節點（分支度為 $0$）的數量為 $N_0$，且分支度為 $2$ 的節點數量為 $N_2$，則必然存在以下公式：
    • 葉節點的數量永遠比擁有兩個子節點的內部節點數量多出 1 個。

如下圖中階度 $3$ 的最大節點數為 $2^3 = 8$ 個節點（因為根節點階度是 $0$，不用 $- 1$），而全部最大節點數為 $2^4 - 1 = 15$ （$0 \sim 3$ 階度總共有四個階度）。

image

Image Source：https://www.geeksforgeeks.org/dsa/difference-between-full-and-complete-binary-tree/

完整二元樹的數學性質

完整二元樹最著名的特性，即父、子節點之間的關係可透過簡單的代數運算來定位，使遍歷與節點交換的時間複雜度極低。

若根節點儲存在陣列索引 $1$ 的位置（1-based indexing）：

對於陣列中的任意節點 $i$（$1 \leq i \leq n$）：

  • 父節點：
    • 若 $i = 1$ 則為根節點，無父節點。
    • 若 $i \ne 1$，則第 $i$ 個節點的父節點位於索引 $\lfloor \frac{i}{2} \rfloor$ （$\lfloor \frac{i}{2} \rfloor$ 表示 $< \frac{i}{2}$ 的最大正整數，即為 floor 函數）。
  • 左子節點：
    • 若 $2i \le n$ ，則節點 $i$ 的左子節點（left child）索引在 $2i$。
    • 若 $2i > n$，代表該節點為葉節點，無左子節點。
  • 右子節點：
    • 若 $2i + 1 \le n$ ，則節點 $i$ 的右子節點（right child）索引在 $2i + 1$ 。
    • 若 $2i + 1 > n$，代表無右子節點。

若根節點儲存在陣列索引 $0$ 的位置（0-based indexing）：

  • 父節點：$\lfloor \frac{i - 1}{2} \rfloor$。
  • 左子節點：$2i + 1$。
  • 右子節點：$2i + 2$。

以上的這些公式用在「由上到下」、「由左至右」的方式編號的完整二元樹，如下圖：

image

Image Source：https://interviewing.io/questions/count-complete-tree-nodes

一維陣列表示二元樹

假設有棵樹長這樣（A、B、C、D、E、F 為資料，而括號內為編號、索引）：

image

Image Source：筆者繪製。

該棵樹的最大節點數為 $2^3 - 1 = 7$ ，因此可將其表示成下列的一維陣列：

image

由於該棵樹是一棵完整二元樹（Complete Binary Tree），因此可用前面的公式來對該一維陣列做驗證：

  • 驗證 B 節點（$i=2$）：
    • 左子節點 $= 2 \times 2 = 4$（資料為 D）
    • 右子節點 $= 2 \times 2 + 1 = 5$（資料為 E）
  • 驗證 F 節點（$i=6$）：
    • 父節點 $= 6 / 2 = 3$（資料為 C）

優缺分析

使用一維陣列表示法的優缺點：

  • 優點：
    1. 節省空間（針對完整二元樹或滿枝二元樹）：不需要儲存左右子樹的指標（Pointer），在 64 位元系統中可節省大量記憶體。
    2. 存取快速：利用索引計算可以直接跳轉到目標節點，時間複雜度為 $O(1)$。
    3. 適合堆積（Heap）：該表示法是實作優先隊列（Priority Queue）或堆積排序（Heap Sort）的標準做法。
  • 缺點：
    1. 空間浪費（針對稀疏樹）：如果二元樹非常不平衡（例如右斜樹），中間會有大量空缺，陣列必須保留這些空間。
      • 例如：深度為 $k$ 的右斜樹只有 $k$ 個節點，但陣列需要 $2^k - 1$ 的空間。
      • 補充：完整二元樹也可能造成空間浪費，如上陣列圖就多出一個空間。
    2. 大小固定：陣列一旦宣告後較難動態擴張，若樹的深度增加，可能需要重新分配整個陣列。
    3. 插入與刪除節點效率低：新增或刪除節點時，可能需要大量搬移陣列中的資料來維持索引結構。

鏈結方式表示二元樹

鏈結（Linked）表示法是實作二元樹最常見且最具彈性的方式。

不同於一維陣列表示法在處理「非完整二元樹、滿枝二元樹」時容易造成大量的記憶體空間浪費，鏈結表示法採用動態記憶體配置，反映樹狀結構的階層與分支關係。

另外鏈結方式也解決一維陣列插入與刪除效率低的問題。

在鏈結表示法中，二元樹是由一個個獨立的節點（Node）所串聯而成，每個節點通常包含三個基本區塊：

  1. 資料欄位（data）：儲存該節點所要記錄的數值或資訊。
  2. 左子指標（Left Pointer, 下圖的 L_link）：指向該節點的左子節點位置，如果沒有左子節點，此指標會設為空值（C 的 NULL 或 C++ nullptr）。
  3. 右子指標（Right Pointer, 下圖的 R_link）：指向該節點的右子節點位置，同樣地，若無右子節點則設為空值。

整棵樹會由一個稱為根節點（Root）的指標作為起點，若這棵樹是空的，則 Root 指標本身就是空值。

image

Image Source：筆者繪製。

若寫成 C 語言，則會像下面這樣（不過通常都會寫成 llink 跟 rlink）：

1
2
3
4
5
struct TreeNode {
    int data;           // 儲存的資料
    TreeNode* L_Link;     // 指向左子樹的指標
    TreeNode* R_Link;    // 指向右子樹的指標
};

鏈結樹的圖形示意：

image

Image Source：https://afteracademy.com/article/what-is-a-tree-data-structure

優缺分析

使用鏈結表示法的優缺：

  • 優點：
    1. 動態記憶體：空間隨用隨取，只有在新增節點時才消耗記憶體，不像陣列需預先宣告一大塊連續空間而造成浪費。
    2. 插入刪除操作靈活：只需改變父節點與子節點之間的指標方向即可，不需像陣列大幅度搬移後續的資料。
  • 缺點：
    1. 額外的空間開銷：每個節點除了儲存資料本身，都必須額外花費記憶體空間來儲存兩個指標（左、右）。
    2. 無法隨機存取：不能像陣列一樣透過索引值（Index）在 $O(1)$ 的時間內直接找到特定節點，必須從根節點（Root）開始，循著指標一步一步往下遍歷尋找。

二元樹的追蹤（traversal）

二元樹的追蹤，或稱遍歷，有以下三種：

  1. 前序遍歷（Preorder Traversal）：先處理當前節點，再處理子節點。這種方式常用於複製整棵二元樹，或是輸出結構化的文件（如前綴表示法）。
    • 拜訪順序：根節點（Root） → 左子樹（Left Subtree） → 右子樹（Right Subtree）
  2. 中序遍歷（Inorder Traversal）：先處理左邊，再處理中間，最後處理右邊。對於二元搜尋樹（Binary Search Tree, BST）來說，中序遍歷的結果會是一個由小到大排序好的數列。
    • 拜訪順序：左子樹（Left Subtree） → 根節點（Root） → 右子樹（Right Subtree）
  3. 後序遍歷（Postorder Traversal）：先處理完所有子節點，最後才處理當前節點。這種方式常用於刪除整棵二元樹，因為必須要先清空左、右子節點的記憶體，最後才能安全釋放父節點。
    • 拜訪順序：左子樹（Left Subtree） → 右子樹（Right Subtree） → 根節點（Root）

繼續以下 C 語言實作前，要先定義二元樹結構：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <stdlib.h>

// 定義二元樹的節點結構
struct Node {
    int data;
    struct Node* llink;
    struct Node* rlink;
};

// 建立新節點的輔助函式
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->llink = NULL;
    newNode->rlink = NULL;
    return newNode;
}

C 語言實作：前序遍歷

1
2
3
4
5
6
7
8
9
10
11
void preorderTraversal(struct Node* node) {
    if (node == NULL) {
        return;
    }
    // 1. 先印出當前節點（根）
    printf("%d ", node->data);
    // 2. 遞迴拜訪左子樹
    preorderTraversal(node->llink);
    // 3. 遞迴拜訪右子樹
    preorderTraversal(node->rlink);
}

在主程式執行：

1
2
3
4
5
6
7
8
int main(){
    struct Node* n = createNode(10);
    struct Node* n1 = createNode(20);
    struct Node* n2 = createNode(30);
    n -> llink = n1;
    n -> rlink = n2;
    preorderTraversal(n);
}

Output：

1
10 20 30

C 語言實作：中序遍歷

1
2
3
4
5
6
7
8
9
10
11
void inorderTraversal(struct Node* node) {
    if (node == NULL) {
        return;
    }
    // 1. 遞迴拜訪左子樹
    inorderTraversal(node->llink);
    // 2. 印出當前節點（根）
    printf("%d ", node->data);
    // 3. 遞迴拜訪右子樹
    inorderTraversal(node->rlink);
}

執行結果：

1
20 10 30

C 語言實作：後序遍歷

1
2
3
4
5
6
7
8
9
10
11
void postorderTraversal(struct Node* node) {
    if (node == NULL) {
        return;
    }
    // 1. 遞迴拜訪左子樹
    postorderTraversal(node->llink);
    // 2. 遞迴拜訪右子樹
    postorderTraversal(node->rlink);
    // 3. 最後印出當前節點（根）
    printf("%d ", node->data);
}

執行結果：

1
20 30 10

三種遍歷方式比較表

遍歷名稱英文名稱執行順序常見應用
前序遍歷Preorder根 → 左 → 右複製二元樹、建立目錄結構
中序遍歷Inorder左 → 根 → 右二元搜尋樹（BST）排序輸出
後序遍歷Postorder左 → 右 → 根安全地釋放（刪除）二元樹的記憶體

以非遞迴形式實作的前、中、後序遍歷

所謂非遞迴形式就是用堆疊（Stack）的方式實現。

首先準備一個簡單的堆疊結構：

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
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

struct Node {
    int data;
    struct Node* llink;
    struct Node* rlink;
};

struct Stack {
    int top;
    struct Node* array[MAX_SIZE];
};

struct Stack* createStack() {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->top = -1;
    return stack;
}

void push(struct Stack* stack, struct Node* node) {
    stack->array[++stack->top] = node;
}

struct Node* pop(struct Stack* stack) {
    if (stack->top == -1) return NULL;
    return stack->array[stack->top--];
}

struct Node* peek(struct Stack* stack) {
    if (stack->top == -1) return NULL;
    return stack->array[stack->top];
}

int isEmpty(struct Stack* stack) {
    return stack->top == -1;
}

前序遍歷

前序遍歷的順序是中 -> 左 -> 右。

由於堆疊為後進先出（LIFO）的資料結構，所以當處理完中間節點後，必須先將右子節點推入堆疊，再推入左子節點，這樣下次取出的時候，才會先取出左子節點。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void preorderTraversal(struct Node* root) {
    if (root == NULL) return;

    struct Stack* stack = createStack();
    push(stack, root);

    while (!isEmpty(stack)) {
        // 取出堆疊頂部的節點並印出
        struct Node* node = pop(stack);
        printf("%d ", node->data);

        // 先推入右子樹（因為後進先出）
        if (node->right) {
            push(stack, node->right);
        }
        // 再推入左子樹
        if (node->left) {
            push(stack, node->left);
        }
    }
    free(stack);
}

執行以下主程式：

1
2
3
4
5
6
7
int main() {
    struct Node* root = createNode(10);
    root->left = createNode(20);
    root->right = createNode(30);

    preorderTraversal(root);
}

Output：

1
10 20 30

中序遍歷

中序遍歷的順序是左 -> 中 -> 右。

需要一個指標 curr 來持續往左走，沿途將經過的節點都推入堆疊，當走到盡頭（左子樹為空）時，從堆疊取出一個節點印出，接著轉向該節點的右子樹，重複同樣的過程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void inorderTraversal(struct Node* root) {
    struct Stack* stack = createStack();
    struct Node* curr = root;

    while (curr != NULL || !isEmpty(stack)) {
        // 不斷往左走，將沿途節點放入堆疊
        while (curr != NULL) {
            push(stack, curr);
            curr = curr->left;
        }

        // 走到最左邊後，取出節點並印出
        curr = pop(stack);
        printf("%d ", curr->data);

        // 轉向右子樹
        curr = curr->right;
    }
    free(stack);
}

執行結果：

1
20 10 30

後序遍歷

後序遍歷的順序是左 -> 右 -> 中。

後序遍歷在非遞迴處理上是最複雜的：當從左子樹返回中間節點時，還不能馬上印出中間節點，必須先去處理右子樹。

在此使用單一堆疊搭配一個 lastVisited 指標的方法：用以記錄上一個印出的節點。

若當前節點的右子樹為空，或者右子樹剛已被印出過（lastVisited == curr->right），就代表左右子樹都處理完了，可直接印出當前節點。

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
void postorderTraversal(struct Node* root) {
    struct Stack* stack = createStack();
    struct Node* curr = root;
    struct Node* lastVisited = NULL;

    while (curr != NULL || !isEmpty(stack)) {
        // 盡可能往左走
        if (curr != NULL) {
            push(stack, curr);
            curr = curr->left;
        } else {
            // 查看堆疊頂部節點，但不先取出
            struct Node* peekNode = peek(stack);

            // 如果有右子樹，且右子樹還沒被拜訪過，轉向右子樹
            if (peekNode->right != NULL && lastVisited != peekNode->right) {
                curr = peekNode->right;
            } else {
                // 如果沒有右子樹，或右子樹已經拜訪過了，就處理當前節點
                printf("%d ", peekNode->data);
                lastVisited = pop(stack); // 從堆疊取出並記錄為已拜訪
            }
        }
    }
    free(stack);
}

二元樹的性質

一般樹轉二元樹

將一般樹轉換為二元樹最標準且常用的方法稱為左子右兄弟（Left-Child Right-Sibling）表示法。

該方法可讓任何一棵一般樹（甚至是一座森林）轉換成一棵二元樹。

轉換上共有三個步驟：

  1. 兄弟相連：將所有同層級、同一個父節點的兄弟節點，從左至右用橫線連接起來。
  2. 保留長子、砍掉剩下的：對每個父節點，除了保留與第一個子節點（最左邊的子節點）的連線外，刪除與其他所有子節點的垂直連線。
  3. 順時針旋轉 45 度：將整棵樹向右（順時針）傾斜 45 度，重新整理層次，原本往下的垂直線變成二元樹的左子樹，原本橫向的兄弟連線變成二元樹的右子樹。

所謂順時針轉 45 度，就像下圖中那樣：

image

Image Source：筆者繪製。

那如果是橫的呢？請看下圖：

image

而所謂兄弟相連、保留長子就是像下面那樣：

image

B、C、D 互相都是兄弟節點，而長子就是最左邊的節點 B。

透過前、中、後序遍歷決定唯一的二元樹

如何透過走訪序列還原一棵唯一的二元樹？必須要有中序遍歷（In-order），再搭配前序遍歷（Pre-order）或後序遍歷（Post-order）其中之一。

如果只有前序和後序，是無法決定一棵唯一的二元樹的。

為何單一遍歷無法決定結構？

無論是前、中、後序，本質上都是將 2D 的樹狀結構降維壓扁成 1D 的線性陣列，在此過程中，父子節點的邊界資訊遺失了。

只知道節點遍歷的先後順序，卻不知道誰是誰的左子樹或右子樹。

定位與切割

要精準還原二元樹的結構，需要兩種不同的資訊交互配合：

  • 前序或後序，負責找根節點（Root）：
    • 前序（中 -> 左 -> 右）：序列的第一個元素，絕對是當前樹的根節點。
    • 後序（左 -> 右 -> 中）：序列的最後一個元素，絕對是當前樹的根節點。
  • 中序負責切割左右子樹：
    • 中序（左 -> 中 -> 右）：一旦透過前序或後序知道了「根節點」是誰，回到中序序列中找到該節點的位置，就可將序列切成兩半，即左邊的全是左子樹節點，右邊的全是右子樹節點。

前序 + 中序範例

假設題目提供兩組序列，求出完整唯一的二元樹：

  • 前序（Pre-order）：[A, B, D, E, C, F]
  • 中序（In-order）：[D, B, E, A, F, C]

第一輪（做確認與切割）：

  1. 看前序的第一個元素，確認根節點是 A。
  2. 拿著 A 去中序找，發現中序被切成兩半：[D, B, E]（左子樹）和 [F, C]（右子樹）。

第二輪（處理左子樹）：

  1. 回到前序，跳過 A 之後往後數 3 個節點 [B, D, E]，即左子樹的前序序列。
  2. 左子樹的前序是 [B, D, E]，第一個元素是 B，所以左子樹的根節點是 B。
  3. 拿 B 去中序的 [D, B, E] 找，切出：[D]（左子樹）和 [E]（右子樹）。

第三輪（處理右子樹）：

  1. 回到前序，跳過 A 之後找出 [C, F]，即右子樹的前序序列。
  2. 右子樹的前序是 [C, F]，第一個元素是 C，所以右子樹的根節點是 C。
  3. 拿 C 去中序的 [F, C] 找，切出：[F]（左子樹）。

最後求出二元樹：

image

後序 + 中序範例

假設題目給了兩組序列：

  • 後序（Post-order）：[D, E, B, F, C, A]
  • 中序（In-order）：[D, B, E, A, F, C]

第一輪（做確認與切割）：

  1. 看後序的最後一個元素，A 即為根節點。
  2. 拿 A 去中序找，將中序序列分兩半：[D, B, E]（左子樹）、[F, C]（右子樹）。

第二輪（處理左子樹）：

  1. 看左子樹後序 [D, E, B] 的最後一個元素是 B，所以 B 是這棵左子樹的根節點（A 的左子節點）。
  2. 拿著 B 去左子樹中序 [D, B, E] 中尋找，可切成 [D]（左子樹）、[E]（右子樹）。

第三輪（處理右子樹）：

  1. 看右子樹後序 [F, C] 的最後一個元素是 C，所以 C 是這棵右子樹的根節點（A 的右子節點）。
  2. 拿著 C 去右子樹中序 [F, C] 中尋找，可切成 [F]（左子樹）。

最後得出的結果與前序 + 中序的結果相同（此為範例刻意設計，後續遇到不同題目並不代表前序算出的結果跟後序一樣），一樣是這張圖：

image

引線二元樹（Thread Binary Tree）

引線二元樹（Thread Binary Tree）又稱線索二元樹，為傳統二元樹的一種改良結構。

概念是利用二元樹中原本空著的（Null）指標，來記錄節點在某種遍歷順序下的前行者（Predecessor）和後繼者（Successor）節點。

:::info

  1. 前行者 (Predecessor)
    • 定義：
      在某種遍歷順序下，緊接在當前節點「之前」被拜訪的那個節點。
      若把遍歷的結果攤平寫成一排直線的陣列，前行者即當前節點左邊的那一個元素。
    • 如何在樹的結構中找到中序前行者？
      假設找節點 $X$ 的中序前行者：
      • 情況 A（有左子樹）：如果 $X$ 有左子樹，則其前行者就是其左子樹中最右下角的節點，相當於在左子樹中尋找數值最大的節點。
      • 情況 B（沒有左子樹）：如果 $X$ 沒有左子樹，必須沿著父節點往上找，找到第一個「把它當作右子孫」的祖先節點，則祖先節點就是 $X$ 的前行者。
  2. 後繼者（Successor）
    • 定義：
      在某種遍歷順序下，緊接在當前節點「之後」被拜訪的那個節點。
      若把遍歷的結果攤平，後繼者就是當前節點右邊的那一個元素。
    • 如何在樹的結構中找到中序後繼者？
      假設我們要找節點 $X$ 的中序後繼者：
      • 情況 A（有右子樹）：如果 $X$ 有右子樹，則其後繼者就是其右子樹中最左下角的節點，相當於在右子樹中尋找數值最小的節點。
      • 情況 B（沒有右子樹）：如果 $X$ 沒有右子樹，必須沿著父節點往上找，找到第一個「把它當作左子孫」的祖先節點，則祖先節點就是 $X$ 的後繼者。
        :::

為什麼需要引線二元樹？

在一個有 $n$ 個節點的標準二元樹中，總共會有 $2n$ 個指標（每個節點有左、右兩個指標）。

但其中只有 $n-1$ 個指標真正指向了子節點（也就是只有 $n - 1$ 的指標被利用），剩下的 $n+1$ 個指標都是空的（Null）。

傳統上，如果要遍歷（例如中序遍歷）一棵二元樹，通常需要使用遞迴或堆疊來記錄回溯的路徑，會消耗額外的記憶體空間與時間。

引線二元樹就是為了解決該問題，將 $n+1$ 個浪費掉的空指標利用起來，將其變成引線（Threads），直接指向遍歷時的上一個或下一個節點，這樣一來，遍歷樹就不再需要遞迴或堆疊了。

引線（Thread）與標籤（Tag）

為區分一個指標到底是指向真正的子節點，還是指向前行者／後繼者節點的引線，需要在節點結構中加入兩個布林值標籤（Tags）：

  1. 左指標（Left Pointer）：
    • 若有左子節點，指向左子節點。
    • 若無左子節點，就將其變成左引線（Left Thread），指向遍歷順序中的前行者節點。
  2. 右指標（Right Pointer）：
    • 若有右子節點，指向右子節點。
    • 若無右子節點，就將其變成右引線（Right Thread），指向遍歷順序中的後繼者節點。
  3. 標籤（Left Tag & Right Tag）：
    • lTag = 1：左指標指向左子節點。
    • lTag = 0：左指標是引線，指向前行者節點。
    • rTag = 1：右指標指向右子節點。
    • rTag = 0：右指標是引線，指向後繼者節點。

在 C 中，這樣的資料結構可定義成：

1
2
3
4
5
6
7
8
9
// 使用 bool 請引入 <stdbool.h>

struct ThreadNode {
    int data;                 // 節點資料
    ThreadNode *llink;    // 左指標
    ThreadNode *rlink;   // 右指標
    bool lTag;                // 左標籤 (1: 子節點, 0: 引線)
    bool rTag;                // 右標籤 (1: 子節點, 0: 引線)
};

圖解：

image

Image Source：筆者繪製。

引線二元樹的長相

下圖實線代表一般正常的子節點指標（Link），虛線代表引線（Thread），也就是那些被重新利用的空指標。

image

Image Source：https://www.geeksforgeeks.org/dsa/threaded-binary-tree/

如何將二元樹轉引線二元樹

以最常見的中序引線二元樹為例。

不需改變原本樹的形狀或實體節點的鏈結，只需把那些原本指向空（Null）的指標，依照中序遍歷（左 -> 中 -> 右）的順序，重新指向它們的前行者或後繼者節點。

要做到二元樹轉引線二元樹，則要在遍歷整棵樹的過程中，必須隨時記住剛剛拜訪過的那一個節點。

有兩個變數：

  • Curr（現在的節點）
  • Prev（上一個節點）

現在開始做中序遍歷（初始化 Curr = 最左邊的節點, Prev = NULL）：

  1. 處理當前節點（Curr）的左引線
    • 若左指標為空，代表無實體的左子節點。
    • 此時把 Curr 的左指標指向 Prev。
    • 並把 Curr 的左標籤（lTag）標記為引線，看你定義 1 or 0 是引線就是哪一個。
  2. 處理上一個節點的右引線
    • 如果 Prev 的右指標為空，代表無實體的右子節點。
    • 因為現在位於 Curr，而 Curr 剛好就是 Prev 的下一步，所以，將 Prev 的右指標指向目前的 Curr。
    • 並把 Prev 的右標籤（rTag）標記為引線。
  3. 前進
    • 當 Curr 的左指標和 Prev 的右指標都檢查且牽好線之後，就讓 Prev 移動到 Curr 的位置（現在的節點即將變成下一次檢查時的上一個節點），然後繼續中序遍歷的下一步。
  4. 處理最後一個節點
    • 當整棵樹都遍歷完畢後，Prev 會停留在整棵樹中序遍歷的最後一個節點（整棵樹最右下角的節點）。
    • 該節點的右指標必定為空。
    • 因為是最後一個，沒有下一個節點可指向，所以其右指標會保持為空（Null），並將右標籤標記為引線。

範例

假設有棵樹長這樣：

image

Image Source：筆者繪製。

則其中序遍歷會是 1 -> 2 -> 3 -> 4 -> 6

設 Curr = 1，Prev = NULL，因為最左邊那個節點沒有前一個節點。

Curr（1）的左指標為空，因此把節點 1 的左引線指向 Prev（Null）。

接著再看 Prev 的右指標，而由於 Prev 現在是 NULL，所以啥事都不用幹，然後現在圖會變這樣：

image

前進走到節點 2（Curr = 2, Prev = 1）：

  • 檢查 Curr（2）的左指標：有指向實體的節點 1，非空，所以不管他。
  • 檢查 Prev（1）的右指標：為空，代表節點 1 需要一條後繼者引線，把節點 1 的右引線指向 Curr（2）。

image

接著前進走到節點 3（Curr = 3, Prev = 2）：

  • 檢查 Curr（3）的左指標：為空，將節點 3 的左引線指向 Prev（2）。
  • 檢查 Prev（2）的右指標：有指向實體的節點 3，非空，所以不管他。

image

然後走到節點 4（Curr = 4, Prev = 3）：

  • 檢查 Curr（4）的左指標：有指向實體節點 2，不管他。
  • 檢查 Prev（3）的右指標：為空，將節點 3 的右引線指向 Curr（4）。

image

最後走到節點 6（Curr = 6, Prev = 4）：

  • 檢查 Curr（6）的左指標：為空，將節點 6 的左引線牽向 Prev（4）。
  • 檢查 Prev（4）的右指標：有指向實體節點 6，不管他。

image

現在所有節點都走完了，做最後的收尾，Prev 停在最後一個節點 6，此時看他的右指標，會是空的，但他後面沒人了，所以將其右引線保持為 Null，並標記為引線。

image

C 語言實作：尋找中序後繼者（Successor）

資料結構定義：

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
#include <stdbool.h>

typedef struct ThreadNode {
    int data;                 // 節點資料
    struct ThreadNode *llink; // 左指標
    struct ThreadNode *rlink; // 右指標
    bool lTag;                // 左標籤 (1: 子節點, 0: 引線)
    bool rTag;                // 右標籤 (1: 子節點, 0: 引線)
} ThreadNode;

接著實作尋找中序後繼者，如同前面所說的，會有兩種情形：

  • 情況 A：若其右指標是引線（rTag == 0），則該條引線即指向後繼者的，直接回傳 rlink 即可。
  • 情況 B：若其右指標是右子樹（rTag == 1），則其後繼者，即右子樹裡面最左邊的節點。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ThreadNode* inorderSuccessor(ThreadNode *curr) {
    if (curr == NULL) return NULL;

    // 情況 A
    if (curr->rTag == 0) {
        return curr->rlink;
    }

    // 情況 B
    ThreadNode *temp = curr->rlink;
    while (temp != NULL && temp->lTag == 1) {
        temp = temp->llink;
    }
    
    return temp;
}

C 語言實作：尋找中序前行者（Predecessor）

  • 情況 A：若左指標是引線（lTag == 0），直接回傳 llink。
  • 情況 B：若左指標是左子樹（lTag == 1），則前行者即左子樹裡面最右邊的節點。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ThreadNode* inorderPredecessor(ThreadNode *curr) {
    if (curr == NULL) return NULL;

    // 情況 A
    if (curr->lTag == 0) {
        return curr->llink;
    }

    // 情況 B
    ThreadNode *temp = curr->llink;
    while (temp != NULL && temp->rTag == 1) {
        temp = temp->rlink;
    }
    
    return temp;
}

C 語言實作：引線二元樹的中序遍歷

有了尋找後繼者的函式後，遍歷整棵樹就會變得簡單，從此不再需要遞迴或堆疊，只要：

  1. 找出整棵樹的起點（由於中序遍歷，因此在整棵樹最左邊的節點）。
  2. 用 while 迴圈，不斷呼叫 inorderSuccessor 往後跳，直到指標變成 NULL 為止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void inorderTraversal(ThreadNode *root) {
    if (root == NULL) return;

    // 1
    ThreadNode *curr = root;
    while (curr->lTag == 1) { // 只要還有左子節點就一直往左走
        curr = curr->llink;
    }

    // 2
    while (curr != NULL) {
        printf("%d ", curr->data);          // 印出當前節點資料
        curr = inorderSuccessor(curr);      // 跳到下一個後繼節點
    }
    printf("\n");
}

C 語言程式實作：引線二元樹的插入操作（插入右方）

假設要將 newNode 插入到 curr 節點的右方，則插入的兩種情況：

  1. 情況一：curr 原本沒有右子樹（curr->rTag == 0）
    • 最簡單的狀況，newNode 直接變成 curr 的右子節點。
      • newNode 的左引線指回 curr（curr 為他的前行者）
      • newNode 的右引線會接上 curr 原本的右引線（指向 curr 原本的後繼者）。
  2. 情況二：curr 原本已經有右子樹（curr->rTag == 1）
    • 此時 newNode 會擠進 curr 和它原本的右子樹之間。
      • newNode 成為 curr 的新右子節點。
      • curr 原本的右子樹，變成 newNode 的右子樹。
      • 原本右子樹裡最左下角的節點，其左引線原本是指向 curr，現在中間多了 newNode，所以必須把那條左引線更新，改為指向 newNode。

程式實作：

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
void insert(ThreadNode *curr, ThreadNode *newNode) {
    if (curr == NULL || newNode == NULL) return;

    // 先處理 newNode 的右半邊
    newNode->rlink = curr->rlink;
    newNode->rTag = curr->rTag;
    
    // 處理 newNode 的左半邊
    newNode->llink = curr;
    newNode->lTag = 0;
    
    // 將 newNode 正式掛載為 curr 的右子節點
    curr->rlink = newNode;
    curr->rTag = 1;

    // 處理情況二
    if (newNode->rTag == 1) {
        // 尋找那棵右子樹中最左下角的節點
        ThreadNode *temp = newNode->rlink;
        while (temp->lTag == 1) {
            temp = temp->llink;
        }
        // 將該節點的左引線更新為指向新插入的 newNode
        temp->llink = newNode;
    }
}

優缺分析

以下是引線二元樹的優缺分析：

  • 優點：
    • 節省空間：不需額外的堆疊就能進行遍歷。
    • 提升遍歷效率：遍歷的過程變成了單純的指標跳躍，速度比傳統遞迴的二元樹更快。
    • 快速尋找鄰居：可非常快速找到任意節點在特定遍歷下的前行者或後繼者節點。
  • 缺點：
    • 插入與刪除複雜：每當樹的結構發生改變（新增或刪除節點）時，除了要修改子節點指標，還必須維護引線的正確性，邏輯較為繁瑣。
    • 節點變大：每個節點要多儲存兩個標籤（lTag, rTag），雖然布林值佔用空間不大，但依然增加了單一節點的大小。

總整理

樹（Tree）基本概念

樹是一種非線性、階層式的資料結構。

若有一棵 $N$ 個節點的連通樹，必定恰好有 $N-1$ 條邊。

重要術語：

  • 根節點（Root）：最頂層、唯一沒有父節點的節點。
  • 葉節點（Leaf／Terminal Node）：沒有任何子節點的末端節點。
  • 內部節點（Internal Node）：至少有一個子節點的節點。
  • 分支度（Degree）：節點擁有的子節點或子樹數量。整棵樹的分支度為最大節點分支度。
  • 深度（Depth）：從根節點往下走到目標節點的邊數（根為 0 或 1，依定義而定）。
  • 高度（Height）：從目標節點往上算到最遠葉節點的邊數（葉為 0）。
  • 樹林（Forest）：移除樹的根節點，底下的子樹集合即為樹林；反之，將多棵樹連上一個共同的根，就變成一棵樹。

考點：$k$ 元樹的空指標計算

  • 實作 $k$ 元樹時，每個節點配置 $k$ 個指標，若樹有 $N$ 個節點：
    • 總指標數：$N \cdot k$
    • 已使用指標（邊數）：$N - 1$
    • 浪費掉的空指標：$N(k - 1) + 1$

二元樹（Binary Tree）

二元樹的最大分支度嚴格限制為 2，並且嚴格區分左、右子樹（即使只有一個子節點也要分左右）。

二元樹允許為空集合。

  1. 特殊型態的二元樹
    1. 斜樹（Skewed Tree）：全偏向左或右，退化成鏈結串列，搜尋時間從對數退化為 $O(n)$。
    2. 滿枝二元樹（Full Binary Tree）：每一層都長滿。深度 $k$ 的樹必有 $2^k - 1$ 個節點。
    3. 完整二元樹（Complete Binary Tree）：除了最底層外全滿，且最底層嚴格由左至右連續填滿。適合用陣列實作（如 Heap）。
  2. 二元樹的數學性質
    • 第 $i$ 階度的最大節點數：$2^{i-1}$
    • 階度 $k$ 的整棵樹最大節點數：$2^k - 1$
    • 葉節點與度數 $2$ 節點的關係：（葉節點永遠比有兩個子節點的內部節點多 $1$ 個）
  3. 儲存表示法
表示法特性與優缺點節點索引關係（以 1-based index 為例）
一維陣列優點：適合完整／滿枝二元樹，存取快 $O(1)$。
缺點：若樹不平衡會嚴重浪費空間。		父節點：$\lfloor i/2 \rfloor$
左子節點：$2i$
右子節點：$2i+1$
鏈結表示法優點：最常用、動態配置記憶體，插入／刪除快。
缺點：需額外空間存指標，無法隨機存取。		節點包含：data, llink, rlink

二元樹的追蹤（Traversal）

將 2D 樹狀結構攤平成 1D 序列的過程，分為遞迴與非遞迴（需依賴堆疊 Stack）實作。

遍歷方式拜訪順序常見應用
前序（Preorder）中 → 左 → 右複製整棵樹、建立目錄結構
中序（Inorder）左 → 中 → 右BST 的排序輸出（由小到大）
後序（Postorder）左 → 右 → 中刪除整棵樹

樹的轉換與結構還原

  1. 一般樹 $\rightarrow$ 二元樹：左子右兄弟法
    • 利用 Left-Child Right-Sibling 技巧：
      1. 兄弟相連：同層兄弟水平連線。
      2. 保留長子：父節點只保留與最左側子節點的垂直連線。
      3. 順時針轉 45 度：原本垂直變左子樹，原本水平連線變右子樹。
  2. 透過遍歷序列還原唯一的二元樹
    • 必備條件：必須有中序，搭配前序或後序才能還原。
      • 前序 / 後序的作用：負責找出根節點（Root）。（前序的第一個，或後序的最後一個）。
      • 中序的作用：拿著找出的根節點，回到中序序列中，將其切割出左子樹與右子樹的範圍，反覆遞迴即可畫出整棵樹。

引線二元樹（Thread Binary Tree）

引線二元樹是為了解決傳統二元樹留下 $N+1$ 個空指標的浪費，並免除追蹤時對 Stack／遞迴的依賴。

  • 概念：將空的左／右指標，改為指向中序遍歷下的前行者（Predecessor）或後繼者（Successor）。
  • 標籤（Tag）：為區分是指向實體子樹還是引線（Thread），節點需加入 lTag 與 rTag（布林值）。
    • Tag = 1：指標連向實體子節點。
    • Tag = 0：指標作為引線，連向鄰居。

如何尋找中序鄰居？

  • 找後繼者（Successor）：
    • 若 rTag == 0：右指標就是後繼者。
    • 若 rTag == 1：右子樹中最左下角的節點。
  • 找前行者（Predecessor）：
    • 若 lTag == 0：左指標就是前行者。
    • 若 lTag == 1：左子樹中最右下角的節點。