C語言從零實現二叉搜索樹（BST）：節點定義、插入、遍歷、銷毀完整教學

二叉搜索樹（BST）核心性質

• 左子樹所有鍵值 < 根節點鍵值
• 右子樹所有鍵值 > 根節點鍵值
• 左右子樹皆為 BST
• 中序遍歷產生遞增序列

節點結構與類型別名

typedef struct BSTNode {
    int data;
    struct BSTNode *left;
    struct BSTNode *right;
} BSTNode, *BSTree;

遞歸結構體定義，`typedef` 簡化指針聲明。

核心操作實現

1. 插入（遞歸版）

void bst_insert(BSTree *root, int val) {
    if (*root == NULL) {
        *root = (BSTree)malloc(sizeof(BSTNode));
        (*root)->data = val;
        (*root)->left = (*root)->right = NULL;
        return;
    }
    if (val < (*root)->data) {
        bst_insert(&(*root)->left, val);
    } else if (val > (*root)->data) {
        bst_insert(&(*root)->right, val);
    }
    // 相等值不插入（集合語義，唯一性）
}

關鍵點：傳遞指針的指針（`BSTree *`），以便修改呼叫者的指針變數（根節點或子樹指針）。

2. 三種深度優先遍歷

// 前序：根 → 左 → 右
void preorder(BSTree root) {
    if (root) {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

// 中序：左 → 根 → 右（產生有序序列）
void inorder(BSTree root) {
    if (root) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

// 後序：左 → 右 → 根（適用於銷毀、釋放）
void postorder(BSTree root) {
    if (root) {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->data);
    }
}

3. 遞歸銷毀（後序釋放）

void bst_destroy(BSTree root) {
    if (root) {
        bst_destroy(root->left);
        bst_destroy(root->right);
        free(root);
    }
}

必須後序：先釋放子樹，再釋放根，避免野指針。

4. 查找（迭代版，效率更高）

BSTree bst_search(BSTree root, int key) {
    while (root) {
        if (key == root->data) return root;
        root = (key < root->data) ? root->left : root->right;
    }
    return NULL;
}

完整測試程式

int main() {
    BSTree root = NULL;
    int keys[] = {9, 4, 15, 6, 12, 17, 2};
    int n = sizeof(keys) / sizeof(keys[0]);

    for (int i = 0; i < n; i++) bst_insert(&root, keys[i]);

    printf("前序: "); preorder(root);  printf("\n");
    printf("中序: "); inorder(root);   printf("\n");
    printf("後序: "); postorder(root); printf("\n");

    // 查找測試
    int target = 12;
    BSTree found = bst_search(root, target);
    printf("查找 %d: %s\n", target, found ? "存在" : "不存在");

    bst_destroy(root);
    return 0;
}

運行結果

前序: 9 4 2 6 15 12 17
中序: 2 4 6 9 12 15 17
後序: 2 6 4 12 17 15 9
查找 12: 存在

樹形結構視覺化

        9
       / \
      4   15
     / \  / \
    2  6 12 17

關鍵教學點總結

| 概念 | 關鍵代碼模式 | 易錯點 | |------|--------------|--------| | 遞歸插入 | `bst_insert(&(*root)->left, val)` | 忘記 `&` 導致無法修改父節點指針 | | 遍歷順序 | 三種 `printf` 位置差異 | 混淆前/中/後序輸出位置 | | 記憶體釋放 | 後序 `free(root)` | 先 `free(root)` 再遞歸 → 野指針 | | 唯一性 | `val == root->data` 不插入 | 允許重複值導致樹退化為鏈表 |

擴展練習建議

1. 刪除節點：三種情況（葉子、單子、雙子），雙子需找前驅/後繼替換
2. 非遞歸插入/查找：用 `while` 循環 + 父節點指針
3. 樹高計算：`max(height(left), height(right)) + 1`
4. 第 k 小元素：中序遍歷計數器
5. 平衡化（AVL/紅黑）：引入平衡因子與旋轉操作

為什麼需要樹形結構？

作者文末提出經典問題：統計 C 關鍵字在代碼中出現頻率。若用線性結構（數組/鏈表），查找/插入均為 O(n)；BST 平均 O(log n)，大規模關鍵字統計效能差異巨大。這正是「選擇正確資料結構」的核心動機。