本文详细介绍了 C++ 中二叉搜索树（BST）的核心设计与实现。内容涵盖 BST 的定义与性质、节点与树的整体架构设计。重点讲解了构造、析构、拷贝构造及赋值运算符的实现，特别是深拷贝与拷贝交换技巧。深入剖析了插入、查找、中序遍历及删除操作的迭代与递归两种实现方式，包括删除节点时的三种情况处理（左空、右空、双非空）。最后进行了性能分析，指出平均时间复杂度为 O(h)，最坏情况为 O(n)，并强调了平衡树的重要性。文章提供了完整的可运行代码示例。
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是：
map/set/multimap/multiset 系列容器底层就是二叉搜索树，其中 map/set 不支持插入相等值，multimap/multiset 支持插入相等值// 二叉搜索树
template<class K>
struct BSTreeNode {
BSTreeNode(const K& key) : _left(nullptr), _right(nullptr), _key(key) {}
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
};
_keyBSTreeNode* _left：指向左孩子的指针BSTreeNode* _right：指向右孩子的指针K _key：存储相应的的键值nullptr_key 为传入的值 keystruct 设计，默认权限为 public，方便下文的 BSTree 类访问成员template<typename K>
class BSTree {
typedef BSTreeNode<K> Node;
public:
// ...（以下为类的成员函数）
private:
Node* _root;
};
BSTreeNode<K> 是模板节点，包含左右指针和键 _key。BSTree<K> 以 _root 指向树根。类内 typedef BSTreeNode<K> Node; 简化后续代码书写。public:
BSTree() : _root(nullptr) {}
BSTree()：默认构造，构造一颗空树，只需将根节点指针 _root 置空即可public:
~BSTree() { Destroy(_root); }
private:
// Destroy（后序删除）
void Destroy(Node*& root) {
if (root == nullptr) return;
// 二叉树的析构，走后序遍历删除
Destroy(root->_left);
Destroy(root->_right);
delete root;
root = nullptr;
}
_root 结点及其子节点管理的内存资源，因此无法通过传统传参递归的方式释放节点。void Destroy(Node*& root)：后序遍历删除实现
Node*& root 引用形式，函数栈帧中的形参 root 成为了每个节点的地址的别名。Node*& root 引用形式允许在删除左右子树后把父指针设为 nullptr，避免悬空指针。~BSTree()：调用 Destroy(_root) 做后序销毁，释放所有节点。public:
BSTree(const BSTree<K>& tree) : _root(nullptr) { _root = Copy(tree._root); }
private:
Node* Copy(Node* root) {
if (root == nullptr) return nullptr;
else {
Node* newRoot = new Node(root->_key);
// 分别递归拷贝 左右子树，拷贝完后，递归回去连接
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
return newRoot;
}
}
const BSTree& 类型，而我们拷贝树需要依次拷贝每个节点，递归拷贝节点时需要传入根节点作为参数。BSTree(const BSTree<K>&)：先把 _root 初始化为 nullptr，再调用私有 Copy 做深拷贝，_root 接收返回的新树的根。这样可以保证两个树互不干扰。Copy() 函数的逻辑，整体逻辑采用递归实现：
nullptr 空结点时，向上级栈帧中返回结点的指针，完成结点的链接关系return 时，向上级栈帧中返回所拷贝结点的指针operator= 的现代写法：
// t2 = t1
public: BSTree<K>& operator=(BSTree<K> tmp) {
std::swap(_root, tmp._root);
return *this;
}
赋值运算符 operator=(BSTree<K> tmp) 重载：采用**拷贝 - 并 - 交换（copy-and-swap）**技巧：t2 = t1
tmp 为值传递，会调用拷贝构造生成一个局部副本（或借助移动语义），该副本 tmp 也为一个 BSTree 对象，和 t1 的内容完全一致，且有各自独立的数据空间。std::swap(_root, tmp._root) 交换资源，更改管理资源的指针的指向，这样 tmp 的析构会自动释放旧资源。vector 中 operator= 的实现，只需要把 _start 指针换成这里的 _root 指针即可// 插入时，需要先找到空位置
bool insert(const K& key) {
// 插入时为空树
if (_root == nullptr) {
_root = new Node(key);
return true;
}
// 不是空树时
Node* parent = nullptr;
Node* curNode = _root;
while (curNode != nullptr) {
if (key > curNode->_key) {
parent = curNode;
curNode = curNode->_right;
} else if (key < curNode->_key) {
parent = curNode;
curNode = curNode->_left;
} else {
return false;
}
}
// 走完循环 curNode 找到了可以插入的位置
// 但要插入结点，必须修改父节点的指针，父节点并不知道 key 是比自己大还是自己小，只知道有一个结点需要插入
// 因此要再比较一次 curNode = new Node(key);
curNode = new Node(key);
if (key > parent->_key)
parent->_right = curNode;
else
parent->_left = curNode;
return true;
}
详细讲解（迭代插入逻辑）：
_root == nullptr，直接把根设为新节点（new Node(key)）。_root 向下查找插入位置：
curNode 跟随，parent 保存其父节点（因为当 curNode 为 nullptr 时需要把新节点挂到 parent）。key > curNode->_key，curNode 沿右子树移动；key < curNode->_key 时，curNode 沿左子树移动。key == curNode->_key，返回 false（二叉搜索树默认不允许重复键）。curNode 走到 nullptr（找到空位）后，代表 curNode 已找到合适的可以插入的位置。new Node(key) 建节点
curNode 的父节点内的左右孩子指针，但父节点并不知道要插入的 key 比自己大还是自己小，只知道下面由位置可以插入，不知道插入到哪个位置key 与 parent->_key 的比较把它接为左/右子节点。
key > parent->_key → 插到右边 (parent->_right = newNode)key < parent->_key → 插到左边 (parent->_left = newNode)curNode == nullptr 的地方。curNode，必须通过 parent 去改指针。parent 自己并不知道空位是在左边还是右边，所以需要再比较一次来决定。关键点与陷阱：
curNode 用来遍历，parent 跟随；这是常见的迭代插入模式。parent 链入整棵树public:
bool insert_R(const K& key) {
return _insert_R(_root, key);
}
private:
bool _insert_R(Node*& root, const K& key) {
// 走到空的地方，可以开始插入了
// 这里可以记录父节点，修改父节点的指针完成插入。不过比较复杂，这里使用
if (root == nullptr) {
root = new Node(key);
return true;
}
if (key < root->_key)
return _insert_R(root->_left, key);
else if (key > root->_key)
return _insert_R(root->_right, key);
else
return false;
}
要点：
_insert_R 的参数是 Node*& root（对指针的引用），这使得当 root 为 nullptr 时可以直接写 root = new Node(key); 来修改父节点的指针，而不需要再记录父节点再通过父节点的比较完成结点的插入，简化了父指针的管理。key < root->_key 时，return _insert_R(root->_left, key) 递归去左子树中插入key > root->_key 时，return _insert_R(root->_right, key) 递归去右子树中插入== 时返回 false，键不允许重复递归与迭代的复杂度比较（两种方式相同）：
bool find(const K& key) const {
Node* curNode = _root;
while (curNode) {
if (key == curNode->_key)
return true;
else if (key > curNode->_key)
curNode = curNode->_right;
else
curNode = curNode->_left;
}
// 循环结束时，循环内没有返回，代表没有找到，返回 false
return false;
}
curNode = _root，curNode从根节点出发开始找，按照二叉搜索树的性质查找即可curNode 表示当前结点，curNode 的移动结合了二叉搜树的性质：
key == curNode->_key 时，成功，返回 truekey > curNode->_key 时，curNode 去右子树查找key < curNode->_key 时，curNode 去左子树查找falsepublic:
bool find_R(const K& key) const {
return _find_R(_root, key);
}
private:
bool _find_R(const Node* root, const K& key) const {
if (root == nullptr)
return false;
if (key < root->_key)
return _find_R(root->_left, key);
else if (key > root->_key)
return _find_R(root->_right, key);
// 不大于，不小于 表明查找成功
else
return true;
}
key > 当前节点的_key 时，递归去右子树查找key < 当前节点的_key 时，递归去左子树查找trueconst Node* 保证不会修改树。由二叉搜索树的性质可得，对二叉搜索树进行中序遍历，可以得到升序序列
中序遍历可以用于升序打印 BST 中的键。代码如下：
public:
void Inorder() const {
_Inorder(_root);
printf("\n");
}
private:
void _Inorder(Node* root = _root) const {
if (root == nullptr) {
return;
}
_Inorder(root->_left);
cout << root->_key << " ";
_Inorder(root->_right);
}
要点：
_Inorder 是典型的递归中序：左 - 根 - 右。_Inorder 写成 void _Inorder(Node* root = _root) const，默认参数指向成员 _root，调用 Inorder() 默认从根节点开始遍历bool erase(const K& key) {
Node* parent = nullptr;
Node* curNode = _root;
// _root 为空时，进不去 while 循环，会直接 return false
while (curNode) {
// 先找要被删除的节点
if (key > curNode->_key) {
parent = curNode;
curNode = curNode->_right;
} else if (key < curNode->_key) {
parent = curNode;
curNode = curNode->_left;
}
// 找到了，找到了，删除分为三种情况
else {
// ... 删除的逻辑
}
}
// 没找到
return false;
}
// 找到后的删除逻辑
else {
// 情况一
// curNode 的左为空
if (curNode->_left == nullptr) {
// 特殊情况，左为空且 curNode 为_root
if (curNode == _root)
_root = curNode->_right;
// 托孤，需要知道孤儿 应该成为 父节点的左子树还是右子树，需要先找孤儿在左右那个子树
// 孤儿在左子树
else if (curNode == parent->_left)
parent->_left = curNode->_right;
// 孤儿在右子树
else
parent->_right = curNode->_right;
delete curNode;
return true;
}
// 情况二 ...
// 情况三 ...
return true;
}
curNode->_left == nullptr）：
_root = curNode->_right;curNode 是父节点的左/右孩子，把父指针指向结点 curNode->_right（托孤），再 delete curNode。// 找到后的删除逻辑
else {
// 情况一 ...
// 情况二 ...
// curNode 的右为空
else if (curNode->_right == nullptr) {
if (curNode == _root)
_root = curNode->_left;
// 托孤
// 当前结点是父的左节点
else if (curNode == parent->_left)
parent->_left = curNode->_left;
// 当前结点是父的右节点
else
parent->_right = curNode->_left;
delete curNode;
return true;
}
// 情况三 ...
return true;
}
curNode->_right == nullptr）：
_root = curNode->_left;curNode 是父节点的左/右孩子，把父指针指向结点 curNode->_left（托孤），再 delete curNode。情况三的删除逻辑，替换法
需要找左子树中最大的、或右子树中最小的替换当前要被删除的结点
这里找左子树中最大的结点
// 找到后的删除逻辑
else {
// 情况一 ...
// 情况二 ...
// 情况三 ...
// curNode 的左右都不为空，需要在树中找一个结点替换 curNode
else {
// 找左子树中最大的结点
Node* maxNode = curNode->_left;
Node* maxParent = curNode;
// 有可能进不去 while 循环，对应于删除时的 else 条件
// 进不去 while 时，此时 maxNode 初始就是左子树的最大结点，parent 和 curNode 重合
while (maxNode->_right != nullptr) {
maxParent = maxNode;
maxNode = maxNode->_right;
}
// 循环结束后，maxNode 为左子树中最大的结点
curNode->_key = maxNode->_key;
// 替换值
// 左子树的最大结点一定没有右孩子，但可能有左孩子
// maxNode 可能是 Parent 的右孩子，且 maxNode 可能有左孩子
if (maxNode == maxParent->_right)
maxParent->_right = maxNode->_left;
// maxNode 也可能是 Parent 的左孩子，且 maxNode 可能有左孩子
else {
// maxNode 是 curNode->_left，此时 pareng->_left 就是 maxNode
maxParent->_left = maxNode->_left;
}
delete maxNode;
}
return true;
}
maxNode 替换 curNode（即向左一次再一路向右走到最右）。maxNode 及其父 maxParent 后， curNode->_key = maxNode->_key 替换 curNode 中的值，然后把 maxNode 从树上摘除：
maxNode 是左子树的最大值，因此 maxNode一定没有右孩子，但可能会有左孩子，左孩子要挂回 maxParentmaxNode 既可能是 maxParent 的左节点，也可能是 maxParent 的右节点// 左子树的最大结点一定没有右孩子，但可能有左孩子
// maxNode 可能是 Parent 的右孩子，且 maxNode 可能有左孩子
if (maxNode == maxParent->_right) {
maxParent->_right = maxNode->_left; // 托孤
}
// maxNode 也可能是 Parent 的左孩子，且 maxNode 可能有左孩子
else {
// maxNode 是 curNode->_left，此时 pareng->_left 就是 maxNode
maxParent->_left = maxNode->_left; // 托孤
}
delete maxNode;
bool erase(const K& key) {
Node* parent = nullptr;
Node* curNode = _root;
// _root 为空时，进不去 while 循环，会直接 return false
while (curNode) {
// 先找要被删除的节点
if (key > curNode->_key) {
parent = curNode;
curNode = curNode->_right;
} else if (key < curNode->_key) {
parent = curNode;
curNode = curNode->_left;
}
// 找到了，找到了，删除分为三种情况
else {
// curNode 的左为空
if (curNode->_left == nullptr) {
// 特殊情况，左为空且 curNode 为_root
if (curNode == _root)
_root = curNode->_right;
// 托孤，需要知道孤儿 应该称为 父节点的左子树还是右子树
// 需要先找孤儿在左右那个子树
// 孤儿在左子树
else if (curNode == parent->_left)
parent->_left = curNode->_right;
// 孤儿在左子树
else
parent->_right = curNode->_right;
delete curNode;
return true;
}
// curNode 的右为空
else if (curNode->_right == nullptr) {
if (curNode == _root)
_root = curNode->_left;
// 托孤
// 当前结点是父的左节点
else if (curNode == parent->_left)
parent->_left = curNode->_left;
// 当前结点是父的右节点
else
parent->_right = curNode->_left;
delete curNode;
return true;
}
// curNode 的左右都不为空，需要在树中找一个结点替换 curNode
else {
// 需要找左子树中最大的、或右子树中最小的替换当前结点
// 二叉搜索树中，子树的最大结点，是树中最右边的结点
// 子树的最小结点，是树中最左边的结点
// 这里找左子树中最大的结点
Node* maxNode = curNode->_left;
Node* maxParent = curNode;
// 有可能进不去 while 循环，对应于删除时的 else 条件
// 进不去 while 时，此时 maxNode 初始就是左子树的最大结点，parent 和 curNode 重合
while (maxNode->_right != nullptr) {
maxParent = maxNode;
maxNode = maxNode->_right;
}
// 循环结束后，maxNode 为左子树中最大的结点
curNode->_key = maxNode->_key;
// 替换值
// 左子树的最大结点一定没有右孩子，但可能有左孩子
// maxNode 可能是 Parent 的右孩子，且 maxNode 可能有左孩子
if (maxNode == maxParent->_right)
maxParent->_right = maxNode->_left;
// maxNode 也可能是 Parent 的左孩子，且 maxNode 可能有左孩子
else {
// maxNode 是 curNode->_left，此时 pareng->_left 就是 maxNode
maxParent->_left = maxNode->_left;
}
delete maxNode;
}
return true;
}
}
return false;
}
左子树为空（curNode->_left == nullptr）：
_root = curNode->_right;否则根据 curNode 是父节点的左/右孩子，把父指针指向 curNode->_right（托孤），再 delete curNode。
这包含了叶子节点（左右都空）和只有右孩子的情况（因为左空且右可能为空或非空）。
右子树为空（curNode->_right == nullptr）：
_root = curNode->_left;curNode 是父节点的左/右孩子，把父指针指向 curNode->_left（托孤），再 delete curNode。左右子树皆非空：
本代码选择用左子树的最大节点 maxNode 替换 curNode（即向左一次再一路向右走到最右）。
找到 maxNode 及其父 maxParent 后， curNode->_key = maxNode->_key 替换 curNode 中的值，然后把 maxNode 从树上摘除：
maxNode 是左子树的最大值，因此 maxNode一定没有右孩子，但可能会有左孩子，左孩子要挂回 maxParentmaxNode 既可能是 maxParent 的左节点，也可能是 maxParent 的右节点托孤的代码：
托孤需要确认孤儿结点是在 parent 的左子树还是右子树，正确托孤后释放结点
while 循环结束后，代表三种情况中都未完成删除，返回 false
// 左子树的最大结点一定没有右孩子，但可能有左孩子
// maxNode 可能是 Parent 的右孩子，且 maxNode 可能有左孩子
if (maxNode == maxParent->_right) {
maxParent->_right = maxNode->_left; // 托孤
}
// maxNode 也可能是 Parent 的左孩子，且 maxNode 可能有左孩子
else {
// maxNode 是 curNode->_left，此时 pareng->_left 就是 maxNode
maxParent->_left = maxNode->_left; // 托孤
}
delete maxNode;
完整代码：
public:
bool erase_R(const K& key) {
return _erase_R(_root, key);
}
private:
bool _erase_R(Node*& root, const K& key) {
if (root == nullptr)
return false;
if (key > root->_key)
return _erase_R(root->_right, key);
else if (key < root->_key)
return _erase_R(root->_left, key);
// 相等时要删除
else {
Node* delNode = root;
// 1. curNode 左为空
if (root->_left == nullptr) {
root = root->_right;
}
// 2. curNode 右为空
else if (root->_right == nullptr) {
root = root->_left;
}
// 3. curNode 左右都不为空
else {
// 找左子树中最大的结点
Node* maxNode = root->_left;
while (maxNode->_right) {
maxNode = maxNode->_right;
}
std::swap(maxNode->_key, root->_key);
// 交换过后，原来的 maxNode 是左子树中最大的结点，因此其右子树一定为空
// 再去左子树中删除一遍
return _erase_R(root->_left, key);
}
delete delNode;
return true;
}
}
代码中查找的逻辑依然需要：
root == nullptr 时，返回 falsekey > root->_key 时，递归去右子树中查找key < root->_key 时，递归去左子树中查找else 代表相等，查找到了要被删除的结点bool _erase_R(Node*& root, const K& key) {
if (root == nullptr)
return false;
if (key > root->_key)
return _erase_R(root->_right, key);
else if (key < root->_key)
return _erase_R(root->_left, key);
// 相等时要删除
else {
// ...
}
}
else 中的删除代码：
// 相等时要删除
else {
Node* delNode = root;
// 这里 写成 curNode 是为了和迭代删除法的形式匹配
// 1. curNode 左为空
if (root->_left == nullptr) {
root = root->_right;
}
// 2. curNode 右为空
else if (root->_right == nullptr) {
root = root->_left;
}
// 3. curNode 左右都不为空
else {
// 找左子树中最大的结点
Node* maxNode = root->_left;
while (maxNode->_right) {
maxNode = maxNode->_right;
}
std::swap(maxNode->_key, root->_key);
// 交换过后，原来的 maxNode 是左子树中最大的结点，因此其右子树一定为空
// 再去左子树中删除一遍
return _erase_R(root->_left, key);
}
delete delNode;
return true;
}
Node*& root 是对结点指针的直接引用，使得当我们把 root 指向 root->_right（或 _left）时，父节点相应的指针会被更新（递归中直接修改）。Node*& root 是对结点指针的直接引用，托孤时无需记录 parent 指针，可以直接对其修改
root 指向 root->_right（托孤），再 delete delNode。maxNode，交换值（swap），然后在左子树递归删除原来持有该值的那个节点。root 是要被删除的结点，但它有左右孩子，不能直接删。maxNode，把 root->_key 和 maxNode->_key 交换。maxNode 是左子树中最大的结点，所以它 不可能有右子树（因为再往右就超过它了）。root->_key 已经被换成了 maxNode->_key，那么树里相当于有两个相同的 key。root->_left 去 继续删除 key。maxNode，并用情况 1 或 2 把它删掉。parent。结点数为 N 的二叉搜索树，最多查找高度次。对于随机插入的平衡树平均 h = O(log n)；最坏情况下 h = O(n)。
log2 N综合而言，⼆叉搜索树增删查改时间复杂度为： O(N)
那么这样的效率显然是⽆法满⾜我们需求的，后续会学习**⼆叉搜索树的变形**，平衡⼆叉搜索树 AVL 树和红⿊树，才能适⽤于我们在内存中存储和搜索数据高性能需求。
⼆分查找也可以实现 O(log2 N) 级别的查找效率，但是**⼆分查找有两⼤缺陷**：
// 二叉搜索树
template<class K>
struct BSTreeNode {
// typedef BSTreeNode<K> Node;
BSTreeNode(const K& key) : _left(nullptr), _right(nullptr), _key(key) {}
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
};
template<typename K>
class BSTree {
typedef BSTreeNode<K> Node;
public:
BSTree() : _root(nullptr) {}
BSTree(const BSTree<K>& tree) : _root(nullptr) { _root = Copy(tree._root); }
// 现在写法的赋值
// t2 = t1
BSTree<K>& operator=(BSTree<K> tmp) {
std::swap(_root, tmp._root);
return *this;
}
~BSTree() { Destroy(_root); }
// 插入时，找到一个空位置插入即可 默认插入的元素不能重复
bool insert(const K& key) {
// 插入时为空树
if (_root == nullptr) {
_root = new Node(key);
return true;
}
// 不是空树时
Node* parent = nullptr;
Node* curNode = _root;
while (curNode != nullptr) {
if (key > curNode->_key) {
parent = curNode;
curNode = curNode->_right;
} else if (key < curNode->_key) {
parent = curNode;
curNode = curNode->_left;
} else {
return false;
}
}
// 走到这里，意味着 curNode 已经找到了位置，此时 curNode 为 nullptr
// parent 为 curNode 的父节点
// curNode 为 结点指针的拷贝，修改 curNode 不能修改结点指针的指向
// 走完循环 curNode 找到了可以插入的位置
// 但要插入结点，必须修改父节点的指针，父节点并不知道 key 是比自己大还是自己小，只知道下面可以插
// 因此要再比较一次 curNode = new Node(key);
curNode = new Node(key);
if (key > parent->_key) {
parent->_right = curNode;
} else
parent->_left = curNode;
return true;
// key 不可能等于 parent->_key 否则上面的循环就是错误的
/*else { return false; }*/
}
void Inorder() const {
_Inorder(_root);
printf("\n");
}
bool find(const K& key) const {
Node* curNode = _root;
while (curNode) {
if (key == curNode->_key)
return true;
else if (key > curNode->_key)
curNode = curNode->_right;
else
curNode = curNode->_left;
}
return false;
}
// 这里不能用引用代替指针，因为指针可以改变指向，引用一旦绑定，指向不可修改
bool erase(const K& key) {
Node* parent = nullptr;
Node* curNode = _root;
// _root 为空时，进不去 while 循环，会直接 return false
while (curNode) {
// 先找要被删除的节点
if (key > curNode->_key) {
parent = curNode;
curNode = curNode->_right;
} else if (key < curNode->_key) {
parent = curNode;
curNode = curNode->_left;
}
// 找到了，找到了，删除分为三种情况
else {
// curNode 的左为空
if (curNode->_left == nullptr) {
// 特殊情况，左为空且 curNode 为_root
if (curNode == _root)
_root = curNode->_right;
// 托孤，需要知道孤儿 应该称为 父节点的左子树还是右子树
// 需要先找孤儿在左右那个子树
// 孤儿在左子树
else if (curNode == parent->_left)
parent->_left = curNode->_right;
// 孤儿在左子树
else
parent->_right = curNode->_right;
delete curNode;
return true;
}
// curNode 的右为空
else if (curNode->_right == nullptr) {
if (curNode == _root)
_root = curNode->_left;
// 托孤
// 当前结点是父的左节点
else if (curNode == parent->_left)
parent->_left = curNode->_left;
// 当前结点是父的右节点
else
parent->_right = curNode->_left;
delete curNode;
return true;
}
// curNode 的左右都不为空，需要在树中找一个结点替换 curNode
else {
// 需要找左子树中最大的、或右子树中最小的替换当前结点
// 二叉搜索树中，子树的最大结点，是树中最右边的结点
// 子树的最小结点，是树中最左边的结点
// 这里找左子树中最大的结点
Node* maxNode = curNode->_left;
Node* maxParent = curNode;
// 有可能进不去 while 循环，对应于删除时的 else 条件
// 进不去 while 时，此时 maxNode 初始就是左子树的最大结点，parent 和 curNode 重合
while (maxNode->_right != nullptr) {
maxParent = maxNode;
maxNode = maxNode->_right;
}
// 循环结束后，maxNode 为左子树中最大的结点
curNode->_key = maxNode->_key;
// 替换值
// 左子树的最大结点一定没有右孩子，但可能有左孩子
// maxNode 可能是 Parent 的右孩子，且 maxNode 可能有左孩子
if (maxNode == maxParent->_right)
maxParent->_right = maxNode->_left;
// maxNode 也可能是 Parent 的左孩子，且 maxNode 可能有左孩子
else {
// maxNode 是 curNode->_left，此时 pareng->_left 就是 maxNode
maxParent->_left = maxNode->_left;
}
delete maxNode;
// Node* maxNode = curNode->_left;
// Node* maxParent = curNode;
// while (maxNode->_right != nullptr) {
// maxParent = maxNode;
// maxNode = maxNode->_right;
// }
// 循环结束后，maxNode 为左子树中最大的结点
// std::swap(maxNode->_key, curNode->_key);
// delete maxNode;
// maxParent->_right = nullptr; // 错误逻辑
}
return true;
}
}
return false;
}
// find 函数的递归版本
// 写了一个子函数，因为递归需要用到 Private 成员_root，来控制递归子树的分支
// 如果不写子函数，需要对外提供一个 getRoot 供调用者使用
bool find_R(const K& key) const {
return _find_R(_root, key);
}
bool insert_R(const K& key) {
return _insert_R(_root, key);
}
bool erase_R(const K& key) {
return _erase_R(_root, key);
}
private:
Node* Copy(Node* root) {
if (root == nullptr)
return nullptr;
else {
Node* newRoot = new Node(root->_key);
// 分别递归拷贝 左右子树，拷贝完后，递归回去连接
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;
root = nullptr;
}
void _Inorder(Node* root = _root) const {
if (root == nullptr) {
return;
}
_Inorder(root->_left);
cout << root->_key << " ";
_Inorder(root->_right);
}
bool _find_R(const Node* root, const K& key) const {
if (root == nullptr)
return false;
if (key < root->_key)
return _find_R(root->_left, key);
else if (key > root->_key)
return _find_R(root->_right, key);
// 不 < 不 > 表明查找成功
else
return true;
}
// 这里参数 root 加引用，修改指针
bool _insert_R(Node*& root, const K& key) {
// 走到空的地方，可以开始插入了
// 这里可以记录父节点，修改父节点的指针完成插入。不过比较复杂，这里使用
if (root == nullptr) {
root = new Node(key);
return true;
}
if (key < root->_key)
return _insert_R(root->_left, key);
else if (key > root->_key)
return _insert_R(root->_right, key);
else
return false;
}
bool _erase_R(Node*& root, const K& key) {
if (root == nullptr)
return false;
if (key > root->_key)
return _erase_R(root->_right, key);
else if (key < root->_key)
return _erase_R(root->_left, key);
// 相等时要删除
else {
Node* delNode = root;
// 这里的 root 等价于 curNode，写成 curNode 是为了和迭代删除法的形式匹配
// 1. curNode 左为空
if (root->_left == nullptr) {
root = root->_right;
}
// 2. curNode 右为空
else if (root->_right == nullptr) {
root = root->_left;
}
// 3. curNode 左右都不为空
else {
// 找左子树中最大的结点
Node* maxNode = root->_left;
while (maxNode->_right) {
maxNode = maxNode->_right;
}
std::swap(maxNode->_key, root->_key);
// 交换过后，原来的 maxNode 是左子树中最大的结点，因此其右子树一定为空
// 再去左子树中删除一遍
return _erase_R(root->_left, key);
// return _erase_R(maxNode, key); // 不能这么写
}
delete delNode;
return true;
}
}
private:
Node* _root;
};
通过本文的实现，我们完整梳理了二叉搜索树的设计与核心操作：
二叉搜索树作为最基础的树形数据结构，是理解 AVL 树、红黑树等平衡二叉树 的起点。掌握 BST 的实现，不仅能加深对 STL 底层的理解，也能为后续学习更复杂的数据结构打下坚实的基础。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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