C 語言實現二叉搜索樹（BST）完整操作：創建、查找、插入、刪除、遍歷

前言

二叉搜索樹（BST）是基礎且重要的數據結構，本文提供標準 C 實現，涵蓋節點定義、樹的清空、查找、查找最值、插入、刪除、中序遍歷打印，並通過遞歸方式體現樹操作的優雅本質。

數據結構定義

typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;

struct TreeNode {
    int Element;
    SearchTree Left;
    SearchTree Right;
};

核心操作實現

1. 清空樹（後序遍歷釋放）

SearchTree MakeEmpty(SearchTree T) {
    if (T != NULL) {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }
    return NULL;
}

2. 查找元素

Position Find(int X, SearchTree T) {
    if (T == NULL) return NULL;
    if (X < T->Element)  return Find(X, T->Left);
    else if (X > T->Element) return Find(X, T->Right);
    else return T;  // 找到
}

3. 查找最小/最大值

Position FindMin(SearchTree T) {
    if (T == NULL) return NULL;
    else if (T->Left == NULL) return T;
    else return FindMin(T->Left);
}

Position FindMax(SearchTree T) {
    if (T == NULL) return NULL;
    else if (T->Right == NULL) return T;
    else return FindMax(T->Right);
}

4. 插入元素

SearchTree Insert(int X, SearchTree T) {
    if (T == NULL) {
        T = malloc(sizeof(struct TreeNode));
        if (T == NULL) { fprintf(stderr, "Out of space\\n"); exit(1); }
        T->Element = X;
        T->Left = T->Right = NULL;
    } else if (X < T->Element) {
        T->Left = Insert(X, T->Left);
    } else if (X > T->Element) {
        T->Right = Insert(X, T->Right);
    }
    // 相等不插入（去重）
    return T;
}

5. 刪除元素（三種情況）

SearchTree Delete(int X, SearchTree T) {
    Position TmpCell;
    if (T == NULL) {
        fprintf(stderr, "Element not found\\n");
    } else if (X < T->Element) {
        T->Left = Delete(X, T->Left);
    } else if (X > T->Element) {
        T->Right = Delete(X, T->Right);
    } else {  // 找到目標節點
        if (T->Left && T->Right) {  // 兩個孩子：用右子樹最小值替代
            TmpCell = FindMin(T->Right);
            T->Element = TmpCell->Element;
            T->Right = Delete(T->Element, T->Right);
        } else {  // 0 或 1 個孩子
            TmpCell = T;
            if (T->Left == NULL) T = T->Right;
            else if (T->Right == NULL) T = T->Left;
            free(TmpCell);
        }
    }
    return T;
}

6. 中序遍歷打印（遞增序列）

void ShowTree(SearchTree T) {
    if (T != NULL) {
        ShowTree(T->Left);
        printf("%d ", T->Element);
        ShowTree(T->Right);
    }
}

測試主程序

int main(void) {
    SearchTree tree = NULL;
    tree = Insert(6, tree);
    tree = Insert(2, tree);
    tree = Insert(8, tree);
    tree = Insert(1, tree);
    tree = Insert(5, tree);
    tree = Insert(4, tree);
    tree = Insert(3, tree);

    Delete(3, tree);  // 刪除葉子節點
    // Delete(3, tree); // 再次刪除測試報錯
    // Delete(6, tree); // 刪除根節點(兩孩子)

    ShowTree(tree);  // 輸出: 1 2 4 5 6 8
    printf("\n");
    FindMax(tree);   // 輸出 MAX = 8
    FindMin(tree);   // 輸出 MIN = 1
    return 0;
}

關鍵點總結

• 遞歸本質：所有操作均利用 BST 性質（左<根<右）縮小問題規模，終止條件為 `NULL` 或找到目標。
• 刪除兩孩子節點：採用「右子樹最小值（或左子樹最大值）替代」策略，保持 BST 有序性，再轉為刪除該最小值節點（最多一個孩子）。
• 內存管理：`MakeEmpty` 採用後序釋放，防止野指針；`Insert` 需檢查 `malloc` 失敗。
• 去重策略：插入時遇到相等值不操作，也可改為計數器支持多重集。

擴展方向

BST 退化為鏈表時操作退化為 O(n)。工程中常用 AVL 樹、紅黑樹、Treap 等平衡樹保證 O(log n) 最壞情況，下文將介紹 AVL 樹旋轉實現。