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

插入操作

思路很简单：

1. 树为空，直接新增结点，赋值给 root 指针。
2. 树不空，按二叉搜索树性质，用 cur 指针遍历，parent 指针记下父亲节点。要插入值 key 比当前节点大往右走，小往左走，直到找到空位置插入新结点。
3. 确定新节点插在 parent 的左边还是右边。

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 {
            return false; // 不允许重复
        }
    }
    if (key < parent->_key) {
        parent->_left = node;
    } else {
        parent->_right = node;
    }
    return true;
}

中序遍历

根据二叉搜索树的特性，其中序遍历的结果恰好为一个有序序列（升序）。由于 _root 是成员变量，在类外面调用无法直接传参，所以采用内部递归辅助函数的形式。

void MidOrder() { _MidOrder(_root); }

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

查找

从根开始比较，val 比根大则往右找，小则往左找。最多查找高度次，走到空还没找到就返回 false。

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;
}

删除操作

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

1. 左为空：将父节点的指针指向该节点的右孩子。
2. 右为空：将父节点的指针指向该节点的左孩子。
3. 左右都不为空：无法直接删除，只能用替换法。找左子树最大值（最右结点）或右子树最小值（最左结点）替代被删节点，交换值后转为删除那个替代节点（此时替代节点必属于情况 1 或 2）。

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 {
            // 左为空
            if (cur->_left == nullptr) {
                if (cur == _root) _root = _root->_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 = _root->_left;
                else if (cur == parent->_left) parent->_left = cur->_left;
                else parent->_right = cur->_left;
                delete cur;
            }
            // 左右均不为空
            else {
                Node* replaceParent = cur;
                Node* replace = cur->_right;
                // 找右子树中最小值的节点 R
                while (replace->_left) {
                    replaceParent = replace;
                    replace = replace->_left;
                }
                cur->_key = replace->_key;
                if (replace == replaceParent->_left) {
                    replaceParent->_left = replace->_right;
                } else {
                    cur->_right = replace->_right;
                }
                delete replace;
            }
            return true;
        }
    }
    return false;
}

Key_Value 类型二叉搜索树的实现

对于 std::map/std::multimap 容器，映射是一种关联容器，它按照特定顺序存储由'键值（key value）'和'映射值（mapped value）'组合而成的元素。

与 Key 类型相比，只是多了个 _value。除了插入操作外，其他操作基本相同，重点补充构造、析构等生命周期管理。

节点与类结构

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;
};

构造函数与拷贝构造

C++11 强制生成默认构造，拷贝构造需要深拷贝。

// 默认构造
BSTree() = default;

// 拷贝构造（深拷贝）
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;
}

赋值重载

现代写法利用 swap 实现自我赋值安全及资源转移。

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

析构函数

后序遍历释放内存，防止根结点被释放而找不到左右孩子节点。

~BSTree() {
    Destory(_root);
    _root = nullptr;
}
void Destory(Node* root) {
    if (root == nullptr) return;
    Destory(root->_left);
    Destory(root->_right);
    delete root;
}

插入

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;
}

总结

本文简单实现了二叉搜索树的基础版本。它与 set/multiset/map/multimap 底层的数据结构——平衡二叉搜索树有所不同，并没有过多关注底层实现细节，比如 insert、Find 返回值等。目的是为了能够加深大家对二叉搜索树的理解，方便后续对平衡二叉树的学习。