本文详细讲解了 C++ 中二叉搜索树（BST）的概念、定义及核心操作。内容包括 BST 的递归定义、中序遍历特性、节点结构体设计。重点阐述了默认构造函数、拷贝构造、赋值运算符重载（Swap 技巧与传统深拷贝）的实现原理。深入分析了查找、插入、删除（含直接删除与替换法）的算法逻辑与代码实现。此外，还探讨了 BST 的性能分析（时间复杂度）、应用场景（K 模型与 KV 模型）以及代码中的模板与类型细节。
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
从二叉搜索树的定义可知，它的前提是二叉树，并且采用了递归的方式进行定义。它的结点间满足一个偏序关系，左子树根结点的值一定比父结点小，右子树根结点的值一定比父结点大。
正如它的名字所说，构造这样一棵树的目的是为了提高搜索的速度。如果对二叉搜索树进行中序遍历，我们可以发现，得到的序列是个递增序列。
递归说明：
- 左右子树本身是二叉搜索树。无论从哪个节点开始，只需考察当前节点的值是否满足与左子树和右子树的比较关系；然后递归到左右子树去判断它们是否分别满足二叉搜索树的性质。
- 以根节点为核心的分层定义 + 当前树的性质由当前根节点与左右子树的性质共同决定；左子树和右子树本身可以被视为规模更小的二叉搜索树，这种嵌套结构直接表明递归定义的存在。
// 树节点的结构体
struct BSTreeNode {
typedef BSTreeNode<K> Node; // 千万别少了这句！！！！！！
Node* _left;
Node* _right;
K _key;
BSTreeNode(const K& key) // 这里是 K 是大写，一定要注意
: _left(nullptr), _right(nullptr), _key(key) {}
};
template<class K>
class BSTree {
typedef BSTreeNode<K> Node;
public:
// 默认构造
BSTree() = default;
// 拷贝构造
BSTree(const BSTree<K>& t) { _root = Copy(t._root); }
private:
// 下面这部分隐藏，对外只提供 InOrder(). 用户只用关注接口不必关心细节。
Node* Copy(Node* root) {
if (root == nullptr) return nullptr;
Node* newRoot = new Node(root->_key);
// 通过递归调用 Copy 函数来复制当前节点的左子节点。将返回的新左子树赋值给 newRoot 的左子节点
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
return newRoot;
}
Node* _root = nullptr;
};
BSTree() = default在上面完整的代码中，BSTree() 默认构造函数是通过以下代码定义的：
BSTree() = default;
= default 的作用：
BSTree() = default; 时，编译器会为类自动生成一个默认的构造函数。它的行为等价于一个空的用户定义构造函数，但由编译器自动完成。= default：显式告诉编译器生成默认构造函数，表示我们明确需要这个默认的构造行为。避免用户误以为我们忘记定义构造函数。保持代码简单，同时遵守编译器生成的高效实现。BSTree 类包含一个私有成员变量 _root：
Node* _root = nullptr;
_root 初始化为 nullptr（因为你用了类内初始化 Node* _root = nullptr;）。但如果你显式定义了其他构造函数（比如拷贝构造、赋值重载），编译器将不再自动生成默认构造函数。为避免丢失默认构造函数的功能，就需要显式使用 = default;。BSTree() = default;，代码更直观地表明：'这个类的默认构造行为是由编译器生成的，我没有进行额外的修改。'= default 和手动定义的区别如果不使用 = default 而是手动定义默认构造函数：
BSTree():_root(nullptr){}
行为与 = default 等价，但显式手动定义不如 = default 简洁。
= default 的好处包括：
使用 = default 常见于以下场景：
= default 更直观。BSTree<K>& operator=(const BSTree<K>& t) {
swap(_root, t._root);
return *this;
}
// 传统深拷贝写法。也很好
// BSTree<K>& operator =(const BSTree<K>& t) {
// tree1 = tree2
// if (this != &t) {
// Destroy(_root); // 清空 tree1 树里的节点，树还在，但是空树
// _root = Copy(t._root); // 把 tree2 里的节点深拷贝到 tree1
// }
// return *this; // 返回 tree1；
// }
这种写法很高效，节省资源，一定要掌握！！！
我们通过一个详细的例子来说明写法二（swap 方式）中的每一步，以及各个变量（如 this 和 t）的变化。
代码回顾
template<class K>
class BSTree {
typedef BSTreeNode<K> Node;
public:
BSTree<K>& operator=(BSTree<K> t) {
swap(_root, t._root);
return *this;
}
private:
Node* _root = nullptr;
};
假设情景
假设有两个二叉搜索树对象 tree1 和 tree2，它们的树结构如下：
tree1：树的根节点为 _root = 5。tree2：树的根节点为 _root = 10。现在我们要将 tree1 赋值为 tree2，即 tree1 = tree2;。
初始状态
tree1._root：指向 5 节点。tree2._root：指向 10 节点。接下来我们逐步讲解赋值运算符 tree1 = tree2; 的执行过程。
第一步：函数调用时，创建临时副本 t
BSTree<K>& operator=(BSTree<K> t)
tree1 = tree2; 发生时，tree2 作为参数传递给 BSTree<K> t，因此会调用 复制构造函数，为 t 创建一个 tree2 的副本。t._root 指向了 tree2 的根节点（即 10），但 t 是一个独立的对象，内存完全独立于 tree2。变量状态：
this：指向 tree1，this->_root = 5。t._root：指向 tree2 的副本，即根节点为 10。第二步：执行 swap
swap(_root, t._root);
这里使用的是标准库中的 std::swap 函数。该函数的核心是交换两个对象的值，具体步骤如下：
temp：temp 保存 this->_root（即 tree1 的 _root），此时 temp = 5。t._root 赋给 this->_root：此时 this->_root 指向 t._root 的值（即 10），也就是 tree2 的根节点。temp 赋给 t._root：最后，t._root 变为 5，即之前 tree1 的根节点。swap 操作结束后，tree1 和 t 的根节点已经交换。
变量状态：
this->_root：现在指向 10，即 tree2 的根节点。t._root：现在指向 5，即 tree1 原来的根节点。第三步：返回当前对象（链式调用支持）
return *this;
operator= 函数返回当前对象，即 tree1，此时 tree1._root = 10。t 是传递进来的临时变量，会在函数结束时自动销毁。由于 t._root 现在指向的是 5（即 tree1 原来的根节点），当 t 离开作用域时，其析构函数会被调用，自动释放 5 这个节点及其子树（如果有）。最终结果
tree1：现在拥有 tree2 的树结构，根节点为 10。tree2：原来的结构不变，仍然指向 10，但由于我们是通过副本 t 操作，tree2 本身不会受到影响。tree1 的树（即以 5 为根的树）：在 t 的生命周期结束时，随着 t 的析构函数被调用，旧的 tree1 树被销毁。关键点总结：
tree2 的副本传递给 t，t 独立于 tree2。swap：swap 交换了 tree1 和 t 的根节点指针，而不是深拷贝整个树，效率更高。t 是传入的临时变量，赋值过程结束后 t 会被自动销毁，释放旧的 tree1 的内存，避免了手动 Destroy 的麻烦。return *this 支持链式调用，如 tree1 = tree2 = tree3;。这种 swap 的写法，简洁、高效，并且通过临时对象 t 自动管理资源，是现代 C++ 中推荐的写法。
return *this?为什么返回 *this？即使 tree1 的内存已被释放？
释放的只是原树的节点，树本身仍然存在
调用 Destroy(_root) 时，仅释放了 tree1 原有的节点内存，但 tree1 本身（即当前对象）仍然存在。_root 只是一个指针成员变量，而非整个 tree1 对象的内存。
例如：
tree1 原本有数据，它们会被 Destroy 清空，变成一个空树（_root == nullptr）。Copy(t._root)，重新构造 tree1 的数据结构，使其变得与 tree2 相同。
最终，tree1 并没有被销毁，而是被重建。返回值的意义：支持链式赋值
返回 *this 是赋值运算符的标准设计，用于支持链式赋值。链式赋值允许连续的赋值操作，如：
BSTree<int> a, b, c; a = b = c;
b = c 执行后，返回 b 的引用。b 的引用作为参数传递给 a = b。
如果不返回 *this，链式赋值将无法工作。为什么不是返回销毁的内容？
Destroy(_root) 只是清空了树的原有数据，tree1 的对象本身还存在。返回 *this 是返回当前对象的引用，表示赋值操作完成，当前对象的状态被更新为目标对象的状态。
例如：
BSTree<int> tree1, tree2; // 假设 tree1 有旧的节点，tree2 是目标树
tree1 = tree2;
在 tree1 = tree2 过程中：
tree1 的原节点，但 tree1 本身还在。tree2 的数据复制到 tree1。tree1 的引用，表示 tree1 现在是 tree2 的深拷贝。示意图说明 初始状态：
tree1：包含若干节点，_root 指向一棵树。tree2：包含若干节点，_root 指向另一棵树。
操作后：Destroy(_root) 释放 tree1 的所有节点，_root 变成 nullptr。Copy(t._root) 创建一棵新的树，将 tree2 的节点深拷贝到 tree1。tree1 现在与 tree2 的内容一致。
链式赋值：a = b = c;
等效于：
b = c; // b 变为 c 的拷贝
a = b; // a 变为 b 的拷贝 (实际上 a 也变为 c 的拷贝)
每次赋值后，*this 返回当前对象的引用供下一个操作使用。
~BSTree()~BSTree() { Destroy(_root); }
InOrder()void InOrder() {
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root) {
if (root == nullptr) return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
InOrder() 为何这样设计？InOrder() 函数设计的目的是为了封装实现细节，让用户只需调用接口函数即可完成对二叉树的中序遍历，而不必了解树的内部数据结构。这种设计的优势在于以下几点：
隐藏内部实现细节
在代码中，InOrder() 调用了一个私有的辅助递归函数 _InOrder(Node* root)：
void InOrder() { _InOrder(_root); cout << endl; }
用户只需要调用 tree.InOrder() 就可以触发中序遍历，输出节点值，而不需要知道：
BSTreeNode<K> 的定义)。_root 开始。
这种封装遵循了面向对象编程中的封装原则，屏蔽了用户不需要知道的复杂实现。简化用户操作 对于用户来说，他们关心的是功能，而非具体实现。用户只需要：
tree.InOrder();
而不需要自己写出复杂的递归逻辑去遍历树，例如：
void InOrderManual(BSTreeNode<int>* root) {
if (!root) return;
InOrderManual(root->_left);
cout << root->_key << " ";
InOrderManual(root->_right);
}
封装之后，用户无需处理树的节点指针，也不用理解递归过程，降低了使用门槛。
降低错误概率
让用户直接访问和操作树的内部结构（如 _root 指针）可能导致以下问题：
_root 或其他节点的子指针）。InOrder() 方法，用户无法直接接触内部的 _root 或树节点，减少了误操作的风险。增强代码的可维护性和扩展性
如果以后需要修改中序遍历的实现（例如加入线程或并行化），我们只需改动私有的 _InOrder() 方法，而无需修改 InOrder() 或影响用户代码。
用户调用 InOrder() 的方式保持不变，代码改动对外透明。这种设计符合模块化设计的思想。
另外需要注意的是： ① 最大元素一定是在树的最右分枝的端结点上。 ② 最小元素一定是在树的最左分枝的端结点上。
// find 函数。用 k，关键字的意思
bool Find(const K& key) {
Node* cur = _root; // 从根节点开始查找
// _root 是存储在 BSTree 类中的成员变量，它指向树的根节点。通过这个指针，你可以访问整个树。
while (cur) {
if (cur->_key < key) {
cur = cur->_right;
} else if (cur->_key > key) {
cur = cur->_left;
} else {
return true;
}
}
return false;
}
root == nullptr），那么直接把要插入的元素作为根节点插入即可。cur 来遍历树，初始时 cur = root。parent 记录当前节点的'父节点'，也就是 cur 移动前的位置。这样，当找到一个空位时，知道应该插入在 parent 的左子树还是右子树。cur 移动到空位置（即 cur == nullptr）时，根据 parent 的位置决定插入新元素：
parent 的值，插入到 parent 的左子树；parent 的值，插入到 parent 的右子树。// 插入
// 类的成员函数（如 Insert）中，成员变量 (_root) 是直接可见的，无需通过参数传递。
// 这是因为成员函数默认会操作类的当前实例。
bool Insert(const K& key) {
// Node* cur = new Node(key); // 这里的 new 后面加什么还是不太清楚。New 的用法忘了，及时复习。
if (_root == nullptr) {
_root = new Node(key);
return true;
}
// 关键：保存父节点
Node* parent = nullptr;
// Node* cur = root; // 错误写法
Node* cur = _root; // 不是 root
while (cur) {
if (cur->_key < key) {
parent = cur;
cur = cur->_right;
} else if (cur->_key > key) {
parent = cur;
cur = cur->_left;
} else {
return false; // 重复了，树里面已经有了 key。插入不了。
}
}
// 此时 cur 为空，为待插入的位置
// cur = new Node(key); // 这句又忘了
// if (parent->_right == nullptr) {
// parent->_left = cur;
// }
// else {
// parent->_left = cur;
// }
// 上面的写法是错的。
// 假如插入 16，此时 parent 为 14，cur 为空，应该判断 key 与 parent 的大小关系，而不是 14 左右子树是否为空。
// 按照错误逻辑，16 插入到 14 的左子树了
// 8
// 3 10
// 1 6 14
// cur = new Node(key);
if (parent->_key < key) {
parent->_right = cur;
} else {
parent->_left = cur;
}
return true;
}
首先查找元素是否在二叉搜索树中，如果不存在，则返回，否则要删除的结点可能分下面四种情况： a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点
看起来有待删除节点有 4 种情况，实际情况 a 可以与情况 b 或者 c 合并起来，因此真正的删除过程如下：
情况 b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
情况 c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
情况 d：在它的右子树中寻找中序下的第一个结点 (关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题–替换法删除
a,b,c 情况——直接删除 将待删除节点的父节点指向待删除节点的孩子节点
我们的目标依然是要保证删除结点 8 后，再次中序遍历它，仍不改变其升序的排列方式。那么我们只有用 7 或者 10 来替换 8 原来的位置。
用 7 替换待删除节点
用 10 替换待删除节点
为什么是 7 或者 10 来替换 8 的位置？ 显然，7 与 10 是挨着 8 的，如果用其他元素替换则会打扰其顺序。那 7 和 10 怎么在二叉排序树中找到呢？ 显然，7 在 8 左子树的'最右边'，10 在 8 右子树的'最左边'。根据二叉排序树的插入方式，比 8 小的元素一定在左子树，而我们又要找到比 8 小的最大的数，这样才能保证他们俩在顺序上是挨着的，所以它又会在 8 的左子树的最右边。同理也可以找到 10.
bool Erase(const K& key) {
Node* parent = nullptr;
Node* cur = _root;
while (cur) {
if (cur->_key < key) {
parent = cur;
cur = cur->_right;
} else if (cur->_key > key) {
parent = cur;
cur = cur->_left;
} else {
// 找到了待删除的节点。
// 左子节点为空（或者是叶子节点）:
if (cur->_left == nullptr) {
if (cur == _root) {
_root = cur->_right;
} else {
/* 10
/ \
5 15
/ \
3 7 */
// 假如删除，15 是 10 的右，把 15 的右 (空),给 10 的右。
// 由此可知：左子节点为空 这部分代码可以解决叶子节点的情况
if (cur == parent->_right) {
parent->_right = cur->_right;
} else {
parent->_left = cur->_right;
}
}
delete cur;
return true;
}
// 右子节点为空:
else if (cur->_right == nullptr) {
if (cur == _root) {
_root = cur->_left;
} else {
if (cur == parent->_right) {
parent->_right = cur->_left;
} else {
parent->_left = cur->_left;
}
}
delete cur;
return true;
}
// 左右子节点均不为空:
else {
// 替换法
Node* rightMinParent = cur;
Node* rightMin = cur->_right;
while (rightMin->_left) {
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
if (rightMin == rightMinParent->_left)
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;
return true;
}
}
}
return false;
}
下面一张图也可以帮助理解。
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有 n 个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
最优情况下，二叉搜索树为完全二叉树 (或者接近完全二叉树)，其平均比较次数为：$log_2 N$
最差情况下，二叉搜索树退化为单支树 (或者类似单支)，其平均比较次数为：$\frac{N}{2}$
// 统计词语出现的次数
string strs[] = {"苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果"};
// 统计水果出现的次数
BSTree<string, int> countTree;
for (auto str : strs) {
auto ret = countTree.Find(str);
if (ret == NULL) {
countTree.Insert(str, 1);
} else {
ret->_value++;
}
}
countTree.InOrder();
<K,V>模型代码
namespace key_value {
// ======================
// 二叉搜索树节点结构体
// ======================
template<class K, class V>
struct BSTreeNode {
// 为了简化书写，用 Node 表示 BSTreeNode<K, V> 类型本身
typedef BSTreeNode<K, V> Node;
Node* _left; // 指向左子节点
Node* _right; // 指向右子节点
K _key; // 节点存储的键
V _value; // 节点存储的值
// 构造函数，用来初始化节点的 key 和 value
BSTreeNode(const K& key, const V& value)
: _left(nullptr), _right(nullptr), _key(key), _value(value) {}
};
// =====================
// 二叉搜索树类
// =====================
template<class K, class V>
class BSTree {
typedef BSTreeNode<K, V> Node;
public:
// 构造函数
BSTree() : _root(nullptr) {}
// 向二叉搜索树中插入一个键值对 (key, value)
// 返回值：如果插入成功返回 true，如果插入失败 (已存在相同 key) 返回 false
bool Insert(const K& key, const V& value) {
// 如果树为空，则直接创建根节点
if (_root == nullptr) {
_root = new Node(key, value);
return true;
}
// 从根节点开始，寻找正确的插入位置
Node* parent = nullptr;
Node* cur = _root;
while (cur) {
// 若当前节点 key 小于要插入的 key，则往右子树查找
if (cur->_key < key) {
parent = cur;
cur = cur->_right;
}
// 若当前节点 key 大于要插入的 key，则往左子树查找
else if (cur->_key > key) {
parent = cur;
cur = cur->_left;
} else {
// 发现已有相同 key，插入失败
return false;
}
}
// 创建新节点
cur = new Node(key, value);
// 判断要插入到 parent 的左子树还是右子树
if (parent->_key < key) {
parent->_right = cur;
} else {
parent->_left = cur;
}
return true;
}
// 查找给定 key 对应的节点，返回指向该节点的指针，如果不存在则返回 nullptr
Node* Find(const K& key) {
Node* cur = _root;
while (cur) {
if (cur->_key < key) {
cur = cur->_right;
} else if (cur->_key > key) {
cur = cur->_left;
} else {
// 找到 key
return cur;
}
}
// 未找到 key
return nullptr;
}
// 从二叉搜索树中删除 key 对应的节点，成功返回 true，失败返回 false
bool Erase(const K& key) {
Node* parent = nullptr; // 记录要删除节点的父节点
Node* cur = _root; // 从根节点开始查找
// 1. 先找到要删除的节点 cur 及其父节点 parent
while (cur) {
if (cur->_key < key) {
parent = cur;
cur = cur->_right;
} else if (cur->_key > key) {
parent = cur;
cur = cur->_left;
} else {
// 找到了要删除的节点
// 2. 根据 cur 是否存在子树分情况处理
// a) cur 没有左子树
if (cur->_left == nullptr) {
// 如果 cur 是根节点，则直接将根设置为右子树
if (cur == _root) {
_root = cur->_right;
} else {
// 如果 cur 不是根节点，则根据 parent 判断
// cur 是 parent 的左子树还是右子树
if (cur == parent->_right) {
parent->_right = cur->_right;
} else {
parent->_left = cur->_right;
}
}
delete cur;
return true;
}
// b) cur 没有右子树
else if (cur->_right == nullptr) {
if (cur == _root) {
_root = cur->_left;
} else {
if (cur == parent->_right) {
parent->_right = cur->_left;
} else {
parent->_left = cur->_left;
}
}
delete cur;
return true;
}
// c) cur 既有左子树又有右子树
else {
// 使用替换法：找到 cur 的右子树中的最小值节点替换掉 cur
Node* rightMinParent = cur;
Node* rightMin = cur->_right;
// 在右子树中一直往左走，找到最小值节点
while (rightMin->_left) {
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
// 用最小值节点替换当前节点
cur->_key = rightMin->_key;
cur->_value = rightMin->_value;
// 将最小值节点删除
if (rightMin == rightMinParent->_left)
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;
return true;
}
}
}
// 没有找到要删除的 key
return false;
}
// 中序遍历：从小到大打印 key
void InOrder() {
_InOrder(_root);
cout << endl;
}
private:
// 辅助函数：中序遍历
void _InOrder(Node* root) {
if (root == nullptr) return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
private:
Node* _root; // 指向二叉搜索树的根节点
};
}
template<class K>
// 树节点的结构体
struct BSTreeNode {
typedef BSTreeNode<K> Node; // 千万别少了这句！！！！！！
Node* _left;
Node* _right;
K _key;
BSTreeNode(const K& key) // 这里是 K 是大写，一定要注意，改了好多
: _left(nullptr), _right(nullptr), _key(key) {}
};
template<class K>
// 二叉搜索树这个类
class BSTree {
typedef BSTreeNode<K> Node;
public:
// 默认构造
BSTree() = default;
// 拷贝构造
BSTree(const BSTree<K>& t) { _root = Copy(t._root); }
// 赋值重载
// 完整的函数名每次忘记怎么写
// BSTree<K>&：返回值类型是对当前对象的引用，以便支持链式赋值（a = b = c; ）。
// operator=：定义赋值运算符。
// const BSTree<K>& t：参数类型是一个 const 引用，表示要赋值的对象不应被修改。
// 使用 swap 交换资源
BSTree<K>& operator=(const BSTree<K>& t) {
swap(_root, t._root);
return *this;
}
// 传统深拷贝写法。也很好（代码详解在语雀）
// BSTree<K>& operator =(const BSTree<K>& t) {
// tree1 = tree2
// if (this != &t) {
// Destroy(_root); // 清空 tree1 树里的节点，树还在，但是空树
// _root = Copy(t._root); // 把 tree2 里的节点深拷贝到 tree1
// }
// return *this; // 返回 tree1；
// }
// 析构
~BSTree() { Destroy(_root); }
// 插入
// 类的成员函数（如 Insert）中，成员变量 (_root) 是直接可见的，无需通过参数传递。这是因为成员函数默认会操作类的当前实例。
bool Insert(const K& key) {
// Node* cur = new Node(key); // 这里的 new 后面加什么还是不太清楚。New 的用法忘了
if (_root == nullptr) {
_root = new Node(key);
return true;
}
// 关键：保存父节点
Node* parent = nullptr;
// Node* cur = root; // Node* cur = root; 错误写法
Node* cur = _root; // 不是 root
while (cur) {
if (cur->_key < key) {
parent = cur;
cur = cur->_right;
} else if (cur->_key > key) {
parent = cur;
cur = cur->_left;
} else {
return false; // 重复了，树里面已经有了 key。插入不了。
}
}
// 此时 cur 为空，为待插入的位置
// cur = new Node(key); // 这句又忘了
// if (parent->_right == nullptr) {
// parent->_left = cur;
// }
// else {
// parent->_left = cur;
// }
// 上面的写法是错的。
// 假如插入 16，此时 parent 为 14，cur 为空，应该判断 key 与 parent 的大小关系，而不是 14 左右子树是否为空。
// 按照错误逻辑，16 插入到 14 的左子树了
// 8
// 3 10
// 1 6 14
// cur = new Node(key);
if (parent->_key < key) {
parent->_right = cur;
} else {
parent->_left = cur;
}
return true;
}
bool Erase(const K& key) {
Node* parent = nullptr;
Node* cur = _root;
while (cur) {
if (cur->_key < key) {
parent = cur;
cur = cur->_right;
} else if (cur->_key > key) {
parent = cur;
cur = cur->_left;
} else {
// 找到了待删除的节点。
// 左子节点为空（或者是叶子节点）:
if (cur->_left == nullptr) {
if (cur == _root) {
_root = cur->_right;
} else {
/* 10
/ \
5 15
/ \
3 7 */
// 假如删除，15 是 10 的右，把 15 的右 (空),给 10 的右。
// 由此可知：左子节点为空 这部分代码可以解决叶子节点的情况
if (cur == parent->_right) {
parent->_right = cur->_right;
} else {
parent->_left = cur->_right;
}
}
delete cur;
return true;
}
// 右子节点为空:
else if (cur->_right == nullptr) {
if (cur == _root) {
_root = cur->_left;
} else {
if (cur == parent->_right) {
parent->_right = cur->_left;
} else {
parent->_left = cur->_left;
}
}
delete cur;
return true;
}
// 左右子节点均不为空:
else {
// 替换法
Node* rightMinParent = cur;
Node* rightMin = cur->_right;
while (rightMin->_left) {
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
if (rightMin == rightMinParent->_left)
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;
return true;
}
}
}
return false;
}
// find 函数。用 k，关键字的意思
bool Find(const K& key) {
Node* cur = _root; // 从根节点开始查找
// Node* cur = nullptr; // 为什么不行？
// _root 是存储在 BSTree 类中的成员变量，它指向树的根节点。通过这个指针，你可以访问整个树。
while (cur) {
if (cur->_key < key) {
cur = cur->_right;
} else if (cur->_key > key) {
cur = cur->_left;
} else {
return true;
}
}
return false;
}
// 前序遍历
void InOrder() {
_InOrder(_root);
cout << endl;
}
//------------------------------------------------------------------------------------------------------------------
// 递归实现
// 这样的设计通常是为了提供递归操作的接口，允许用户以更简单的方式调用递归函数。以下是这些函数的作用：
// bool FindR(const K& key) // 递归查找键值是否存在于树中。
// 实际上调用 _FindR 函数。
bool FindR(const K& key) {
return _FindR(_root, key);
}
// bool InsertR(const K& key) // 递归插入一个键值到树中。
// 实际上调用 _InsertR 函数。
bool InsertR(const K& key) {
return _InsertR(_root, key);
}
// bool EraseR(const K& key) // 递归删除一个键值。
// 实际上调用 _EraseR 函数。
bool EraseR(const K& key) {
return _EraseR(_root, key);
}
private:
// 下面这部分隐藏，对外只提供 InOrder(). 用户只用关注接口不必关心细节。
void _InOrder(Node* root) {
if (root == nullptr) return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
Node* Copy(Node* root) {
if (root == nullptr) return nullptr;
Node* newRoot = new Node(root->_key);
// 通过递归调用 Copy 函数来复制当前节点的左子节点。将返回的新左子树赋值给 newRoot 的左子节点
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
return newRoot;
}
// 赋值运算重载的第二种写法要用到，析构函数也要用到
void Destroy(Node* root) {
if (root == nullptr) return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
// 这些函数的实现通常会更简洁，因为递归结构自然而然地处理了树的遍历：
// bool _FindR(Node* root, const K& key) // 如果当前节点为空，则返回 false。
// 根据键值与当前节点的比较，决定向左或向右子树递归查找。
bool _FindR(Node* root, const K& key) {
if (root == nullptr) return false;
if (root->_key < key) return _FindR(root->_right, key);
else if (root->_key > key) return _FindR(root->_left, key);
else return true;
}
// bool _InsertR(Node*& root, const K& key) // 处理插入操作的递归逻辑。
// 当找到合适的插入位置（当前节点为空）时，创建新节点。
bool _Insert(Node*& root, const K& key) {
if (root == nullptr) {
// root->_key = key;
root = new Node(key);
return true;
}
if (root == nullptr) return false;
if (root->_key < key) return _Insert(root->_right, key);
else if (root->_key > key) return _Insert(root->_left, key);
else {
// 遇到值相等的，重复了 无法插入
return false;
}
}
// bool _EraseR(Node*& root, const K& key) // 处理删除操作的递归逻辑。
// 逻辑与非递归的 _Erase 类似，但通过递归方式实现。
bool _EraseR(Node*& root, const K& key) {
// Node* parent = nullptr;
// Node* cur = root;
if (root == nullptr) return false;
if (root->_key < key) return _EraseR(root->_right, key);
else if (root->_key < key) return _EraseR(root->_left, key); // 注意此处应为 > key，原文可能有误，按逻辑修正
else {
// 注意，root 是上一节点的左指针 (右指针)
// 保存当前待删除的节点。
Node* del = root;
// 如果左子树为空
if (root->_right == nullptr) {
root = root->_left;
} else if (root->_left == nullptr) {
root = root->_right;
} else {
// Node* rightMin = root->_right;
// while (rightMin->_left) {
// rightMin = rightMin->_left;
// }
Node* rightMin = root->_right;
while (rightMin->_left) {
rightMin = rightMin->_left;
}
swap(root, rightMin);
return _EraseR(root->_right, key);
}
delete del;
return true;
}
}
private:
Node* _root = nullptr;
};
template <class K>在上面的代码中，出现两处 template <class K> 是因为它们的作用域和含义不同：
第一处 template <class K>
template<class K>
struct BSTreeNode
这一部分定义了一个模板结构体 BSTreeNode，它接受一个模板参数 K，用来指定二叉搜索树节点的关键字类型。模板参数 K 是用来描述节点内部的 _key 数据成员类型。
第二处 template <class K>
template<class K>
class BSTree
这里定义了一个模板类 BSTree，它也接受一个模板参数 K，用来指定树中的节点关键字类型。BSTree 内部的 Node 类型被定义为 BSTreeNode<K>，即二叉树节点的模板参数类型与 BSTree 的模板参数一致。
为什么需要两次 template <class K>？
这是因为 模板定义的作用域是独立的，模板参数的声明只能在其所属的模板中生效。也就是说：
BSTreeNode<K> 的 K 和 BSTree<K> 的 K 是两个不同的模板参数，尽管它们名字相同，但彼此独立。BSTree 中使用 BSTreeNode<K> 时，需要显式传递模板参数 K，以表明 BSTreeNode 的模板实例化。如果模板类 BSTree 不单独定义自己的模板参数，而直接使用 BSTreeNode<K> 的模板参数，会导致代码难以扩展和维护。
bool 和 status 的区别bool 和 status 的区别主要取决于上下文中的定义和使用方式。以下是它们之间的一些典型区别：
bool 是一种数据类型bool 是一种内置的布尔类型，用来表示逻辑上的真假值，取值范围是 true 或 false。示例:
bool isReady = true; // 表示某个条件成立
if (isReady) {
// 做某些事情
}
status 是一种抽象的状态表示status 一般用于表示系统、进程、任务、操作等的状态，通常不局限于 true 和 false 两种值。示例（用枚举表示 status）:
enum class Status {
SUCCESS,
FAILURE,
PENDING,
ERROR
};
Status taskStatus = Status::PENDING; // 当前任务正在处理中
if (taskStatus == Status::SUCCESS) {
// 操作成功
} else if (taskStatus == Status::ERROR) {
// 操作失败
}
| 特性 | bool | status |
|---|---|---|
| 类型 | 内置类型 | 通常是枚举或扩展类型 |
| 取值范围 | 仅有 true 和 false | 可以有多个值（如 SUCCESS, FAILURE） |
| 信息丰富度 | 表示简单的二元逻辑结果 | 可以描述更复杂的状态 |
| 可扩展性 | 不可扩展 | 易于扩展更多状态值 |
bool。status 或类似的机制。在实际工程中，可以同时使用 bool 和 status，例如在函数返回值中使用 status 表示总体结果，用 bool 表示局部成功或失败的标志：
enum class Status {
SUCCESS,
PARTIAL_SUCCESS,
FAILURE,
ERROR
};
bool isValidInput(const std::string& input) {
return !input.empty(); // 简单的真假判断
}
Status processTask(const std::string& task) {
if (!isValidInput(task)) {
return Status::ERROR; // 返回复杂状态
}
// 处理任务逻辑...
return Status::SUCCESS;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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