書籍資訊
- 書名：
《圖解演算法：使用 C#》 - 類型：二叉樹與相關延伸結構整理
這篇在講什麼
這一篇圍繞在二叉樹，整理了幾個層次：
- 二叉樹的基本型態
- 如何表示二叉樹
- 常見遍歷方式
- 二叉搜尋樹
- 平衡樹、霍夫曼樹、線索二叉樹等延伸概念
二叉樹的基本型態
二叉樹的意思很直接：
- 每個節點最多只有兩個子節點
- 通常分成左子樹與右子樹
常見類型包括：
- 滿二叉樹
Fully Binary Tree - 完全二叉樹
Complete Binary Tree - 斜樹
Skewed Binary Tree - 嚴格二叉樹
Strictly Binary Tree
這些名詞的意義，在於幫助你判斷：
- 結構是否規整
- 高度是否容易失控
- 適合用哪種儲存方式
怎麼表示二叉樹
陣列表示法
如果樹夠規整，尤其接近完全二叉樹，可以直接用陣列表示。
常見索引關係是：
- 父節點在
i - 左子節點在
2 * i - 右子節點在
2 * i + 1
這種方式的好處是簡單，但缺點是：
- 樹一旦不平衡，空洞會很多
- 斜樹時會浪費大量空間
節點指標表示法
更一般的做法是每個節點保存：
- 值
- 左子節點
- 右子節點
這種表示法更靈活，也是實務上最常見的形式。
二叉樹遍歷
遍歷的本質是：
- 你打算用什麼順序拜訪所有節點
三種經典遞迴順序是：
- 前序：根 -> 左 -> 右
- 中序：左 -> 根 -> 右
- 後序：左 -> 右 -> 根
其中最常被拿來講性質的是中序遍歷，因為對二叉搜尋樹來說，中序遍歷會得到有序結果。
public static void InOrder(TreeNode node)
{
if (node == null)
{
return;
}
InOrder(node.left);
Console.WriteLine(node.val);
InOrder(node.right);
}二叉搜尋樹 BST
二叉搜尋樹 Binary Search Tree 的核心規則是：
- 左子樹所有值都比根小
- 右子樹所有值都比根大
這讓搜尋、插入、刪除都能利用比較結果，一路往左或往右縮小範圍。
它的價值在於：
- 平均情況下查找效率不錯
- 中序遍歷天然有序
但問題也很典型：
- 如果資料插入順序太差，樹可能一路歪掉
- 一歪就會接近鏈結串列
刪除節點時要想什麼
BST 刪除最常分三種情況：
- 刪葉節點：直接刪
- 只有一個子節點：讓父節點接過去
- 有兩個子節點：找前驅或後繼來補位
這裡最重要的不是背步驟，而是維持 BST 性質不能壞掉。
線索樹、延伸二叉樹、霍夫曼樹
線索二叉樹
線索二叉樹的目的是善用原本為 null 的指標，讓遍歷更方便。
它偏向資料結構教材中的經典技巧，重點在節點關係的重新利用。
延伸二叉樹
延伸二叉樹會把原本的空子節點位置也視為一種外部節點，方便做理論分析，例如：
- 外部路徑長度
- 內部路徑長度
霍夫曼樹
霍夫曼樹 Huffman Tree 的重點是加權路徑長最小。
它常用在：
- 最佳化編碼
- 壓縮問題
平衡樹與 AVL
BST 最大的問題是會失衡。
AVL 樹就是為了解決這件事而出現的。
它要求：
- 每個節點左右子樹高度差不能太大
這樣可以避免樹退化，讓搜尋、插入、刪除都維持比較穩定的效率。
所以 AVL 的核心不是「很會轉」，而是：
- 用旋轉維持高度平衡
我自己的整理
二叉樹這一篇的重點，其實可以壓成三句話：
- 樹的結構會影響操作成本
- 遍歷順序會影響你看到的結果
- 搜尋樹如果不平衡，優勢就會消失
後面那些延伸結構，都是在補二叉樹的不同弱點：
- 線索樹在補遍歷成本
- 霍夫曼樹在補加權路徑長
- AVL 在補平衡問題
先記住的重點
- 二叉樹是每個節點最多兩個子節點的樹
- 中序遍歷在 BST 上會得到有序序列
- BST 的效率仰賴結構不要失衡
- 刪除 BST 節點時，要先判斷子節點情況
- AVL 的重點是維持高度平衡，不讓樹退化