視覺化概覽
graph TD N50["50"] --> N30["30"] N50 --> N70["70"] N30 --> N20["20"] N30 --> N40["40"] N70 --> N60["60"] N70 --> N80["80"] L1["左子樹 < 根"] -.-> N30 R1["右子樹 > 根"] -.-> N70 style N50 fill:#f9f,stroke:#333,stroke-width:2px style L1 fill:#fff,stroke:#999,stroke-dasharray: 5 5 style R1 fill:#fff,stroke:#999,stroke-dasharray: 5 5
什麼是樹？
樹是階層式的資料結構，有一個根節點，每個節點可以有多個子節點。
50 ← 根 (root)
/ \
30 70 ← 子節點
/ \ / \
20 40 60 80 ← 葉節點 (沒有子節點)
基本術語
| 術語 | 說明 |
|---|---|
| Root | 最頂端的節點 |
| Parent | 有子節點的節點 |
| Child | 被指向的節點 |
| Leaf | 沒有子節點的節點 |
| Height | 從根到最深葉節點的距離 |
| Depth | 從根到該節點的距離 |
Binary Tree 二元樹
每個節點最多有兩個子節點（左、右）。
class Node {
int value;
Node left; // 左子節點
Node right; // 右子節點
}Binary Search Tree (BST) 二元搜尋樹
特殊的二元樹，具有排序特性：
- 左子樹所有節點 < 根節點
- 右子樹所有節點 > 根節點
50
/ \
30 70 30 < 50 < 70 ✓
/ \ / \
20 40 60 80 20 < 30 < 40 ✓
時間複雜度
| 操作 | 平均 | 最差（退化成鏈表） |
|---|---|---|
| 搜尋 | O(log n) | O(n) |
| 插入 | O(log n) | O(n) |
| 刪除 | O(log n) | O(n) |
BST 插入
插入 25:
50
/ \
30 70
/
20
\
25 ← 新節點
過程: 50 → 左(25<50) → 30 → 左(25<30) → 20 → 右(25>20) → 插入
BST 搜尋
搜尋 40:
50
/ \
30 70
/ \
20 40 ← 找到！
過程: 50 → 左(40<50) → 30 → 右(40>30) → 40 ✓
BST 刪除
三種情況：
Case 1: 刪除葉節點
直接刪除。
刪除 20:
30 30
/ \ → \
20 40 40
Case 2: 有一個子節點
用子節點替代。
刪除 30:
50 50
/ \ → / \
30 70 40 70
\
40
Case 3: 有兩個子節點
用右子樹的最小值替代。
刪除 50:
50 60
/ \ → / \
30 70 30 70
/
60
遍歷方式
50
/ \
30 70
| 方式 | 順序 | 結果 | 用途 |
|---|---|---|---|
| 中序 In-order | 左→根→右 | 30, 50, 70 | BST 排序輸出 |
| 前序 Pre-order | 根→左→右 | 50, 30, 70 | 複製樹 |
| 後序 Post-order | 左→右→根 | 30, 70, 50 | 刪除樹 |
| 層序 Level-order | 一層一層 | 50, 30, 70 | BFS |
中序遍歷的特殊性
BST 的中序遍歷會得到排序後的結果！
BST: 中序遍歷:
50 → [20, 30, 40, 50, 60, 70, 80]
/ \ 已排序！
30 70
/ \ / \
20 40 60 80
樹的變體
| 類型 | 特性 |
|---|---|
| AVL Tree | 自平衡，高度差 ≤ 1 |
| Red-Black Tree | 自平衡，Java TreeMap 使用 |
| B-Tree | 多路樹，資料庫索引使用 |
| Trie | 前綴樹，字串搜尋 |
為什麼需要平衡？
最差情況：依序插入 1,2,3,4,5
1
\
2
\
3 → 變成鏈表！
\ 搜尋變 O(n)
4
\
5
解法：使用 AVL 或 Red-Black Tree 自動平衡。
相關檔案
- Java 實作：BinarySearchTree.java
- 視覺化：tree.html