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

編輯：關於C語言

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

BST 定義與性質

左子樹鍵值 < 根節點鍵值
右子樹鍵值 > 根節點鍵值
左右子樹皆為 BST
中序遍歷 = 遞增有序序列（驗證樹正確性的關鍵）

節點結構

typedef int ElemType;
typedef struct BTNode {
    ElemType data;
    struct BTNode *lChild, *rChild;
} BiTNode, *BiTree;

核心操作實現

1. 插入節點（遞歸）


void Insert(BiTree *T, int x) {
    if (*T == NULL) {
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = x;
        (*T)->lChild = (*T)->rChild = NULL;
        return;
    }
    if (x < (*T)->data) Insert(&(*T)->lChild, x);
    else if (x > (*T)->data) Insert(&(*T)->rChild, x);
    // 相等值不插入（或按需求處理）
}

2. 遍歷驗證


void InOrder(BiTree T) {  // 中序：遞增
    if (!T) return;
    InOrder(T->lChild);
    printf("%d ", T->data);
    InOrder(T->rChild);
}
void PreOrder(BiTree T) { // 先序：根左右
    if (!T) return;
    printf("%d ", T->data);
    PreOrder(T->lChild);
    PreOrder(T->rChild);
}

3. 查找（遞歸/迭代）


BiTree Search(BiTree T, int x) {
    while (T) {
        if (x < T->data) T = T->lChild;
        else if (x > T->data) T = T->rChild;
        else return T;
    }
    return NULL;
}

4. 刪除節點（三種情況）


BiTree Delete(BiTree *T, int x) {
    if (!*T) return NULL;
    BiTree p = *T, parent = NULL;
    // 1. 定位節點及其父節點
    while (p && p->data != x) {
        parent = p;
        p = (x < p->data) ? p->lChild : p->rChild;
    }
    if (!p) return *T; // 不存在

    // 情況 A：葉子節點
    if (!p->lChild && !p->rChild) {
        if (parent) {
            if (parent->lChild == p) parent->lChild = NULL;
            else parent->rChild = NULL;
        } else *T = NULL; // 刪根
        free(p);
    }
    // 情況 B：單子樹
    else if (!p->lChild || !p->rChild) {
        BiTree child = p->lChild ? p->lChild : p->rChild;
        if (parent) {
            if (parent->lChild == p) parent->lChild = child;
            else parent->rChild = child;
        } else *T = child;
        free(p);
    }
    // 情況 C：雙子樹 → 找後繼（右子樹最小）
    else {
        BiTree succ = p->rChild, succParent = p;
        while (succ->lChild) { succParent = succ; succ = succ->lChild; }
        p->data = succ->data; // 複製值
        // 刪除後繼（後繼無左子樹，歸歸為情況 A/B）
        if (succParent->lChild == succ) succParent->lChild = succ->rChild;
        else succParent->rChild = succ->rChild;
        free(succ);
    }
    return *T;
}

主程式測試


int main() {
    BiTree root = NULL;
    int vals[] = {50, 30, 70, 20, 40, 60, 80};
    for (int v : vals) Insert(&root, v);

    printf("InOrder:  "); InOrder(root);  puts("");
    printf("PreOrder: "); PreOrder(root); puts("");

    printf("Search 40: %p\n", Search(root, 40));
    Delete(&root, 30);
    printf("After del 30 InOrder: "); InOrder(root); puts("");
    return 0;
}