C++ 实现二叉搜索树：增删查与场景分析

这里要注意，拷贝构造函数中的 Copy 方法需要递归地创建新节点，而不是直接复制指针，否则会导致两个树共享同一块内存，析构时会发生重复释放错误。

Node* Copy(Node* root) {
    if (root == nullptr) return nullptr;
    Node* copy = new Node(root->_key);
    copy->_left = Copy(root->_left);
    copy->_right = Copy(root->_right);
    return copy;
}

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

增删查操作详解

插入操作

插入逻辑相对直观：如果树为空，直接设为根；否则根据大小关系向左或向右走，直到找到空位置插入新节点。

注意：如果不支持插入相等值，遇到相同 key 应返回失败。代码中我们采用迭代方式查找插入位置，同时记录父节点以便连接新节点。

bool Insert(const K& key) {
    if (_root == nullptr) {
        _root = new Node(key);
        return true;
    }

    Node* cur = _root;
    Node* parent = nullptr;
    while (cur) {
        if (cur->_key < key) {
            parent = cur;
            cur = cur->_right;
        } else if (cur->_key > key) {
            parent = cur;
            cur = cur->_left;
        } else {
            return false; // 已存在
        }
    }

    cur = new Node(key);
    if (parent->_key < key)
        parent->_right = cur;
    else
        parent->_left = cur;

    return true;
}

查找操作

利用 BST 的性质，从根节点开始比较：目标值大往右走，小往左走。如果走到空节点还没找到，说明不存在。

bool Find(const K& key) {
    Node* cur = _root;
    while (cur) {
        if (cur->_key < key)
            cur = cur->_right;
        else if (cur->_key > key)
            cur = cur->_left;
        else
            return true;
    }
    return false;
}

删除操作（难点）

删除是最复杂的部分，因为删除后必须保持 BST 的性质。假设要删除节点为 x，分四种情况：

1. 左右孩子均为空：直接删除，父节点对应指针置空。
2. 左空右不空：父节点指向右孩子。
3. 右空左不空：父节点指向左孩子。
4. 左右都不空：这是最棘手的情况。不能直接删除，需要用替换法。通常找右子树的最小节点（或左子树的最大节点）替代 x 的值，然后转为删除那个最小节点（此时该节点最多只有一个孩子，转化为情况 2 或 3）。

实际编码时，我们会先找到待删除节点及其父节点，再根据上述逻辑调整指针。

bool Erase(const K& key) {
    Node* parent = nullptr;
    Node* cur = _root;
    
    while (cur) {
        if (cur->_key < key) {
            parent = cur;
            cur = cur->_right;
        } else if (cur->_key > key) {
            parent = cur;
            cur = cur->_left;
        } else {
            // 找到了，准备删除
            if (cur->_left == nullptr) {
                if (cur == _root)
                    _root = cur->_right;
                else {
                    if (cur == parent->_left)
                        parent->_left = cur->_right;
                    else
                        parent->_right = cur->_right;
                }
                delete cur;
            } else if (cur->_right == nullptr) {
                if (cur == _root)
                    _root = cur->_left;
                else {
                    if (cur == parent->_left)
                        parent->_left = cur->_left;
                    else
                        parent->_right = cur->_left;
                }
                delete cur;
            } else {
                // 两个孩子：找右子树最小节点替代
                Node* pMinRight = cur;
                Node* minRight = cur->_right;
                while (minRight->_left) {
                    pMinRight = minRight;
                    minRight = minRight->_left;
                }
                swap(minRight->_key, cur->_key);
                
                // 现在删除的是 minRight 节点，它最多只有右孩子
                if (pMinRight->_left == minRight)
                    pMinRight->_left = minRight->_right;
                else
                    pMinRight->_right = minRight->_right;
                delete minRight;
            }
            return true;
        }
    }
    return false;
}

中序遍历

利用递归进行中序遍历，可以验证树的有序性。

void InOrder() {
    _InOrder(_root);
    cout << endl;
}

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

Key 与 Key-Value 结构

上面的实现仅存储了 Key。在实际应用中，我们往往需要关联一个值 Value，比如字典查询或词频统计。

Key-Value 实现要点

节点结构增加 V _value 成员。增删查依然以 Key 为准，但允许修改 Value 而不破坏树结构。注意 Erase 时只删除指定 Key 的节点，不影响其他 Value。

template<class K, class V>
struct BSTreeNode {
    BSTreeNode<K, V>* _left;
    BSTreeNode<K, V>* _right;
    K _key;
    V _value;
    // ... 构造函数略
};

典型应用场景

Key 结构场景

1. 车牌识别系统：将合法车牌号存入 BST，车辆进入时扫描比对，快速判断是否放行。
2. 拼写检查：将词典单词存入 BST，读取文章单词时查找是否存在，不在则标红。

Key-Value 结构场景

1. 简易翻译器：Key 存英文，Value 存中文，输入英文即可获取释义。
2. 停车场计费：Key 存车牌，Value 存入场时间。出场时计算时长并扣费。
3. 词频统计：Key 存单词，Value 存出现次数。遍历文章更新计数。

二叉搜索树是数据结构中的基石之一，理解其原理对掌握更复杂的平衡树（如红黑树）至关重要。