查找樹 ADT：二叉查找樹（BST）C 語言完整實現

編輯：關於C語言

BST 定義與性質

對任意節點 X，左子樹所有鍵值 < X.key，右子樹所有鍵值 > X.key。支持 O(h) 查找、插入、刪除（h 為樹高，平均 O(log n)，最壞 O(n)）。

節點結構與類型定義

typedef int ElementType;

struct TreeNode {
    ElementType element;
    struct TreeNode *left;
    struct TreeNode *right;
};
typedef struct TreeNode *SearchTree;
typedef struct TreeNode *Position;

核心操作實現

查找（遞歸/迭代）

Position Find(ElementType X, SearchTree T) {
    if (!T) return NULL;
    if (X < T->element) return Find(X, T->left);
    else if (X > T->element) return Find(X, T->right);
    else return T;
}

Position IterFind(ElementType X, SearchTree T) {
    while (T) {
        if (X < T->element) T = T->left;
        else if (X > T->element) T = T->right;
        else return T;
    }
    return NULL;
}

最小/最大值


Position FindMin(SearchTree T) {
    if (!T) return NULL;
    while (T->left) T = T->left;
    return T;
}

Position FindMax(SearchTree T) {
    if (!T) return NULL;
    while (T->right) T = T->right;
    return T;
}

插入

SearchTree Insert(ElementType X, SearchTree T) {
    if (!T) {
        T = malloc(sizeof(struct TreeNode));
        if (!T) { 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; // 重複值忽略
}

刪除（三種情況）

SearchTree Delete(ElementType X, SearchTree T) {
    Position tmp;
    if (!T) return NULL;

    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) { // 兩個孩子
            tmp = FindMin(T->right);
            T->element = tmp->element;
            T->right = Delete(T->element, T->right);
        } else { // 0 或 1 個孩子
            tmp = T;
            if (!T->left) T = T->right;
            else if (!T->right) T = T->left;
            free(tmp);
        }
    }
    return T;
}

遍歷與應用

void InOrder(SearchTree T) {
    if (T) {
        InOrder(T->left);
        printf("%d ", T->element);
        InOrder(T->right);
    }
}

測試主程序

int main() {
    SearchTree T = NULL;
    int arr[] = {50, 30, 70, 20, 40, 60, 80};
    for (int i = 0; i < 7; i++) T = Insert(arr[i], T);

    printf("In-order: "); InOrder(T); printf("\n"); // 有序輸出

    T = Delete(30, T);
    printf("After delete 30: "); InOrder(T); printf("\n");

    Position p = Find(60, T);
    if (p) printf("Found 60\n");

    return 0;
}