C++ 二叉搜索树（BST）是一种左子节点值小于根节点、右子节点值大于根节点的二叉树结构。详细阐述了 BST 的定义、性能分析及其在 C++ 中的具体实现。内容涵盖 Key 类型与 Key_Value 类型的节点结构设计，包括默认构造、拷贝构造、析构及赋值重载等基础操作。核心功能实现了插入、中序遍历、查找以及复杂的删除逻辑（处理叶子节点、单孩子节点和双孩子节点）。通过代码示例展示了如何构建平衡性未保证的 BST，为理解红黑树等平衡树容器底层机制奠定基础。
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
• 左子树上所有节点的值都小于等于根结点的值； • 右子树上所有节点的值都大于等于根结点的值； • 它的左右子树也分别为二叉搜索树
***注意：***二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义。后续学习 map/set/multimap/multiset 系列容器底层就是二叉搜索树，其中 map/set 不支持插入相等值，multimap/multiset 支持插入相等值。
在最优情况下，二叉搜索树为完全二叉树 (或者接近完全二叉树)，其高度为：log2 N
最差情况下，二叉搜索树退化为单支树 (或者类似单支)，其高度为：N
所以平均时间的时间复杂度为 O(log n)，最差情况为 O(n)。
**说明：虽然二分查找也可以实现 O(log2 N) 级别的查找效率，但是二分查找有两大缺陷：
为什么是 key 类型二叉搜索树呢？因为我们后面要讲的 set/multiset/map/multimap 容器的底层数据结构就红黑树（Red-Black Tree）—— 一种'近似平衡'的二叉搜索树（BST）。但不同的是，对于 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>; // 使用 using 重命名
public:
// ...
private:
Node* _root = nullptr; // 成员变量
};
***说明：***下面我们实现过程中默认为值不重复的情形
思路：
（1）树为空，则直接新增结点，赋值给 root 指针
（2）树不空，按二叉搜索树性质，用 cur 指针遍历二叉搜索树，用一个 parent 指针记下父亲节点，要插入值 key 比当前节点大往右走，插入值比当前结点小往左走，直到找到空位置，插入新结点。
（4）确定要插入的节点在父亲节点的左边还是右边，即当_key < parent->_key 则将新节点插入到 parent 的左边，反之则插入到右边。
（5）如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。但是，要确定相同的值要么都往左边走或者都往右边走。
//-------------------------------代码实现-------------------------------------------------
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);
std::cout << _root->_key << " ";
_MidOrder(_root->_right);
}
思路：
（1）从根开始比较，查找 val，val 比根的值大则往右边走查找，val 比根值小则往左边走查找。
（2）最多查找高度次，走到到空，还没找到，这个值不存在，返回 false。
（3）如果不支持插入相等的值，找到 x 即可返回。
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 if (val == cur->_key) {
return true;
} else {
return false;
}
}
return false;
}
思路：
（1）要删除节点 N 的位置有四种情况： a. 结点 N 左右孩子均为空；b. 结点 N 左孩子为空，右孩子结点不为空；c. 结点 N 右孩子位空，左孩子结点不为空；d. 结点 N 左右孩子结点均不为空。
（2）对于左右孩子都为空的情况，我们可以将其放在左孩子为空和右孩子为空的情况中处理。即将上面四种情况重新分为：左为空；右为空；左右都不为空三种。
（3）对于左为空，要删除节点 N 可能为根结点，则让该节点的右节点作为新的根结点；或者是父节点的左节点，则让父节点的_left 指针指向节点 N 的右边；或者父节点的右节点，则让父节点的_right 指针指向节点 N 的左边，右为空类似。
（4）对于左右都不为空，无法直接删除 N 结点，因为 N 的两个孩子无处安放，只能用替换法删除，找 N 左子树的值最大结点 R(最右结点) 或者 N 右子树的值最小结点 R(最左结点) 替代 N，因为这两个结点中任意一个，放到 N 的位置，都满足二叉搜索树的规则。替代 N 的意思就是 N 和 R 的两个结点的值交换，转而变成删除 R 结点，R 结点符合情况 2 或情况 3，可以直接删除。
bool Erase(const K& val) {
Node* cur = _root;
Node* parent = nullptr; // 修正：初始化 parent 为 nullptr 以处理根节点删除逻辑
// 遍历先找到 N 节点
while (cur) {
if (val < cur->_key) {
parent = cur;
cur = cur->_left;
} else if (val > cur->_key) {
parent = cur;
cur = cur->_right;
} else {
// 找到 N 节点
// 左为空
if (cur->_left == nullptr) {
// 根结点
if (parent == nullptr) {
_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 (parent == nullptr) {
_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; // 找右子树中最小值的节点 R(最左结点)
(replace->_left) {
replaceparent = replace;
replace = replace->_left;
}
cur->_key = replace->_key;
(replace == replaceparent->_left) {
replaceparent->_left = replace->_right;
} {
replaceparent->_right = replace->_right;
}
replace;
}
;
}
}
;
}
为什么还有 key_value 类型二叉搜索树呢？对于 map/multimap 容器，映射（Maps）是一种关联容器，它按照特定顺序存储由'键值（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;
};
***说明：***对于 key_value 类型我们实现一下其构造，析构等，除了插入操作与 key 类型有一点不同外，其他操作基本相同，所以我们不再重复解释。
// 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;
}
// 赋值重载 (现代写法)
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;
}
本文主要是简单实现了一下二叉搜索树的最基础的版本，与 set/multiset/map/multimap 底层的数据结构——平衡二叉搜索树有所不同，并没有过多关注底层实现细节，比如 insert，Find 返回值等。只是为了能够加深大家对二叉搜索树的理解，方便后面对平衡二叉树的理解。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online