二叉搜尋樹（BST）原理與 C 語言完整實作

為何需要 BST？

有序線性表插入/刪除需移動元素（O(n)），鏈表雖插刪 O(1) 但查找 O(n)。BST 結合兩者優點：查找、插入、刪除平均 O(log n)，最壞 O(n)（退化成鏈表）。

定義

• 左子樹鍵值 < 根節點鍵值
• 右子樹鍵值 > 根節點鍵值
• 左右子樹皆為 BST

核心操作

1. 查找

BiTree SearchBST(BiTree T, int key, BiTree parent, BiTree *found) {
    if (!T) { *found = parent; return NULL; }
    if (key == T->data) { *found = T; return T; }
    return (key < T->data) ? SearchBST(T->lchild, key, T, found)
                           : SearchBST(T->rchild, key, T, found);
}

2. 插入

Status InsertBST(BiTree *T, int key) {
    BiTree parent = NULL, node = NULL;
    if (!SearchBST(*T, key, NULL, &parent)) {      // 未找到
        node = (BiTree)malloc(sizeof(BiTNode));
        node->data = key; node->lchild = node->rchild = NULL;
        if (!parent) *T = node;                    // 空樹
        else if (key < parent->data) parent->lchild = node;
        else parent->rchild = node;
        return OK;
    }
    return ERROR;                                  // 鍵值已存在
}

3. 刪除（三種情況）

1. 葉節點：直接釋放。
2. 單一子樹：以子樹取代。
3. 雙子樹：找中序前驅（左子樹最右節點）或後繼，複製其值，再刪除該前驅/後繼節點。

Status Delete(BiTree *T) {
    BiTree q = *T, s;
    if (!(*T)->lchild) { *T = (*T)->rchild; free(q); }
    else if (!(*T)->rchild) { *T = (*T)->lchild; free(q); }
    else {
        q = *T; s = (*T)->lchild;
        while (s->rchild) { q = s; s = s->rchild; }  // 找前驅
        (*T)->data = s->data;
        (q != *T) ? (q->rchild = s->lchild) : (q->lchild = s->lchild);
        free(s);
    }
    return OK;
}

效能分析與平衡問題

BST 查找效能取決於樹高。若輸入有序，樹退化為右斜樹，查找變 O(n)。解決方案：平衡二叉樹（AVL、紅黑樹），下一回將深入探討。

完整測試主程式

int main() {
    int a[] = {62,88,58,47,35,73,51,99,37,93};
    BiTree T = NULL;
    for (int i=0; i<10; ++i) InsertBST(&T, a[i]);
    DeleteBST(&T, 93); DeleteBST(&T, 47);
    InOrder(T);  // 中序輸出驗證
    return 0;
}

建議設中斷點單步追蹤，觀察指針變化，加深理解。