數據結構：C語言實現二叉搜索樹（BST）完整教學——插入、中序遍歷、查找

二叉搜索樹（BST）定義

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

節點結構

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

核心操作實現

1. 迭代插入（避免遞歸棧溢位）

int bst_insert(BSTree *root, int key) {
    BSTree new_node = malloc(sizeof(BSTNode));
    new_node->key = key;
    new_node->left = new_node->right = NULL;

    if (*root == NULL) {
        *root = new_node;
        return 1;
    }

    BSTree curr = *root, parent = NULL;
    while (curr) {
        if (key == curr->key) { free(new_node); return 0; }  // 重複
        parent = curr;
        curr = (key < curr->key) ? curr->left : curr->right;
    }

    if (key < parent->key) parent->left = new_node;
    else parent->right = new_node;
    return 1;
}

2. 交互式建樹

void bst_create(BSTree *root) {
    *root = NULL;
    int key;
    printf("輸入鍵值 (-1 結束): ");
    while (scanf("%d", &key) == 1 && key != -1) {
        bst_insert(root, key);
    }
}

3. 中序遍歷（遞歸）

void bst_inorder(BSTree root) {
    if (root) {
        bst_inorder(root->left);
        printf("%d ", root->key);
        bst_inorder(root->right);
    }
}

4. 迭代查找

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

完整測試程式

int main() {
    BSTree root = NULL;
    int choice, key;

    printf("=== 建立二叉搜索樹 ===\n");
    bst_create(&root);

    printf("\n中序遍歷 (有序): ");
    bst_inorder(root);
    printf("\n");

    while (1) {
        printf("\n輸入查找鍵值 (0 退出): ");
        scanf("%d", &key);
        if (key == 0) break;

        BSTree found = bst_search(root, key);
        if (found) printf("找到: %d\n", found->key);
        else printf("不存在\n");
    }

    // 銷毀樹（後序釋放）
    void destroy(BSTree r) {
        if (r) { destroy(r->left); destroy(r->right); free(r); }
    }
    destroy(root);
    return 0;
}

運行示例

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

關鍵複雜度分析

| 操作 | 平均情況 | 最壞情況 (退化為鏈表) | |------|----------|------------------------| | 查找 | O(log n) | O(n) | | 插入 | O(log n) | O(n) | | 刪除 | O(log n) | O(n) | | 遍歷 | O(n) | O(n) |

常見問題與優化

1. 退化為鏈表：有序輸入導致樹高 O(n) → 使用 AVL/紅黑樹 自平衡
2. 遞歸棧溢位：深度過大時遞歸遍歷/插入崩潰 → 改用迭代版本（本文插入/查找均為迭代）
3. 重複鍵值處理：忽略/計數/存儲列表，視業務而定
4. 記憶體碎片：頻繁 malloc/free → 考慮內存池分配節點

擴展練習

• 實現刪除節點（三種情況：葉子、單子、雙子找前驅/後繼）
• 實現非遞歸中序遍歷（顯式棧模擬）
• 實現第 k 小元素查找（節點維護子樹大小 `size`）
• 實現區間查詢（輸出 [L, R] 內所有鍵值）

總結

二叉搜索樹是動態有序集合的基石數據結構。本文提供了迭代插入、中序遍歷、迭代查找、交互式建樹、記憶體銷毀完整工程級代碼模板。掌握 BST 核心不變量（左 < 根 < 右）與中序遍歷有序性，是理解所有進階搜索樹（AVL、紅黑、B樹、Treap、Splay）的前提。