二叉搜索樹C語言實現：創建、查找、插入、刪除、遍歷與極值查找

編輯：關於C語言

BST 性質與節點定義

左子樹鍵值 < 根節點 < 右子樹鍵值。遞歸結構天然適合遞歸操作。


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));
        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) {
        printf("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; // 原代碼此處重複判斷 Left==NULL，已修正
            free(TmpCell);
        }
    }
    return T;
}

原代碼 Bug 修正：單孩子分支中 else if (T->Left == NULL) 重複，第二個應為 T->Right == NULL (或直接 else)。

6. 中序遍歷打印 (有序輸出)


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

測試驅動


int main() {
    SearchTree T = NULL;
    T = Insert(6, T); T = Insert(2, T); T = Insert(8, T);
    T = Insert(1, T); T = Insert(5, T); T = Insert(4, T); T = Insert(3, T);
    // 樹結構:
    //       6
    //     /   \
    //    2     8
    //   / \
    //  1   5
    //     /
    //    4
    //   /
    //  3

    Delete(3, T); // 刪除葉子 3
    ShowTree(T);  // 輸出: 1 2 4 5 6 8
    printf("\n");
    FindMax(T);   // 8
    FindMin(T);   // 1
    MakeEmpty(T); // 釋放內存
    return 0;
}