【C++】二叉搜索树（二叉查找树、二叉排序树）详解

前进之路 · 2025-3-12 23:24:06

一、概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

从二又搜索树的定义可知，它的条件是二叉树，而且接纳了递归的方式进行定义，它的结点间满意一个偏序关系，左子树根结点的值定比父结点小，右子树根结点的值肯定比父结点大。
正如它的名字所说，构造这样一棵树的目的是为了提高搜索的速率，假如对二叉搜索树进行中序遍历，我们可以发现，得到的序列是个递增序列。

递归：
(1) 左右子树本身是二叉搜索树

无论从哪个节点开始，只需考察：

当前节点的值是否满意与左子树和右子树的比力关系；
然后递归到左右子树去判断它们是否分别满意二叉搜索树的性质。

  这种对左右子树重复性质的要求是递归定义的直接体现。
  (2) 以根节点为核心的分层定义

+ 当前树的性质由当前根节点与左右子树的性质共同决定； + 左子树和右子树本身可以被视为规模更小的二叉搜索树，这种嵌套结构直接表明递归定义的存在。  二、定义

//树节点的结构体
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;

复制代码

原因 1: 明确默认构造需求
假如没有声明任何构造函数，编译器会自动生成默认构造函数，且会将 _root 初始化为 nullptr（因为你用了类内初始化 Node* _root = nullptr;
）。但假如你显式定义了其他构造函数（比如拷贝构造、赋值重载），编译器将不再自动生成默认构造函数。为制止丢失默认构造函数的功能，就必要显式使用 = default;。
原因 2: 保持代码的可读性与语义
通过显式声明 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)
//
// {
// Destory(_root);//清空tree1树里的节点，树还在，但是空树
// _root = Copy(t._root);//把tree2里的节点深拷贝到tree1
// }
// return *this;
//返回tree1；
//}

复制代码

赋值重载swap写法详解

这种写法很高效，节省资源，肯定要掌握！！！
我们通过一个详细的例子来说明写法二（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 这个节点及其子树（假如有）。

变量状态：

this->_root：保持指向 10，即 tree2 的根节点。
t：将在函数结束时烧毁，t._root 指向 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 的内存已被开释？

开释的只是原树的节点，树本身仍然存在

调用 Destory(_root) 时，仅开释了 tree1 原有的节点内存，但 tree1 本身（即当前对象）仍然存在。_root 只是一个指针成员变量，而非整个 tree1 对象的内存。
例如：

假如 tree1 本来有数据，它们会被 Destory 清空，变成一个空树（_root == nullptr）。
然后通过 Copy(t._root)，重新构造 tree1 的数据结构，使其变得与 tree2 相同。

最终，tree1 并没有被烧毁，而是被重修。

返回值的意义：支持链式赋值

返回 *this 是赋值运算符的标准筹划，用于支持链式赋值。链式赋值答应连续的赋值操纵，如：

BSTree<int> a, b, c;
a = b = c;

复制代码

流程：
- b = c 实行后，返回 b 的引用。
- 然后将 b 的引用作为参数传递给 a = b。

假如不返回 *this，链式赋值将无法工作。

为什么不是返回烧毁的内容？

Destory(_root) 只是清空了树的原有数据，tree1 的对象本身还存在。返回 *this 是返回当前对象的引用，表示赋值操纵完成，当前对象的状态被更新为目的对象的状态。
例如：

BSTree<int> tree1, tree2;
// 假设 tree1 有旧的节点，tree2 是目标树
tree1 = tree2;

复制代码

在 tree1 = tree2 过程中：

清空 tree1 的原节点，但 tree1 本身还在。
将 tree2 的数据复制到 tree1。
返回 tree1 的引用，表示 tree1 如今是 tree2 的深拷贝。

示意图说明

初始状态：

tree1：包罗若干节点，_root 指向一棵树。
tree2：包罗若干节点，_root 指向另一棵树。

操纵后：

Destory(_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()
{
Destory(_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() 的方式保持不变，代码改动对外透明。这种筹划符合模块化筹划的思想。
三、查找、插入

1.查找

从根开始比力，查找，比根大则往右边走查找，比根小则往左边走查找。
最多查找高度次，走到到空，还没找到，这个值不存在

别的必要注意的是
①最大元素肯定是在树的最右分枝的端结点上。
②最小元素肯定是在树的最左分枝的端结点上。

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

复制代码

2.插入

特别情况处理：
假如树是空的（即 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情况——直接删除

将待删除节点的父节点指向待删除节点的孩子节点

d情况（要删除的结点有左、右孩子结点） ——替换法删除

先假删除根节点8.
我们的目的依然是要保证删除结点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个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二
叉搜索树的深度的函数，即结点越深，则比力次数越多。
但对于同一个关键码集合，假如各关键码插入的次序差别，大概得到差别结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树(或者靠近完全二叉树)，其平均比力次数为： l o g 2 N log_2 N log2N
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比力次数为： N 2 \frac{N}{2} 2N
六、应用——KV模子

K模子：K模子即只有key作为关键码，结构中只必要存储Key即可，关键码即为必要搜索到
的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
KV模子：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方
式在现实生活中非常常见：
比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英
文单词与其对应的中文<word, chinese>就构成一种键值对；
再比如统计单词次数，统计乐成后，给定单词就可快速找到其出现的次数，单词与其出
现次数就是<word, count>就构成一种键值对。
统计次数

//统计词语出现的次数
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) // { // Destory(_root);//清空tree1树里的节点，树还在，但是空树 // _root = Copy(t._root);//把tree2里的节点深拷贝到tree1 // } // return *this;
//返回tree1； //} //析构 ~BSTree() { Destory(_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; //不是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(cosnt 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(const K & 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 Destory(Node* root) { if (root == nullptr) { return; } Destory(root->_left); Destory(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); } 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); } } }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和statue的区别

bool 和 status 的区别主要取决于上下文中的定义和使用方式。以下是它们之间的一些典型区别：

1. bool 是一种数据范例

描述: bool 是一种内置的布尔范例，用来表示逻辑上的真假值，取值范围是 true 或 false。
用途: 用于条件判断、布尔表达式、逻辑运算等。
常见场景:
- 判断条件是否建立。
- 返回是否乐成的标志，例如函数的实行结果。

示例:

bool isReady = true; // 表示某个条件成立
if (isReady) {
// 做某些事情
}

复制代码

2. 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) {
// 操作失败
}

复制代码

3. 典型区别
特性boolstatus范例内置范例通常是枚举或扩展范例取值范围仅有 true 和 false可以有多个值（如 SUCCESS, FAILURE）信息丰富度表示简朴的二元逻辑结果可以描述更复杂的状态可扩展性不可扩展易于扩展更多状态值

4. 选择依据

简朴的真假判断:
- 假如某个结果仅需表示 “是或否”（例如操纵是否乐成），选择 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;
}

复制代码

		自动登录	找回密码
密码			立即注册

【C++】二叉搜索树（二叉查找树、二叉排序树）详解

本帖子中包含更多资源

0 个回复

快速回复

楼主热帖

标签云

浏览过的版块