練習題與詳解 — 樹

本檔收錄 5 題由易到難的練習。建議流程：先蓋住解答自己寫，卡住再看「解題思路」，寫完對照「參考解答」。每題完整程式碼在 exercises/：

cc -std=c11 -Wall -Wextra -o /tmp/out exercises/ex1_count_sum.c && /tmp/out

貫穿本單元的心法：樹的問題先想遞迴公式—— 「整棵樹的答案 = 我自己 ⊕ 左子樹的答案 ⊕ 右子樹的答案」，基底是空樹。想清楚公式，程式常常只有一行。

練習 1：tree_count 與 tree_sum（難度：基礎）

題目

實作 tree_count（節點總數）與 tree_sum（鍵值總和），皆為遞迴一行式。以下面這棵 BST 驗證（count=8、sum=360），並測子樹與空樹：

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

解題思路

遞迴公式（樹的一切從這裡開始）：

count(空)   = 0
count(t)    = 1 + count(t->left) + count(t->right)

sum(空)     = 0
sum(t)      = t->key + sum(t->left) + sum(t->right)

兩式結構完全相同，只差「我自己」貢獻什麼（1 或 key）與合併運算（都是加法）。這個模式叫樹摺疊（fold）—— 之後的高度、深度、找最值全是它的變體。 2. 為什麼敢遞迴：每次呼叫的樹嚴格變小（往子樹走），基底（NULL）一定會到——終止性有保證。 3. 一行式：條件運算子 t == NULL ? 0 : ... 讓公式直譯成程式；教學上先寫 if 版本，熟了之後一行式更貼近數學定義。 4. 釋放：樹的釋放必須後序（先左右子樹、後自己）—— 先 free 自己就拿不到子樹指標了。 5. sum 用 long 累加：鍵多或值大時 int 可能溢位。

參考解答

/*
 * ex1_count_sum.c — 練習 1：tree_count 與 tree_sum（遞迴一行式）
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex1_count_sum.c
 * 執行：/tmp/out
 *
 * 樹的遞迴公式：
 *   count(t) = t 為空 ? 0 : 1 + count(左) + count(右)
 *   sum(t)   = t 為空 ? 0 : 值 + sum(左) + sum(右)
 */
#include <stdio.h>
#include <stdlib.h>

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

/* BST 插入（重複鍵忽略） */
static struct tnode *insert(struct tnode *t, int key)
{
    if (t == NULL) {
        t = malloc(sizeof *t);
        if (t == NULL) {
            fprintf(stderr, "out of memory\n");
            exit(1);
        }
        t->key = key;
        t->left = t->right = NULL;
    } else if (key < t->key) {
        t->left = insert(t->left, key);
    } else if (key > t->key) {
        t->right = insert(t->right, key);
    }
    return t;
}

/* 節點總數：空樹 0，否則自己 1 個 + 兩棵子樹 */
static int tree_count(const struct tnode *t)
{
    return t == NULL ? 0 : 1 + tree_count(t->left) + tree_count(t->right);
}

/* 鍵值總和：空樹 0，否則自己的值 + 兩棵子樹的和 */
static long tree_sum(const struct tnode *t)
{
    return t == NULL ? 0 : t->key + tree_sum(t->left) + tree_sum(t->right);
}

/* 中序印出（遞增） */
static void print_inorder(const struct tnode *t)
{
    if (t == NULL)
        return;
    print_inorder(t->left);
    printf(" %d", t->key);
    print_inorder(t->right);
}

/* 後序釋放：先釋放子樹再釋放自己 */
static void tree_free(struct tnode *t)
{
    if (t == NULL)
        return;
    tree_free(t->left);
    tree_free(t->right);
    free(t);
}

int main(void)
{
    int keys[] = { 50, 30, 70, 20, 40, 60, 80, 10 };
    size_t n = sizeof keys / sizeof keys[0];

    struct tnode *root = NULL;
    for (size_t i = 0; i < n; i++)
        root = insert(root, keys[i]);

    /*
     * 樹形：            50
     *                 /    \
     *               30      70
     *              /  \    /  \
     *            20    40 60   80
     *           /
     *         10
     */
    printf("inorder:");
    print_inorder(root);
    printf("\n\n");

    printf("tree_count = %d  (expected 8)\n", tree_count(root));
    printf("tree_sum   = %ld (expected 360)\n", tree_sum(root));

    printf("\nsubtree checks:\n");
    printf("  count(left of root)  = %d\n", tree_count(root->left));
    printf("  count(right of root) = %d\n", tree_count(root->right));

    printf("\nempty tree: count=%d sum=%ld\n",
           tree_count(NULL), tree_sum(NULL));

    tree_free(root);
    return 0;
}

程式碼講解

tree_count 與 tree_sum 各一行，直譯遞迴公式；參數 const struct tnode * 標明查詢不改樹。
子樹檢查 tree_count(root->left) = 4（30、20、40、10）、右邊 3 個——遞迴函式天然支援「對任意子樹發問」，這是把參數設計成「子樹根」的好處。
空樹回 0 讓兩個函式不需要任何特判就能處理空輸入—— 基底選對，邊界自動正確。
tree_free 是後序走訪的應用：三種走訪順序各有用途（中序=排序、前序=複製、後序=釋放/計算）。
易錯處：釋放寫成前序（先 free(t) 再遞迴 t->left）—— use-after-free。

範例輸出

inorder: 10 20 30 40 50 60 70 80

tree_count = 8  (expected 8)
tree_sum   = 360 (expected 360)

subtree checks:
  count(left of root)  = 4
  count(right of root) = 3

empty tree: count=0 sum=0

練習 2：tree_min / tree_max（迭代版）（難度：基礎）

題目

實作 tree_min／tree_max 的迭代版本（一路向左／向右）。回傳節點指標（空樹回 NULL）。驗證：整棵樹的 min/max、右子樹的 min（= 大於根的最小鍵）、空樹。

解題思路

BST 的排序性質：左子樹全部 < 根 < 右子樹全部。推論：最小值在「最左」的節點——從根出發，有左子就往左，走到沒有左子為止。最大值鏡像。
為什麼用迭代：遞迴版 `return t->left ? tree_min(t->left)

t;` 是尾端遞迴——遞迴呼叫是函式的最後一步，沒有「回來之後還要做的事」，可以機械式改寫成 while 迴圈：不吃堆疊空間，樹再深（退化成串列時 O(n) 深）也不怕爆棧。
介面設計：回傳「節點指標」而非「值」—— 空樹沒有最小值，NULL 自然表達「不存在」；回傳值的版本就得用 found 旗標（同串列單元練習 1 的討論）。
右子樹的 min 是誰：大於根的所有鍵中最小的—— 這正是刪除演算法（練習 4）要用的「中序後繼」，先在這裡熟悉。

參考解答

/*
 * ex2_min_max.c — 練習 2：tree_min / tree_max（迭代版）
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex2_min_max.c
 * 執行：/tmp/out
 *
 * BST 的排序性質：最小值 = 一路向左走到底；最大值 = 一路向右。
 * 用迴圈而非遞迴——尾端遞迴改寫成迭代的典型例子。
 */
#include <stdio.h>
#include <stdlib.h>

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

static struct tnode *insert(struct tnode *t, int key)
{
    if (t == NULL) {
        t = malloc(sizeof *t);
        if (t == NULL) {
            fprintf(stderr, "out of memory\n");
            exit(1);
        }
        t->key = key;
        t->left = t->right = NULL;
    } else if (key < t->key) {
        t->left = insert(t->left, key);
    } else if (key > t->key) {
        t->right = insert(t->right, key);
    }
    return t;
}

/*
 * 最小值：從根一路向左。
 * 空樹沒有最小值——回傳節點指標而非值，NULL 自然表達「不存在」。
 */
static const struct tnode *tree_min(const struct tnode *t)
{
    if (t == NULL)
        return NULL;
    while (t->left != NULL)         /* 還有更小的：繼續左走 */
        t = t->left;
    return t;
}

/* 最大值：一路向右 */
static const struct tnode *tree_max(const struct tnode *t)
{
    if (t == NULL)
        return NULL;
    while (t->right != NULL)
        t = t->right;
    return t;
}

static void print_inorder(const struct tnode *t)
{
    if (t == NULL)
        return;
    print_inorder(t->left);
    printf(" %d", t->key);
    print_inorder(t->right);
}

static void tree_free(struct tnode *t)
{
    if (t == NULL)
        return;
    tree_free(t->left);
    tree_free(t->right);
    free(t);
}

int main(void)
{
    int keys[] = { 50, 30, 70, 20, 40, 60, 80, 10, 90 };
    struct tnode *root = NULL;
    for (size_t i = 0; i < sizeof keys / sizeof keys[0]; i++)
        root = insert(root, keys[i]);

    printf("inorder:");
    print_inorder(root);
    printf("\n\n");

    const struct tnode *mn = tree_min(root);
    const struct tnode *mx = tree_max(root);
    printf("tree_min = %d  (leftmost node)\n", mn->key);
    printf("tree_max = %d  (rightmost node)\n", mx->key);

    /* 子樹的 min/max：對 root->right 這棵子樹再問一次 */
    printf("\nmin of right subtree (keys > 50) = %d\n",
           tree_min(root->right)->key);

    /* 空樹 */
    printf("empty tree: min is %s\n",
           tree_min(NULL) == NULL ? "NULL (no minimum)" : "?");

    tree_free(root);
    return 0;
}

程式碼講解

while (t->left != NULL) t = t->left;——兩行就是全部；進迴圈前先擋掉空樹（t == NULL），否則第一步就解參考 NULL。
回傳 const struct tnode *：呼叫端可以讀 key，但不被鼓勵透過這個指標改樹。
tree_min(root->right) 展示「子樹即樹」：同一個函式不加修改就能回答子樹問題。
易錯處：迴圈條件寫成 t != NULL（走到 NULL 才停）—— 停下來時 t 已是 NULL，拿不到最後一個節點；正確條件是「還有左子」。

範例輸出

inorder: 10 20 30 40 50 60 70 80 90

tree_min = 10  (leftmost node)
tree_max = 90  (rightmost node)

min of right subtree (keys > 50) = 60
empty tree: min is NULL (no minimum)

練習 3：tree_to_array——中序即排序（難度：進階）

題目

實作 tree_to_array：中序走訪把 BST 的所有鍵填進陣列，驗證陣列已排序（證明「BST 中序 = 排序」）。陣列大小用 tree_count 先算好、一次配置；測資用亂序插入的 10 個鍵。

解題思路

為什麼中序是排序：對任一節點，中序順序是「左子樹全部 → 自己 → 右子樹全部」，而 BST 保證左 < 自己 < 右——歸納每個節點都在正確的相對位置，整體即遞增。這是 BST 最重要的定理。
填陣列的游標問題：遞迴各層都要往同一個陣列寫，「下一個空位」必須跨層共享——把游標做成 int *idx 傳指標，每層 arr[(*idx)++] = t->key;。不變量：「左子樹填完時，游標恰好停在我的位置」。
兩段式介面：tree_to_array 先 tree_count 算大小、 malloc 剛好的空間，再呼叫遞迴的 fill_inorder—— 「算需求、配置、填入」三步曲（同 concat 練習的兩遍掃描）。
驗證：相鄰元素兩兩比較 arr[i-1] <= arr[i]—— O(n) 的排序檢查，不需要眼睛比對。
用途：這是「BST → 排序資料」的橋樑，練習 5 的平衡重建第一步就是它；也是 tree sort 排序法的後半段。

參考解答

/*
 * ex3_to_array.c — 練習 3：tree_to_array——中序走訪即排序
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex3_to_array.c
 * 執行：/tmp/out
 *
 * 中序走訪 BST（左 -> 根 -> 右）恰好按遞增順序拜訪每個節點。
 * 把值填進陣列並驗證有序，證明「中序 = 排序」。
 */
#include <stdio.h>
#include <stdlib.h>

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

static struct tnode *insert(struct tnode *t, int key)
{
    if (t == NULL) {
        t = malloc(sizeof *t);
        if (t == NULL) {
            fprintf(stderr, "out of memory\n");
            exit(1);
        }
        t->key = key;
        t->left = t->right = NULL;
    } else if (key < t->key) {
        t->left = insert(t->left, key);
    } else if (key > t->key) {
        t->right = insert(t->right, key);
    }
    return t;
}

static int tree_count(const struct tnode *t)
{
    return t == NULL ? 0 : 1 + tree_count(t->left) + tree_count(t->right);
}

/*
 * 中序走訪填陣列。
 * idx 用指標共享：所有遞迴層共用同一個游標，
 * 「左子樹填完，游標剛好停在我的位置」。
 */
static void fill_inorder(const struct tnode *t, int *arr, int *idx)
{
    if (t == NULL)
        return;
    fill_inorder(t->left, arr, idx);    /* 1. 比我小的先進陣列 */
    arr[(*idx)++] = t->key;             /* 2. 輪到我 */
    fill_inorder(t->right, arr, idx);   /* 3. 比我大的最後 */
}

/* 包裝：配置剛好大小的陣列並填滿 */
static int *tree_to_array(const struct tnode *root, int *n_out)
{
    int n = tree_count(root);
    int *arr = malloc((size_t)(n > 0 ? n : 1) * sizeof *arr);
    if (arr == NULL) {
        fprintf(stderr, "out of memory\n");
        exit(1);
    }
    int idx = 0;
    fill_inorder(root, arr, &idx);
    *n_out = n;
    return arr;
}

static void tree_free(struct tnode *t)
{
    if (t == NULL)
        return;
    tree_free(t->left);
    tree_free(t->right);
    free(t);
}

int main(void)
{
    /* 刻意亂序插入 */
    int keys[] = { 42, 7, 99, 1, 23, 65, 88, 15, 3, 57 };
    size_t nk = sizeof keys / sizeof keys[0];

    struct tnode *root = NULL;
    printf("insert order:");
    for (size_t i = 0; i < nk; i++) {
        printf(" %d", keys[i]);
        root = insert(root, keys[i]);
    }
    printf("\n");

    int n;
    int *arr = tree_to_array(root, &n);

    printf("tree_to_array:");
    for (int i = 0; i < n; i++)
        printf(" %d", arr[i]);
    printf("\n");

    /* 驗證有序：每對相鄰元素檢查一次 */
    int sorted = 1;
    for (int i = 1; i < n; i++)
        if (arr[i - 1] > arr[i])
            sorted = 0;
    printf("sorted? %s  (inorder traversal of a BST is sorted)\n",
           sorted ? "yes" : "NO -- bug!");

    free(arr);
    tree_free(root);
    return 0;
}

程式碼講解

fill_inorder 的三行正是中序的定義：左、自己、右。把 arr[(*idx)++] 那行搬到最前／最後就變前序／後序—— 走訪順序只是「處理自己」的位置不同。
idx 傳 int * 而不是 int：值傳遞的話每層各有一份游標，彼此覆蓋——這是新手在「遞迴 + 陣列」組合最常犯的錯。（另一種寫法：讓函式回傳「下一個空位」，函數式風格。）
malloc(n > 0 ? n : 1)：空樹時避免 malloc(0) （回傳值實作定義），配 1 個位元組的哨兵空間。
驗證迴圈用 >（嚴格遞增檢查用 >=）：本 BST 忽略重複鍵，嚴格遞增成立。
易錯處：先序或後序填陣列——輸出不是排序的；「sorted? NO」的檢查就是為此而設。

範例輸出

insert order: 42 7 99 1 23 65 88 15 3 57
tree_to_array: 1 3 7 15 23 42 57 65 88 99
sorted? yes  (inorder traversal of a BST is sorted)

練習 4：BST 刪除的三種情況（難度：挑戰）

題目

實作 tree_delete(t, key)，正確處理三種情況並逐一示範：

葉節點：直接摘除；
單一子節點：子樹頂上來；
兩個子節點：用中序後繼（右子樹最小值）頂替，再到右子樹刪除後繼原節點。

也要測「刪除不存在的鍵」（樹不變）。每次刪除後印中序驗證。

解題思路

介面：回傳新子樹根。刪除可能改變子樹的根（根被刪掉時），所以用 t->left = tree_delete(t->left, key) 的「遞迴改寫」模式——與 insert 同構，父節點的指標由遞迴回傳值自動接好。
先找後刪：key 與 t->key 比大小決定往左往右走（BST 性質），相等才進入刪除邏輯。
三種情況逐一分析：

text 情況 1（葉）：情況 2（單子）：情況 3（雙子）： 30 40 50 / \ \ del 40 / \ 20 40 del 10 45 ------> 30 70 / ------> 45 / \ / \ 10 摘掉，父指 NULL 頂上來 20 40 60 80 del 50：用 60 頂替

情況 1、2 可合併：「至多一個子節點」→ 把那個子樹（可能是 NULL）回傳給父節點，free 自己。
情況 3 不能直接摘（兩個子樹沒地方掛）。 4. 中序後繼的選擇：要找一個「頂上來之後 BST 性質仍成立」的鍵——比左子樹全部大、比右子樹其餘的都小，唯二人選：左子樹最大值（前驅）或右子樹最小值（後繼）。本解用後繼：右子樹一路向左（複習練習 2）。 5. 為什麼不會無窮遞迴：後繼是右子樹的最小值， 不可能有左子——到右子樹刪它必落入情況 1 或 2，遞迴深度最多再一層鏈。 6. 技巧：情況 3 實際上「複製鍵、刪後繼」—— 移動的是值不是節點，省去改一堆指標。

參考解答

/*
 * ex4_bst_delete.c — 練習 4：BST 刪除的三種情況
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex4_bst_delete.c
 * 執行：/tmp/out
 *
 * 刪除節點的三種情況：
 *   1. 葉節點       直接摘除
 *   2. 單一子節點   子樹頂上來
 *   3. 兩個子節點   用「中序後繼」（右子樹最小值）頂替，
 *                   再到右子樹刪掉後繼原本的節點
 */
#include <stdio.h>
#include <stdlib.h>

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

static struct tnode *insert(struct tnode *t, int key)
{
    if (t == NULL) {
        t = malloc(sizeof *t);
        if (t == NULL) {
            fprintf(stderr, "out of memory\n");
            exit(1);
        }
        t->key = key;
        t->left = t->right = NULL;
    } else if (key < t->key) {
        t->left = insert(t->left, key);
    } else if (key > t->key) {
        t->right = insert(t->right, key);
    }
    return t;
}

/*
 * 刪除 key，回傳新的子樹根（遞迴改寫父節點的指標）。
 * 遞迴先「找到」節點（沿 BST 性質左右走），找到後分三種情況。
 */
static struct tnode *tree_delete(struct tnode *t, int key)
{
    if (t == NULL)
        return NULL;                    /* 沒找到：什麼都不做 */

    if (key < t->key) {
        t->left = tree_delete(t->left, key);
    } else if (key > t->key) {
        t->right = tree_delete(t->right, key);
    } else {
        /* 找到了。情況 1 & 2：至多一個子節點 -> 子樹頂上來 */
        if (t->left == NULL) {
            struct tnode *r = t->right;     /* 葉節點時 r 是 NULL */
            free(t);
            return r;
        }
        if (t->right == NULL) {
            struct tnode *l = t->left;
            free(t);
            return l;
        }

        /*
         * 情況 3：雙子節點。
         * 中序後繼 = 右子樹的最小值 = 「剛好比我大的鍵」。
         * 用它的鍵覆蓋我，再到右子樹刪除那個鍵——
         * 後繼最多只有右子（它是最小值，不可能有左子），
         * 遞迴一定落入情況 1 或 2，不會無窮遞迴。
         */
        struct tnode *succ = t->right;
        while (succ->left != NULL)
            succ = succ->left;
        t->key = succ->key;                     /* 頂替 */
        t->right = tree_delete(t->right, succ->key);
    }
    return t;
}

static void print_inorder(const struct tnode *t)
{
    if (t == NULL)
        return;
    print_inorder(t->left);
    printf(" %d", t->key);
    print_inorder(t->right);
}

static void show(const char *msg, const struct tnode *root)
{
    printf("%-28s:", msg);
    print_inorder(root);
    printf("\n");
}

static void tree_free(struct tnode *t)
{
    if (t == NULL)
        return;
    tree_free(t->left);
    tree_free(t->right);
    free(t);
}

int main(void)
{
    /*
     * 建這棵樹：         50
     *                  /    \
     *                30      70
     *               /  \    /  \
     *             20    40 60   80
     *            /        \
     *          10          45
     */
    int keys[] = { 50, 30, 70, 20, 40, 60, 80, 10, 45 };
    struct tnode *root = NULL;
    for (size_t i = 0; i < sizeof keys / sizeof keys[0]; i++)
        root = insert(root, keys[i]);

    show("initial tree (inorder)", root);

    root = tree_delete(root, 10);       /* 情況 1：葉節點 */
    show("delete 10 (leaf)", root);

    root = tree_delete(root, 40);       /* 情況 2：單子節點（右子 45） */
    show("delete 40 (one child)", root);

    root = tree_delete(root, 50);       /* 情況 3：雙子節點（根！） */
    show("delete 50 (two children)", root);
    printf("  (50 replaced by inorder successor 60)\n");

    root = tree_delete(root, 999);      /* 不存在的鍵：無變化 */
    show("delete 999 (absent)", root);

    tree_free(root);
    return 0;
}

程式碼講解

前兩個 if（t->left == NULL／t->right == NULL）優雅地合併了情況 1 與 2：葉節點時 t->right 是 NULL，「回傳 NULL 給父節點」與「摘除」是同一件事。
情況 3 的 while (succ->left != NULL) 就是 tree_min 的迭代版——練習 2 不是白做的。
t->key = succ->key; 之後必須刪右子樹中的 succ 原節點，否則同鍵出現兩次；遞迴 tree_delete(t->right, succ->key) 重用同一個函式，正是遞迴設計的紅利。
刪除不存在的鍵：第一個 if (t == NULL) return NULL; 讓遞迴走到底自然結束，樹原封不動——不需要特別的「找不到」處理。
易錯處一：情況 3 頂替後忘記刪後繼原節點（重複鍵）。
易錯處二：用「左子樹最大值」但仍到右子樹去刪—— 刪錯邊，樹壞掉。前驅／後繼與刪除方向必須配對。

範例輸出

initial tree (inorder)      : 10 20 30 40 45 50 60 70 80
delete 10 (leaf)            : 20 30 40 45 50 60 70 80
delete 40 (one child)       : 20 30 45 50 60 70 80
delete 50 (two children)    : 20 30 45 60 70 80
  (50 replaced by inorder successor 60)
delete 999 (absent)         : 20 30 45 60 70 80

練習 5：tree_balance——重建平衡樹（難度：挑戰）

題目

實作 tree_balance：中序倒出排序陣列（練習 3），遞迴取中點重建完全平衡的 BST，前後各印一次樹高比較。測資用最壞情況：遞增插入 1..15（樹退化成高度 15 的「串列」），平衡後高度應為 4。

解題思路

問題背景：BST 的效率靠「高度低」；插入順序不好（已排序資料）會讓樹退化成串列，查找從 O(log n) 掉到 O(n)。 AVL／紅黑樹邊插邊修；本題練習一次性重建—— 簡單但需要 O(n) 停機時間的離線方案。
排序陣列 → 平衡樹：取中點當根，左半遞迴建左子樹、右半建右子樹：

arr = 1..15，mid=8 當根：
                 8
              /     \
        (1..7)       (9..15)
          4             12
        /   \         /    \
       2     6      10      14
      / \   / \    /  \    /  \
     1   3 5   7  9   11  13   15

每層元素數減半 → 高度 = ⌈log₂(n+1)⌉，達到理論下限。 3. 為什麼中點是對的：左右兩半大小最多差 1，遞迴每層都維持這個性質——歸納得整棵樹每個節點的兩子樹節點數差 ≤ 1（比 AVL 的高度差 ≤ 1 更強）。 4. 組裝流程：count → malloc 陣列 → fill_inorder → build_balanced → free 陣列 → free 舊樹（節點是新配的，舊的不釋放就漏一整棵樹）。 5. 中點公式：lo + (hi - lo) / 2 而非 (lo + hi) / 2—— 後者在極大索引時可能溢位；本題不會，但慣用式值得養成。 6. 驗證：高度 15 → 4；中序輸出前後一致（重建不能弄丟或弄亂鍵）；根是 8、兩子是 4 與 12。

參考解答

/*
 * ex5_balance.c — 練習 5：tree_balance——重建完全平衡的 BST
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex5_balance.c
 * 執行：/tmp/out
 *
 * 步驟：
 *   1. 中序走訪把鍵倒進排序陣列（複習練習 3）
 *   2. 遞迴取中點當根、左半建左子樹、右半建右子樹
 *   3. 前後各印一次樹高比較
 * 最壞示範：遞增序列插入把 BST 退化成串列（高 = n），
 * 平衡後高度回到 ⌈log2(n+1)⌉。
 */
#include <stdio.h>
#include <stdlib.h>

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

static struct tnode *new_node(int key)
{
    struct tnode *t = malloc(sizeof *t);
    if (t == NULL) {
        fprintf(stderr, "out of memory\n");
        exit(1);
    }
    t->key = key;
    t->left = t->right = NULL;
    return t;
}

static struct tnode *insert(struct tnode *t, int key)
{
    if (t == NULL)
        return new_node(key);
    if (key < t->key)
        t->left = insert(t->left, key);
    else if (key > t->key)
        t->right = insert(t->right, key);
    return t;
}

static int tree_count(const struct tnode *t)
{
    return t == NULL ? 0 : 1 + tree_count(t->left) + tree_count(t->right);
}

/* 樹高：空樹 0，否則 1 + 較高的子樹 */
static int tree_height(const struct tnode *t)
{
    if (t == NULL)
        return 0;
    int lh = tree_height(t->left);
    int rh = tree_height(t->right);
    return 1 + (lh > rh ? lh : rh);
}

static void fill_inorder(const struct tnode *t, int *arr, int *idx)
{
    if (t == NULL)
        return;
    fill_inorder(t->left, arr, idx);
    arr[(*idx)++] = t->key;
    fill_inorder(t->right, arr, idx);
}

/*
 * 從排序陣列 arr[lo..hi] 建完全平衡 BST：
 * 取中點當根，左半、右半遞迴建子樹。
 * 每層節點數減半 -> 高度必為 O(log n)。
 */
static struct tnode *build_balanced(const int *arr, int lo, int hi)
{
    if (lo > hi)
        return NULL;

    int mid = lo + (hi - lo) / 2;       /* 防溢位的中點寫法 */
    struct tnode *t = new_node(arr[mid]);
    t->left  = build_balanced(arr, lo, mid - 1);
    t->right = build_balanced(arr, mid + 1, hi);
    return t;
}

static void tree_free(struct tnode *t)
{
    if (t == NULL)
        return;
    tree_free(t->left);
    tree_free(t->right);
    free(t);
}

/* 平衡：倒出 -> 重建 -> 釋放舊樹 */
static struct tnode *tree_balance(struct tnode *root)
{
    int n = tree_count(root);
    if (n == 0)
        return root;

    int *arr = malloc((size_t)n * sizeof *arr);
    if (arr == NULL) {
        fprintf(stderr, "out of memory\n");
        exit(1);
    }
    int idx = 0;
    fill_inorder(root, arr, &idx);

    struct tnode *balanced = build_balanced(arr, 0, n - 1);

    free(arr);
    tree_free(root);                    /* 舊樹的節點已不再需要 */
    return balanced;
}

static void print_inorder(const struct tnode *t)
{
    if (t == NULL)
        return;
    print_inorder(t->left);
    printf(" %d", t->key);
    print_inorder(t->right);
}

int main(void)
{
    /* 最壞情況：遞增插入 1..15，樹退化成右斜串列 */
    struct tnode *root = NULL;
    for (int k = 1; k <= 15; k++)
        root = insert(root, k);

    printf("insert 1..15 in ascending order (worst case):\n");
    printf("  height before balance = %d  (degenerated to a list)\n",
           tree_height(root));
    printf("  inorder:");
    print_inorder(root);
    printf("\n\n");

    root = tree_balance(root);

    printf("after tree_balance:\n");
    printf("  height after balance  = %d  (perfect: ceil(log2(16)) = 4)\n",
           tree_height(root));
    printf("  inorder:");
    print_inorder(root);
    printf("\n");
    printf("  root=%d, root->left=%d, root->right=%d\n",
           root->key, root->left->key, root->right->key);

    tree_free(root);
    return 0;
}

程式碼講解

build_balanced 是「分治建樹」的原型：基底 lo > hi 回 NULL；mid 當根；兩半遞迴。與 binary search 的索引邏輯完全同構——一個在找、一個在建。
tree_balance 把三個練習串成管線：count（練習 1）→ fill_inorder（練習 3）→ build_balanced（本題核心），資料結構的練習正是這樣層層堆起來的。
tree_free(root) 在回傳新樹之前：舊節點全部釋放，新樹的節點是 build_balanced 新配的——兩棵樹不共享節點，所有權清楚。
輸出驗證三件事：高度（15 → 4）、中序不變（鍵一個不少）、根與兩子的值（8、4、12——中點遞迴的直接證據）。
易錯處一：build_balanced 的基底寫成 lo >= hi—— 漏掉單元素區間，鍵默默消失。
易錯處二：忘記釋放舊樹或舊陣列——本題的記憶體流動（舊樹 → 陣列 → 新樹）每一步都有該釋放的東西。

範例輸出

insert 1..15 in ascending order (worst case):
  height before balance = 15  (degenerated to a list)
  inorder: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

after tree_balance:
  height after balance  = 4  (perfect: ceil(log2(16)) = 4)
  inorder: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
  root=8, root->left=4, root->right=12

常見錯誤解法對照

錯誤寫法	症狀	正解
前序釋放（先 free 再遞迴）	use-after-free	後序釋放（練習 1）
min/max 迴圈條件 `t != NULL`	回傳 NULL 拿不到節點	條件是「還有左/右子」（練習 2）
遞迴填陣列游標用值傳遞	各層互相覆蓋	游標傳指標共享（練習 3）
刪除情況 3 忘刪後繼原節點	同鍵出現兩次	頂替後遞迴刪右子樹（練習 4）
前驅/後繼與刪除方向不配對	BST 性質被破壞	後繼配右子樹刪除（練習 4）
build_balanced 基底 `lo >= hi`	單元素區間遺失	基底 `lo > hi`（練習 5）
平衡後不釋放舊樹	漏一整棵樹	重建後 tree_free 舊樹（練習 5）

練習題與詳解 — 樹

練習 1：tree_count 與 tree_sum（難度：基礎）

題目

解題思路

參考解答

程式碼講解

範例輸出

練習 2：tree_min / tree_max（迭代版）（難度：基礎）

題目

解題思路

參考解答

程式碼講解

範例輸出

練習 3：tree_to_array——中序即排序（難度：進階）

題目

解題思路

參考解答

程式碼講解

範例輸出

練習 4：BST 刪除的三種情況（難度：挑戰）

題目

解題思路

參考解答

程式碼講解

範例輸出

練習 5：tree_balance——重建平衡樹（難度：挑戰）

題目

解題思路

參考解答

程式碼講解

範例輸出

常見錯誤解法對照

相关文章

練習題與詳解 — 單元 01：C 語言入門（Getting Started）

單元 01：C 語言入門（Getting Started）

練習題與詳解 — 單元 02：變數與基本型別（Variables & Types）

單元 02：變數與基本型別（Variables & Types）

練習題與詳解 — 單元 03：運算子與運算式（Operators & Expressions）

單元 03：運算子與運算式（Operators & Expressions）