樹是第一個「遞迴天生合理」的資料結構：每個子樹本身就是一棵樹， 於是插入、搜尋、走訪的程式碼幾乎就是定義本身。二元搜尋樹（BST）把「排序」 內建到結構裡，讓搜尋從 O(n) 降到 O(log n)。本單元對應 K&R §6.5 的單字計數樹 ——K&R 全書最精彩的完整範例之一，並補充四種走訪、樹的釋放與平衡概念。

學習目標

  • 理解二元樹節點的遞迴定義與二元搜尋樹（BST）的不變量
  • 實作 BST 的插入、搜尋、最小/最大值
  • 掌握四種走訪：前序、中序、後序（遞迴）與層序（概念）
  • 重現 K&R §6.5 單字計數樹：統計文字中每個單字出現次數並依字典序輸出
  • 正確釋放整棵樹（後序釋放）
  • 理解樹高、退化與平衡的概念（為什麼需要 AVL / 紅黑樹）

對照章節 / 參考來源

  • K&R §6.5 Self-referential Structures（struct tnode、addtree、treeprint）
  • CLRS 第 12 章 Binary Search Trees、第 13 章 Red-Black Trees
  • Sedgewick《Algorithms》第 3.2 節 BST
  • Wikipedia: Tree traversal、AVL tree

觀念講解

1. 節點定義與 BST 不變量

struct tnode {
    int           value;
    struct tnode *left;
    struct tnode *right;
};

BST 不變量：任一節點的左子樹全部小於它，右子樹全部大於它。

以 50, 30, 70, 20, 40, 60, 80 的插入順序建樹：

            50
          /    \
        30      70
       /  \    /  \
     20    40 60    80

不變量讓搜尋每一步都能砍掉一半的候選——這就是二分搜尋的樹形化。

2. 插入與搜尋（遞迴）

struct tnode *insert(struct tnode *t, int v)
{
    if (t == NULL)               /* 走到空位：這就是 v 的家 */
        return node_new(v);
    if (v < t->value)
        t->left = insert(t->left, v);
    else if (v > t->value)
        t->right = insert(t->right, v);
    /* 相等：忽略（或計數，見單字計數樹） */
    return t;
}

「回傳子樹根、呼叫端接回去」的寫法讓空樹與非空樹共用同一段碼。 搜尋同構：小往左、大往右、相等即命中、NULL 即不存在。

3. 四種走訪

走訪 順序 典型用途
前序 preorder 根 → 左 → 右 複製樹、序列化、印目錄結構
中序 inorder 左 → 根 → 右 BST 中序 = 由小到大排序
後序 postorder 左 → 右 → 根 釋放記憶體、計算子樹彙總
層序 level-order 一層一層由上而下 最短路徑、印樹形、需要佇列輔助

前三種是「同一段遞迴碼、printf 擺的位置不同」； 層序不是遞迴而是 BFS：用上一單元的佇列，出隊時把子節點入隊。

4. K&R 單字計數樹

K&R §6.5 的問題：統計輸入中每個單字的出現次數，並依字典序印出。 BST 一石二鳥：插入時若單字已存在就 count++，中序走訪天然就是字典序：

struct tnode {                  /* K&R 原版結構 */
    char         *word;
    int           count;
    struct tnode *left;
    struct tnode *right;
};

addtree 用 strcmp 決定往左往右；treeprint 中序輸出。 這個 60 行的程式同時用到：結構、遞迴、動態記憶體、字串處理—— 是檢驗前面所有章節是否融會貫通的試金石。

5. 釋放樹：必須後序

先釋放兩個子樹、最後釋放自己——順序反了就是 use-after-free：

void tree_free(struct tnode *t)
{
    if (t == NULL) return;
    tree_free(t->left);
    tree_free(t->right);
    free(t);            /* 自己最後走 */
}

6. 樹高、退化與平衡

搜尋成本 = 走訪路徑長 ≤ 樹高。隨機順序插入 n 個鍵，期望高度 O(log n)； 但已排序的輸入會讓 BST 退化成鏈結串列：

insert 10, 20, 30, 40:      10
                              \
                               20      高度 = n，搜尋 O(n)
                                 \     （最壞情況！）
                                  30
                                    \
                                     40
情況 高度 搜尋/插入
完全平衡 ⌈log₂(n+1)⌉ O(log n)
隨機插入（期望） ≈ 1.39 log₂ n O(log n)
已排序輸入（退化） n O(n)

自平衡樹（AVL、紅黑樹）在插入刪除時做旋轉維持高度 O(log n)； Linux 核心、C++ std::map、Java TreeMap 都用紅黑樹。本單元示範退化現象， 平衡演算法留作進階閱讀。

範例程式

檔案 內容 編譯 / 執行
01_bst.c BST 全套：插入/搜尋/min/max/三種遞迴走訪/層序/樹高/釋放/退化示範 cc -std=c11 -Wall -Wextra -o out 01_bst.c && ./out
02_wordcount_tree.c K&R §6.5 單字計數樹：對寫死的文章統計詞頻並依字典序輸出 cc -std=c11 -Wall -Wextra -o out 02_wordcount_tree.c && ./out

常見錯誤與陷阱

  1. 忘記接回遞迴結果：insert(t->left, v); 沒寫 t->left =， 新節點掛不上去，樹永遠只有根。
  2. 釋放順序錯誤：先 free(t) 再 tree_free(t->left) 是 use-after-free； 釋放必須後序。
  3. 比較字串用 ==：t->word == w 比的是指標；單字計數樹必須用 strcmp。
  4. 重複鍵沒有策略：插入相等的值時要嘛忽略、要嘛計數、要嘛允許重複放右邊， 沒想清楚會導致「searched but not found」的詭異 bug。
  5. 對已排序資料用普通 BST：退化成 O(n)。輸入可能有序時， 先洗牌、或改用自平衡樹。

練習題

  1. 【易】實作 tree_count（節點總數）與 tree_sum（鍵值總和），皆為遞迴一行式。
  2. 【易】實作 tree_min / tree_max（一路向左／向右的迭代版本）。
  3. 【中】實作 tree_to_array：中序走訪把 BST 的值填進已排序陣列， 驗證「中序 = 排序」。
  4. 【中】為單字計數樹加上「出現次數排行榜」：把節點倒進陣列後用 qsort 依 count 遞減排序，印前 5 名（複習函式指標單元）。
  5. 【難】實作 BST 的刪除（三種情況：葉、單子、雙子——雙子用中序後繼頂替）。
  6. 【難】實作 tree_balance：中序倒出排序陣列後，遞迴取中點重建完全平衡的樹， 前後各印一次樹高比較。

補充：樹在真實系統中的樣子

  • 檔案系統：目錄結構就是一棵樹；du、find 都是樹走訪。
  • 編譯器：原始碼被解析成抽象語法樹（AST）， 之後的型別檢查、最佳化、產碼全是樹走訪（多半是後序）。
  • 資料庫索引：B-tree / B+tree 是 BST 的「多叉、磁碟友善」版本， 每個節點存幾百個鍵以配合磁碟頁大小。
  • 優先佇列：binary heap 是「以陣列存的完全二元樹」， 父節點在 i，子節點在 2i+1、2i+2——不需要指標的樹。
  • 前綴樹（trie）：鍵是字串時逐字元分支，自動完成、路由表用它。

延伸閱讀

  • K&R §6.5（addtree/treeprint 原始碼）與習題 6-2、6-3
  • CLRS 第 12–13 章（BST 與紅黑樹）
  • Sedgewick, "Left-leaning Red-Black Trees"（較易實作的紅黑樹變體）
  • Linux 核心 lib/rbtree.c
  • 《The Art of Computer Programming》Vol.3 §6.2.2（樹搜尋的數學分析）