前言
本文从零开始实现一棵 C++ 二叉搜索树(BST):先定义节点结构,再实现核心的插入、查找与中序遍历,最后详细讲解删除操作(涵盖叶子节点、单子节点与双子节点三种情况)。通过完整代码与逻辑梳理,帮助读者深入理解二叉搜索树的底层原理。
1. 什么是二叉搜索树?
二叉搜索树(Binary Search Tree, BST)又称二叉排序树。它或者是一棵空树,或者是具有以下性质的二叉树:
- 左子树上所有节点的值均小于等于根节点的值;
- 右子树上所有节点的值均大于等于根节点的值;
- 它的左右子树也分别为二叉搜索树。
注意:二叉搜索树是否支持插入相等的值取决于具体使用场景。例如,标准库中的
std::set/std::map不允许重复键,而std::multiset/std::multimap则允许。
2. 二叉搜索树性能分析
- 最优情况:树为完全二叉树(或接近完全二叉树),高度为 $O(\log_2 N)$。
- 最差情况:树退化为单支树(类似链表),高度为 $O(N)$。
- 平均时间复杂度:查找、插入、删除的平均时间复杂度为 $O(\log N)$,最差为 $O(N)$。
说明:虽然二分查找也能达到 $O(\log N)$ 的查找效率,但存在两大局限:
- 数据必须存储在支持下标随机访问的连续结构中,且保持有序。
- 插入和删除操作效率低下,通常需要移动大量元素。
3. Key 类型二叉搜索树的实现
本节实现仅存储键值(Key)的二叉搜索树,对应标准库中 set 容器的底层逻辑(默认元素唯一)。
节点结构
template<class K>
struct BSTNode {
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
BSTNode(const K& key = K())
: _key(key), _left(nullptr), _right(nullptr) {}
};
类结构
template<class K>
class BSTree {
using Node = BSTNode<K>;
public:
// 接口声明...
private:
Node* _root = nullptr;
};
3.1 插入
:


