二叉搜索树 C++ 简单实现：增删查改详解 | 极客日志

C++算法

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

二叉搜索树（BST）是有序查找的基础结构。通过 C++ 演示了 key 与 key_value 两种类型的实现细节，涵盖节点定义、插入、中序遍历、查找及删除操作。重点解析了删除节点时左右子树的处理策略，包括单支树退化风险及平衡性讨论，为理解红黑树等平衡树打下基础。

路由之心发布于 2025/10/8更新于 2026/4/251 浏览

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

什么是二叉搜索树？

二叉搜索树（Binary Search Tree, BST）又称二叉排序树。它或者是一棵空树，或者是具有以下性质的二叉树：

左子树上所有节点的值都小于等于根结点的值；
右子树上所有节点的值都大于等于根结点的值；
它的左右子树也分别为二叉搜索树。

BST Structure

需要注意的是，二叉搜索树中可以支持插入相等的值，也可以不支持，具体取决于使用场景定义。后续学习的 map/set/multimap/multiset 系列容器底层就是基于二叉搜索树的变体，其中 map/set 不支持插入相等值，而 multimap/multiset 支持。

性能分析

在最优情况下，二叉搜索树为完全二叉树（或接近完全二叉树），其高度为 log₂N。最差情况下，二叉搜索树退化为单支树（类似链表），其高度为 N。因此平均时间复杂度为 O(log n)，最差情况为 O(n)。

Performance

虽然二分查找也能实现 O(log₂N) 级别的查找效率，但它有两大缺陷：

需要存储在支持下标随机访问的结构中，并且有序。
插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。

Key 类型二叉搜索树的实现

我们首先从 key 类型入手，这对应于 set/multiset 容器的底层逻辑。集合（Sets）是一种容器，按照特定顺序存储唯一的元素。

节点结构

template<class K> struct BSTNode {
    K _key;
    BSTNode<K>* _left;
    BSTNode<K>* _right;
    
    BSTNode(const K& key = 0) :_key(key), _left(nullptr), _right(nullptr) {}
};

类结构

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

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

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

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->_right) {
                    parent->_right = cur->_left;
                } else {
                    parent->_left = cur->_left;
                }
                delete cur;
            } else {
                // 左右都不为空，找右子树最小值替代
                Node* replaceParent = cur;
                Node* replace = cur->_right;
                while (replace->_left) {
                    replaceParent = replace;
                    replace = replace->_left;
                }
                cur->_key = replace->_key;
                if (replace == replaceParent->_left) {
                    replaceParent->_left = replace->_right;
                } else {
                    replaceParent->_right = replace->_right;
                }
                delete replace;
            }
            return true;
        }
    }
    return false;
}

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() = 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;
}

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

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