# 【考試向】資料結構筆記（樹及二元樹）
[TOC]
歡迎你點入本篇文章！我是 LukeTseng，本系列文章主要整理自學資料結構的一些知識，如果你喜歡我的文章，麻煩您不吝嗇的在文章底下按下一顆愛心，或是追蹤我唷～
## 簡介（Introduction）
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 Source：筆者繪製。
可用 C 語言撰寫成這樣：
```c=
#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$。
最後求得空指標數（總指標數減去已使用的指標數）：$$(N \cdot k) - (N - 1) = N(k - 1) + 1 = Nk - 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 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 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 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 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$，則必然存在以下公式：$$N_0 = N_2 + 1$$
- 葉節點的數量永遠比擁有兩個子節點的內部節點數量多出 1 個。
如下圖中階度 $3$ 的最大節點數為 $2^3 = 8$ 個節點（因為根節點階度是 $0$，不用 $- 1$），而全部最大節點數為 $2^4 - 1 = 15$ （$0 \sim 3$ 階度總共有四個階度）。
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 Source：https://interviewing.io/questions/count-complete-tree-nodes
### 一維陣列表示二元樹
假設有棵樹長這樣（A、B、C、D、E、F 為資料，而括號內為編號、索引）：
Image Source：筆者繪製。
該棵樹的最大節點數為 $2^3 - 1 = 7$ ，因此可將其表示成下列的一維陣列：
由於該棵樹是一棵完整二元樹（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 Source：筆者繪製。
若寫成 C 語言，則會像下面這樣（不過通常都會寫成 `llink` 跟 `rlink`）：
```c=
struct TreeNode {
int data; // 儲存的資料
TreeNode* L_Link; // 指向左子樹的指標
TreeNode* R_Link; // 指向右子樹的指標
};
```
鏈結樹的圖形示意：
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 語言實作前，要先定義二元樹結構：
```c=
#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 語言實作：前序遍歷
```c=
void preorderTraversal(struct Node* node) {
if (node == NULL) {
return;
}
// 1. 先印出當前節點（根）
printf("%d ", node->data);
// 2. 遞迴拜訪左子樹
preorderTraversal(node->llink);
// 3. 遞迴拜訪右子樹
preorderTraversal(node->rlink);
}
```
在主程式執行：
```c=
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：
```
10 20 30
```
### C 語言實作：中序遍歷
```c=
void inorderTraversal(struct Node* node) {
if (node == NULL) {
return;
}
// 1. 遞迴拜訪左子樹
inorderTraversal(node->llink);
// 2. 印出當前節點（根）
printf("%d ", node->data);
// 3. 遞迴拜訪右子樹
inorderTraversal(node->rlink);
}
```
執行結果：
```
20 10 30
```
### C 語言實作：後序遍歷
```c=
void postorderTraversal(struct Node* node) {
if (node == NULL) {
return;
}
// 1. 遞迴拜訪左子樹
postorderTraversal(node->llink);
// 2. 遞迴拜訪右子樹
postorderTraversal(node->rlink);
// 3. 最後印出當前節點（根）
printf("%d ", node->data);
}
```
執行結果：
```
20 30 10
```
### 三種遍歷方式比較表
| 遍歷名稱 | 英文名稱 | 執行順序 | 常見應用 |
|------|-----------|-------------|------------------|
| 前序遍歷 | Preorder | 根 → 左 → 右 | 複製二元樹、建立目錄結構 |
| 中序遍歷 | Inorder | 左 → 根 → 右 | 二元搜尋樹（BST）排序輸出 |
| 後序遍歷 | Postorder | 左 → 右 → 根 | 安全地釋放（刪除）二元樹的記憶體 |
### 以非遞迴形式實作的前、中、後序遍歷
所謂非遞迴形式就是用堆疊（Stack）的方式實現。
首先準備一個簡單的堆疊結構：
```c=
#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）的資料結構，所以當處理完中間節點後，必須先將右子節點推入堆疊，再推入左子節點，這樣下次取出的時候，才會先取出左子節點。
```c=
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);
}
```
執行以下主程式：
```c=
int main() {
struct Node* root = createNode(10);
root->left = createNode(20);
root->right = createNode(30);
preorderTraversal(root);
}
```
Output：
```
10 20 30
```
#### 中序遍歷
中序遍歷的順序是左 -> 中 -> 右。
需要一個指標 `curr` 來持續往左走，沿途將經過的節點都推入堆疊，當走到盡頭（左子樹為空）時，從堆疊取出一個節點印出，接著轉向該節點的右子樹，重複同樣的過程。
```c=
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);
}
```
執行結果：
```
20 10 30
```
#### 後序遍歷
後序遍歷的順序是左 -> 右 -> 中。
後序遍歷在非遞迴處理上是最複雜的：當從左子樹返回中間節點時，還不能馬上印出中間節點，必須先去處理右子樹。
在此使用單一堆疊搭配一個 `lastVisited` 指標的方法：用以記錄上一個印出的節點。
若當前節點的右子樹為空，或者右子樹剛已被印出過（`lastVisited == curr->right`），就代表左右子樹都處理完了，可直接印出當前節點。
```c=
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 Source：筆者繪製。
那如果是橫的呢？請看下圖：
而所謂兄弟相連、保留長子就是像下面那樣：
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]`（左子樹）。
最後求出二元樹：
#### 後序 + 中序範例
假設題目給了兩組序列：
- 後序（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]`（左子樹）。
最後得出的結果與前序 + 中序的結果相同（此為範例刻意設計，後續遇到不同題目並不代表前序算出的結果跟後序一樣），一樣是這張圖：
## 引線二元樹（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 中，這樣的資料結構可定義成：
```c=
// 使用 bool 請引入 <stdbool.h>
struct ThreadNode {
int data; // 節點資料
ThreadNode *llink; // 左指標
ThreadNode *rlink; // 右指標
bool lTag; // 左標籤 (1: 子節點, 0: 引線)
bool rTag; // 右標籤 (1: 子節點, 0: 引線)
};
```
圖解：
Image Source：筆者繪製。
### 引線二元樹的長相
下圖實線代表一般正常的子節點指標（Link），虛線代表引線（Thread），也就是那些被重新利用的空指標。
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 Source：筆者繪製。
則其中序遍歷會是 1 -> 2 -> 3 -> 4 -> 6
設 `Curr = 1`，`Prev = NULL`，因為最左邊那個節點沒有前一個節點。
`Curr`（`1`）的左指標為空，因此把節點 1 的左引線指向 `Prev`（`Null`）。
接著再看 `Prev` 的右指標，而由於 `Prev` 現在是 `NULL`，所以啥事都不用幹，然後現在圖會變這樣：
前進走到節點 2（`Curr = 2`, `Prev = 1`）：
- 檢查 `Curr`（`2`）的左指標：有指向實體的節點 1，非空，所以不管他。
- 檢查 `Prev`（`1`）的右指標：為空，代表節點 1 需要一條後繼者引線，把節點 1 的右引線指向 `Curr`（`2`）。
接著前進走到節點 3（`Curr = 3`, `Prev = 2`）：
- 檢查 `Curr`（`3`）的左指標：為空，將節點 3 的左引線指向 `Prev`（`2`）。
- 檢查 `Prev`（`2`）的右指標：有指向實體的節點 `3`，非空，所以不管他。
然後走到節點 4（`Curr = 4`, `Prev = 3`）：
- 檢查 `Curr`（`4`）的左指標：有指向實體節點 2，不管他。
- 檢查 `Prev`（`3`）的右指標：為空，將節點 3 的右引線指向 `Curr`（`4`）。
最後走到節點 6（`Curr = 6`, `Prev = 4`）：
- 檢查 `Curr`（`6`）的左指標：為空，將節點 6 的左引線牽向 `Prev`（`4`）。
- 檢查 `Prev`（`4`）的右指標：有指向實體節點 6，不管他。
現在所有節點都走完了，做最後的收尾，Prev 停在最後一個節點 6，此時看他的右指標，會是空的，但他後面沒人了，所以將其右引線保持為 `Null`，並標記為引線。
### C 語言實作：尋找中序後繼者（Successor）
資料結構定義：
```c=
#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`），則其後繼者，即右子樹裡面最左邊的節點。
```c=
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`），則前行者即左子樹裡面最右邊的節點。
```c=
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` 為止。
```c=
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`。
程式實作：
```c=
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$ 節點的關係：$$N_0 = N_2 + 1$$ （葉節點永遠比有兩個子節點的內部節點多 $1$ 個）
3. 儲存表示法
| 表示法 | 特性與優缺點 | 節點索引關係（以 1-based index 為例） |
|-------|----------------------------------------|-----------------------------|
| 一維陣列 | 優點：適合完整／滿枝二元樹，存取快 $O(1)$。<br>缺點：若樹不平衡會嚴重浪費空間。 | 父節點：$\lfloor i/2 \rfloor$<br>左子節點：$2i$<br>右子節點：$2i+1$ |
| 鏈結表示法 | 優點：最常用、動態配置記憶體，插入／刪除快。<br>缺點：需額外空間存指標，無法隨機存取。 | 節點包含：`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`：左子樹中最右下角的節點。
Sign in via Google
Sign in via Facebook
Sign in via X(Twitter)
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Connect another wallet