二叉排序樹（BST）構建、插入與刪除操作完整實現

節點結構

struct LNode {
    int data;
    LNode *lchild, *rchild;
};

插入操作

void buildtree(LNode *root, LNode *q) {
    LNode *p = root;
    while (1) {
        if (q->data == p->data) break;  // 忽略重複值
        if (q->data > p->data) {
            if (p->rchild) p = p->rchild;
            else { p->rchild = q; break; }
        } else {
            if (p->lchild) p = p->lchild;
            else { p->lchild = q; break; }
        }
    }
}

刪除操作（三種情況）

void del(LNode *root, LNode *q) {
    LNode *p = root, *r = nullptr;  // r 為 p 的父節點
    while (1) {
        if (p->data == q->data) {
            // 1. 葉子節點
            if (!p->lchild && !p->rchild) {
                (r->lchild == p) ? r->lchild = nullptr : r->rchild = nullptr;
                delete p; break;
            }
            // 2. 單右子
            if (!p->lchild && p->rchild) {
                (r->lchild == p) ? r->lchild = p->rchild : r->rchild = p->rchild;
                delete p; break;
            }
            // 3. 單左子
            if (p->lchild && !p->rchild) {
                (r->lchild == p) ? r->lchild = p->lchild : r->rchild = p->lchild;
                delete p; break;
            }
            // 4. 雙子節點：用前驅（左子樹最大）或後繼（右子樹最小）替代
            if (p->lchild && p->rchild) {
                LNode *s = p->lchild;
                while (s->rchild) s = s->rchild;  // 找前驅
                p->data = s->data;
                delete s; break;
            }
        }
        r = p;
        p = (q->data < p->data) ? p->lchild : p->rchild;
    }
}

中序遍歷驗證

void inorder(LNode *root) {
    if (root) { inorder(root->lchild); cout<data<<" "; inorder(root->rchild); }
}

本文出自「菜鳥的進階之路」博客，轉載請保留出處：原文鏈接