C++ 二叉搜索树基础实现：增删查改详解

说明：以下实现默认假设不支持插入相等值，若需支持，只需调整插入时的比较逻辑即可。

插入操作

思路很直观：

1. 树为空，直接创建新节点作为根。
2. 树不空，从根开始遍历。若待插入值小于当前节点，往左走；大于则往右走。
3. 找到空位置时，将新节点挂到父节点的左侧或右侧。

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

    Node* parent = nullptr;
    Node* cur = _root;

    while (cur) {
        if (key < cur->_key) {
            parent = cur;
            cur = cur->_left;
        } else if (key > cur->_key) {
            parent = cur;
            cur = cur->_right;
        } else {
            // 已存在，根据需求决定是否返回 false
            delete node;
            return false;
        }
    }

    if (key < parent->_key) {
        parent->_left = node;
    } else {
        parent->_right = node;
    }
    return true;
}

中序遍历

BST 的中序遍历结果是一个升序序列，这是验证树结构正确性的好方法。

void MidOrder() {
    _MidOrder(_root);
}

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

查找

查找逻辑与插入类似，沿着路径向下比较即可。

bool 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 {
            return true;
        }
    }
    return false;
}

删除操作

删除是 BST 中最复杂的部分，主要分三种情况处理：

1. 左孩子为空：用右孩子替代当前节点。
2. 右孩子为空：用左孩子替代当前节点。
3. 左右孩子均不为空：找到左子树的最大值（最右节点）或右子树的最小值（最左节点）替换当前节点的值，然后递归删除那个被替换的节点。

bool Erase(const K& val) {
    Node* cur = _root;
    Node* parent = nullptr;

    while (cur) {
        if (val < cur->_key) {
            parent = cur;
            cur = cur->_left;
        } else if (val > cur->_key) {
            parent = cur;
            cur = cur->_right;
        } else {
            // 找到目标节点
            // 情况 1：左为空
            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;
            }
            // 情况 2：右为空
            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;
            }
            // 情况 3：左右都不为空
            else {
                Node* replaceParent = cur;
                Node* replace = cur->_right;
                // 找右子树中最小值的节点 R
                while (replace->_left) {
                    replaceParent = replace;
                    replace = replace->_left;
                }
                // 交换值
                cur->_key = replace->_key;
                // 删除 R 节点（此时 R 最多只有右孩子）
                if (replace == replaceParent->_left) {
                    replaceParent->_left = replace->_right;
                } else {
                    replaceParent->_right = replace->_right;
                }
                delete replace;
            }
            return true;
        }
    }
    return false;
}

Key_Value 类型二叉搜索树的实现

对于 std::map/std::multimap，我们需要存储键值对。核心逻辑与 Key 类型一致，主要区别在于构造函数、拷贝构造及析构等生命周期管理。

节点与类结构

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

    BSTNode(const K& key = 0, const V& value = 0)
        :_key(key), _value(value), _left(nullptr), _right(nullptr) {}
};

template<class K, class V>
class BSTree {
    using Node = BSTNode<K, V>;
public:
    // ...
private:
    Node* _root = nullptr;
};

特殊成员函数

拷贝构造（深拷贝）

BSTree(const BSTree& tree) {
    _root = copy(tree._root);
}

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

赋值重载

BSTree& operator=(BSTree tree) {
    swap(_root, tree._root);
    return *this;
}

析构

~BSTree() {
    Destroy(_root);
    _root = nullptr;
}

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

插入

逻辑与 Key 类型基本相同，只是多传一个 Value。

bool Insert(const K& key, const V& value) {
    Node* node = new Node(key, value);
    if (_root == nullptr) {
        _root = node;
        return true;
    }
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur) {
        if (key < cur->_key) {
            parent = cur;
            cur = cur->_left;
        } else if (key > cur->_key) {
            parent = cur;
            cur = cur->_right;
        } else {
            return false;
        }
    }
    if (key < parent->_key) {
        parent->_left = node;
    } else {
        parent->_right = node;
    }
    return true;
}

总结

本文详细演示了二叉搜索树的基础版本实现。通过对比 Key 与 Key-Value 两种模式，展示了泛型编程在数据结构中的应用。重点剖析了删除节点时的复杂分支处理，特别是双孩子节点时的替换策略。理解这些基础操作，有助于后续深入学习红黑树等平衡二叉搜索树的底层机制。