C++ 二叉搜索树详解：概念、操作与递归实现

3. 插入操作

需保证树不空时按性质寻找位置，且不允许重复值。

bool insert(const T& val) {
    if (_root == nullptr) { _root = new Node(val); return true; }
    Node* cur = _root;
    Node* parent = nullptr;
    while (cur != nullptr) {
        if (cur->_key > val) { parent = cur; cur = cur->_left; }
        else if (cur->_key < val) { parent = cur; cur = cur->_right; }
        else return false; // 已存在
    }
    Node* newNode = new Node(val);
    if (parent->_key < val) parent->_right = newNode;
    else parent->_left = newNode;
    return true;
}

4. 删除操作（难点）

删除后必须维持 BST 性质。分三种情况：无孩子、单孩子、双孩子。双孩子时通常用'左子树最大值'或'右子树最小值'替换待删节点值，再删除该替换节点。

bool erase(const T& val) {
    Node* cur = _root;
    Node* parent = nullptr;
    while (cur != nullptr) {
        if (cur->_key > val) { parent = cur; cur = cur->_left; }
        else if (cur->_key < val) { parent = cur; cur = cur->_right; }
        else {
            // 情况 1：无左孩子
            if (cur->_left == nullptr) {
                if (parent == nullptr) _root = cur->_right;
                else if (parent->_left == cur) parent->_left = cur->_right;
                else parent->_right = cur->_right;
            }
            // 情况 2：无右孩子
            else if (cur->_right == nullptr) {
                if (parent == nullptr) _root = cur->_left;
                else if (parent->_left == cur) parent->_left = cur->_left;
                else parent->_right = cur->_left;
            }
            // 情况 3：有左右孩子
            else {
                Node* lmaxp = cur;
                Node* lmax = cur->_left;
                while (lmax->_right != nullptr) {
                    lmaxp = lmax;
                    lmax = lmax->_right;
                }
                swap(cur->_key, lmax->_key);
                cur = lmax; // 准备删除 lmax
            }
            delete cur;
            return true;
        }
    }
    return false;
}

测试时可配合中序遍历验证有序性。

四、递归实现

递归写法更简洁，但需注意指针引用传递。

bool _findR(Node* root, const T& key) {
    if (!root) return false;
    if (root->_key < key) return _findR(root->_right, key);
    else if (root->_key > key) return _findR(root->_left, key);
    else return true;
}

关于 Node*& root 的思考： 递归修改树结构时，参数必须是引用。否则函数内修改的是局部副本，无法更新父节点的指针域，导致树结构断裂或内存泄漏。

bool _insertR(Node*& root, const T& key) {
    if (!root) { root = new Node(key); return true; }
    if (root->_key < key) return _insertR(root->_right, key);
    else if (root->_key > key) return _insertR(root->_left, key);
    else return false;
}

删除同理，递归版本同样需要处理替换逻辑。

五、完善类成员

遵循 Rule of Three，需实现拷贝构造、赋值运算符和析构函数。

// 拷贝构造
BSTree(const BSTree<T>& t) { _root = Copy(t._root); }
Node* Copy(Node* root) {
    if (!root) return nullptr;
    Node* copyRoot = new Node(root->_key);
    copyRoot->_left = Copy(root->_left);
    copyRoot->_right = Copy(root->_right);
    return copyRoot;
}

// 赋值运算符重载
BSTree<T>& operator=(BSTree<T> t) {
    swap(_root, t._root);
    return *this;
}

// 析构函数
~BSTree() { Destroy(_root); }
void Destroy(Node*& root) {
    if (!root) return;
    Destroy(root->_left);
    Destroy(root->_right);
    delete root;
    root = nullptr;
}

至此，一个完整的二叉搜索树模板类基本成型。实际开发中可根据需求进一步优化平衡性（如 AVL 树或红黑树）。