C++ 二叉搜索树：原理与增删查实现详解

3. 删除操作

删除是 BST 中最复杂的部分，因为删除后必须保证树的性质不被破坏。我们需要分三种情况讨论：

情况一：待删除节点是叶子节点（无孩子）

直接删除即可，不影响其他节点。

情况二：待删除节点只有一个孩子

用唯一的子节点替换待删除节点的位置，相当于把子节点'提上来'。

情况三：待删除节点有两个孩子

这是难点。不能直接删除，否则左右子树无法连接。策略是：找替代者。

通常选择右子树的最小节点（即右子树的最左下节点）或者左子树的最大节点来覆盖待删除节点的值，然后删除那个替代节点。这样既保持了有序性，又避免了复杂的指针重连。

以选择右子树最小节点为例：

1. 找到右子树的最小节点 rightMin。
2. 将 rightMin 的值复制到待删除节点。
3. 删除 rightMin 节点（此时 rightMin 最多只有一个右孩子，简化了删除逻辑）。

bool erase(const K& val) {
    if (_root == nullptr) return false;

    Node* cur = _root;
    Node* curPre = nullptr;

    // 1. 查找待删除节点
    while (cur) {
        if (val < cur->_key) {
            curPre = cur;
            cur = cur->_left;
        } else if (val > cur->_key) {
            curPre = cur;
            cur = cur->_right;
        } else {
            break;
        }
    }

    if (cur == nullptr) return false; // 未找到

    // 2. 处理删除逻辑
    // 情况 A: 0 个或 1 个孩子
    if (cur->_left == nullptr || cur->_right == nullptr) {
        Node* curNext = cur->_left ? cur->_left : cur->_right;

        if (cur != _root) {
            if (curPre->_left == cur)
                curPre->_left = curNext;
            else
                curPre->_right = curNext;
        } else {
            _root = curNext; // 删除的是根节点
        }
        delete cur;
    }
    // 情况 B: 2 个孩子
    else {
        // 找右子树最小节点
        Node* rightMin = cur->_right;
        Node* rightMinPre = cur;
        while (rightMin->_left) {
            rightMinPre = rightMin;
            rightMin = rightMin->_left;
        }

        // 值覆盖
        cur->_key = rightMin->_key;

        // 删除 rightMin 节点（此时 rightMin 最多只有右孩子）
        Node* rightMinNext = rightMin->_right;
        if (rightMinPre->_left == rightMin)
            rightMinPre->_left = rightMinNext;
        else
            rightMinPre->_right = rightMinNext;

        delete rightMin;
    }

    return true;
}

完整代码实现

下面是整合后的完整类定义及测试用例，包含了析构函数和中序遍历打印功能，方便验证结果。

#pragma once
#include <iostream>
#include <vector>
using namespace std;

template<class K>
struct BSTNode {
    BSTNode<K>* _left;
    BSTNode<K>* _right;
    K _key;

    BSTNode(const K& val) : _left(nullptr), _right(nullptr), _key(val) {}
};

template<class K>
class BSTree {
public:
    typedef BSTNode<K> Node;

    BSTree() : _root(nullptr) {}

    ~BSTree() {
        destroy(_root);
    }

    Node* find(const K& val) {
        Node* cur = _root;
        while (cur) {
            if (val < cur->_key) cur = cur->_left;
            else if (val > cur->_key) cur = cur->_right;
            else break;
        }
        return cur;
    }

    bool insert(const K& val) {
        if (_root == nullptr) {
            _root = new Node(val);
            return true;
        }
        Node* cur = _root;
        Node* curPre = nullptr;
        while (cur) {
            if (val == cur->_key) return false;
            else if (val < cur->_key) {
                curPre = cur;
                cur = cur->_left;
            } else {
                curPre = cur;
                cur = cur->_right;
            }
        }
        if (curPre->_key > val)
            curPre->_left = new Node(val);
        else
            curPre->_right = new Node(val);
        return true;
    }

    bool erase(const K& val) {
        if (_root == nullptr) return false;
        Node* cur = _root;
        Node* curPre = nullptr;
        while (cur) {
            if (val < cur->_key) { curPre = cur; cur = cur->_left; }
            else if (val > cur->_key) { curPre = cur; cur = cur->_right; }
            else break;
        }
        if (cur == nullptr) return false;

        if (cur->_left == nullptr || cur->_right == nullptr) {
            Node* curNext = cur->_left ? cur->_left : cur->_right;
            if (cur != _root) {
                if (curPre->_left == cur) curPre->_left = curNext;
                else curPre->_right = curNext;
            } else {
                _root = curNext;
            }
            delete cur;
        } else {
            Node* rightMin = cur->_right;
            Node* rightMinPre = cur;
            while (rightMin->_left) {
                rightMinPre = rightMin;
                rightMin = rightMin->_left;
            }
            cur->_key = rightMin->_key;
            Node* rightMinNext = rightMin->_right;
            if (rightMinPre->_left == rightMin) rightMinPre->_left = rightMinNext;
            else rightMinPre->_right = rightMinNext;
            delete rightMin;
        }
        return true;
    }

    void inOrder() {
        _inOrder(_root);
        cout << endl;
    }

private:
    Node* _root;

    void destroy(Node* root) {
        if (root == nullptr) return;
        destroy(root->_left);
        destroy(root->_right);
        delete root;
    }

    void _inOrder(Node* root) {
        if (root == nullptr) return;
        _inOrder(root->_left);
        cout << root->_key << " ";
        _inOrder(root->_right);
    }
};

void testBST() {
    BSTree<int> bst;
    vector<int> arr = {8, 3, 10, 1, 6, 14, 5, 7, 13};
    cout << "=== 创建二叉搜索树 ===\n";
    for (const auto& e : arr) bst.insert(e);
    cout << "中序遍历结果：";
    bst.inOrder();

    cout << "=== 查找数据 ===\n";
    cout << "查找 14: " << (bst.find(14) ? "存在" : "不存在") << endl;
    cout << "查找 28: " << (bst.find(28) ? "存在" : "不存在") << endl;

    cout << "=== 删除数据 ===\n";
    cout << "删除前：";
    bst.inOrder();
    bst.erase(6); // 双子节点
    cout << "删除 6 后：";
    bst.inOrder();
    bst.erase(1); // 叶子节点
    cout << "删除 1 后：";
    bst.inOrder();
}

典型应用场景

理解了增删查，我们来看看 BST 在实际中能做什么。

1. K 模型（Key Model）

只存储 Key，用于判断某个元素是否存在。

• 词库校验：将字典里的单词作为 Key 存入 BST，输入单词时查询是否存在，快速判断拼写错误。
• 门禁系统：记录授权人员 ID，判断是否在名单内。

2. KV 模型（Key-Value Model）

每个 Key 对应一个 Value，形成键值对。

• 英汉词典：Key 是英文单词，Value 是中文释义。
• 频率统计：Key 是单词，Value 是出现次数。遍历文本时，若 Key 存在则 Value+1，否则插入并置为 1。

// KV 模型示例：统计单词频率
template<class K, class V>
struct BSTNodeKV {
    K _key;
    V _value;
    BSTNodeKV<K, V>* _left;
    BSTNodeKV<K, V>* _right;
    BSTNodeKV(const K& k, const V& v) : _key(k), _value(v), _left(nullptr), _right(nullptr) {}
};

// 使用逻辑类似，只需在节点中增加 value 字段，并在插入/更新时处理 value 的增减

总结

二叉搜索树通过简单的规则实现了高效的查找能力。只要记住三个关键点：

1. 有序性：左 < 根 < 右。
2. 删除策略：双子节点时，用后继（右子树最小）或前驱（左子树最大）替换。
3. 性能瓶颈：数据有序会导致退化，实际工程中常配合平衡机制使用。

掌握了 BST，你就迈进了高级数据结构的大门，后续的 AVL 树和红黑树本质上都是在解决 BST 不平衡的问题。