二叉查找樹模板：插入、查找、刪除、中序遍歷完整 C++ 實現

節點結構

struct Node {
    Node *left, *right;
    int val;
    Node(int v) : left(nullptr), right(nullptr), val(v) {}
};

核心操作

查找

bool find(Node* p, int v) {
    if (!p) return false;
    if (v == p->val) return true;
    return v < p->val ? find(p->left, v) : find(p->right, v);
}

插入

void insert(Node*& p, int v) {
    if (!p) { p = new Node(v); return; }
    if (v <= p->val) insert(p->left, v);
    else insert(p->right, v);
}

刪除（三種情況）

void remove(Node*& p, int v) {
    if (!p) return;
    if (v == p->val) {
        if (p->left && p->right) {
            // 兩子：找右子樹最小節點替代
            Node* t = p->right;
            while (t->left) t = t->left;
            p->val = t->val;
            remove(p->right, t->val);
        } else {
            // 0或1子：直接替換
            Node* t = p;
            p = p->left ? p->left : p->right;
            delete t;
        }
    } else if (v < p->val) remove(p->left, v);
    else remove(p->right, v);
}

中序遍歷（遞增輸出）

void inorder(Node* p) {
    if (!p) return;
    inorder(p->left);
    cout << p->val << '\n';
    inorder(p->right);
}

測試主程序

支持命令：F(查找)、I(插入)、P(遍歷)、D(刪除)。初始插入 2,3,1 驗證輸出 1,2,3。

擴展方向

此模板可作為 Treap、Splay、AVL 等平衡樹的基礎，後續添加 fix（優先級）、size（子樹大小）、旋轉操作即可。