--- # System prepended metadata title: 【考試向】資料結構筆記（樹及二元樹） tags: [資料結構, 程式設計, 電腦] --- # 【考試向】資料結構筆記（樹及二元樹） [TOC] 歡迎你點入本篇文章！我是 LukeTseng，本系列文章主要整理自學資料結構的一些知識，如果你喜歡我的文章，麻煩您不吝嗇的在文章底下按下一顆愛心，或是追蹤我唷～ ## 簡介（Introduction） ![image](https://hackmd.io/_uploads/SyPuQz1tWe.png) 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](https://hackmd.io/_uploads/rJMfDFlF-g.png) Image Source：筆者繪製。 可用 C 語言撰寫成這樣： ```c= #include #include // 定義 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](https://hackmd.io/_uploads/Hk0KE_lYZe.png) 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](https://hackmd.io/_uploads/BkzwruxYbg.png) 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](https://hackmd.io/_uploads/SJreFOgYZe.png) 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](https://hackmd.io/_uploads/B18Jx0sh-l.png) 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](https://hackmd.io/_uploads/Hk_1sdeYbg.png) 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](https://hackmd.io/_uploads/rJDcBKet-g.png) Image Source：https://interviewing.io/questions/count-complete-tree-nodes ### 一維陣列表示二元樹 假設有棵樹長這樣（A、B、C、D、E、F 為資料，而括號內為編號、索引）： ![image](https://hackmd.io/_uploads/rkeb0Pbtbx.png) Image Source：筆者繪製。 該棵樹的最大節點數為 $2^3 - 1 = 7$ ，因此可將其表示成下列的一維陣列： ![image](https://hackmd.io/_uploads/BkFwJObYWg.png) 由於該棵樹是一棵完整二元樹（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](https://hackmd.io/_uploads/BJNKxKZY-g.png) Image Source：筆者繪製。 若寫成 C 語言，則會像下面這樣（不過通常都會寫成 `llink` 跟 `rlink`）： ```c= struct TreeNode { int data; // 儲存的資料 TreeNode* L_Link; // 指向左子樹的指標 TreeNode* R_Link; // 指向右子樹的指標 }; ``` 鏈結樹的圖形示意： ![image](https://hackmd.io/_uploads/HJhEbYWYbe.png) 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 #include // 定義二元樹的節點結構 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 #include #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](https://hackmd.io/_uploads/SJzfnA7tbx.png) Image Source：筆者繪製。 那如果是橫的呢？請看下圖： ![image](https://hackmd.io/_uploads/HyTb6RQY-l.png) 而所謂兄弟相連、保留長子就是像下面那樣： ![image](https://hackmd.io/_uploads/Sk75aAXY-l.png) 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](https://hackmd.io/_uploads/S1S0oZNFZx.png) #### 後序 + 中序範例 假設題目給了兩組序列： - 後序（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](https://hackmd.io/_uploads/S1S0oZNFZx.png) ## 引線二元樹（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 請引入 struct ThreadNode { int data; // 節點資料 ThreadNode *llink; // 左指標 ThreadNode *rlink; // 右指標 bool lTag; // 左標籤 (1: 子節點, 0: 引線) bool rTag; // 右標籤 (1: 子節點, 0: 引線) }; ``` 圖解： ![image](https://hackmd.io/_uploads/SyiO4-7tWl.png) Image Source：筆者繪製。 ### 引線二元樹的長相 下圖實線代表一般正常的子節點指標（Link），虛線代表引線（Thread），也就是那些被重新利用的空指標。 ![image](https://hackmd.io/_uploads/SyF-Hb7YWe.png) 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](https://hackmd.io/_uploads/HJMQszmKbx.png) Image Source：筆者繪製。 則其中序遍歷會是 1 -> 2 -> 3 -> 4 -> 6 設 `Curr = 1`，`Prev = NULL`，因為最左邊那個節點沒有前一個節點。 `Curr`（`1`）的左指標為空，因此把節點 1 的左引線指向 `Prev`（`Null`）。 接著再看 `Prev` 的右指標，而由於 `Prev` 現在是 `NULL`，所以啥事都不用幹，然後現在圖會變這樣： ![image](https://hackmd.io/_uploads/SJ-Wnz7F-l.png) 前進走到節點 2（`Curr = 2`, `Prev = 1`）： - 檢查 `Curr`（`2`）的左指標：有指向實體的節點 1，非空，所以不管他。 - 檢查 `Prev`（`1`）的右指標：為空，代表節點 1 需要一條後繼者引線，把節點 1 的右引線指向 `Curr`（`2`）。 ![image](https://hackmd.io/_uploads/ByI02zQKZe.png) 接著前進走到節點 3（`Curr = 3`, `Prev = 2`）： - 檢查 `Curr`（`3`）的左指標：為空，將節點 3 的左引線指向 `Prev`（`2`）。 - 檢查 `Prev`（`2`）的右指標：有指向實體的節點 `3`，非空，所以不管他。 ![image](https://hackmd.io/_uploads/HJQOpzXFZx.png) 然後走到節點 4（`Curr = 4`, `Prev = 3`）： - 檢查 `Curr`（`4`）的左指標：有指向實體節點 2，不管他。 - 檢查 `Prev`（`3`）的右指標：為空，將節點 3 的右引線指向 `Curr`（`4`）。 ![image](https://hackmd.io/_uploads/r131RMQYWx.png) 最後走到節點 6（`Curr = 6`, `Prev = 4`）： - 檢查 `Curr`（`6`）的左指標：為空，將節點 6 的左引線牽向 `Prev`（`4`）。 - 檢查 `Prev`（`4`）的右指標：有指向實體節點 6，不管他。 ![image](https://hackmd.io/_uploads/ryCH0GQFZg.png) 現在所有節點都走完了，做最後的收尾，Prev 停在最後一個節點 6，此時看他的右指標，會是空的，但他後面沒人了，所以將其右引線保持為 `Null`，並標記為引線。 ![image](https://hackmd.io/_uploads/S1wq0z7KZe.png) ### C 語言實作：尋找中序後繼者（Successor） 資料結構定義： ```c= #include #include 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)$。
缺點：若樹不平衡會嚴重浪費空間。 | 父節點：$\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`：左子樹中最右下角的節點。