二元樹基礎#
資料結構的演進#
從線性到非線性的演化過程：
單向連結串列 → 雙向連結串列 → 樹 → 圖
(1個next) (prev+next) (多個指標) (可有環)關鍵理解：
- 連結串列是特殊的樹（沒有分叉）
- 樹是特殊的圖（沒有環）
二元樹核心術語#
| 術語 | 說明 |
|---|---|
| 根節點 (Root) | 最頂端的節點 |
| 葉節點 (Leaf) | 沒有子節點的節點 |
| 高度 (Height) | 節點到葉節點的最長路徑 |
| 深度 (Depth) | 根節點到該節點的路徑長度 |
| 階層 (Level) | 深度 + 1 |
二元搜尋樹 (BST)#
定義#
BST 必須滿足：
- 左子樹所有節點值 < 根節點值
- 右子樹所有節點值 > 根節點值
- 左右子樹也必須是 BST（遞迴定義）
常見誤區：不能只比較直接子節點！必須確保整個子樹都滿足條件。
複雜度分析#
| 操作 | 平均 | 最差 |
|---|---|---|
| 搜尋 | O(log n) | O(n) |
| 插入 | O(log n) | O(n) |
| 刪除 | O(log n) | O(n) |
退化問題：依序插入 1,2,3,4,5 會使 BST 退化成連結串列，效率降為 O(n)。
解決方案：平衡二元樹#
- AVL 樹：嚴格平衡，左右子樹高度差 <= 1
- 紅黑樹：近似平衡，實作較簡單，工程常用
節點定義程式碼
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right