【C++修仙录03】进阶篇：二叉搜索树
嗨~大家好，这里是春栀怡铃声的博客~
“做你害怕的事，然后发现，不过如此~”
目录
二叉搜索树的定义
二叉搜索树（Binary Search Tree），又称二叉查找树或二叉排序树。是一棵具有下列性质的二叉树：
-
若它的左子树不为空，则左子树上所有节点的值均小于它的根节点的值。
-
若它的右子树不为空，则右子树上所有节点的值均大于它的根节点的值。
-
它的左、右子树本身也分别都是二叉搜索树。
-
（通常情况下）树中没有键值相等的节点。
一句话总结口诀： “左小、右大、根中间”。
想象一下我们玩“猜数字”游戏，范围是 1 到 100。 你猜“50”，我告诉你“太小了”。这时候你绝对不会再去猜 1 到 50 之间的数字，而是直接去猜 75，直接把一半的选项淘汰掉。 二叉搜索树就是把这个“猜数字”的过程实体化了。 每一个节点就是一个裁判，当你拿着一个数字来找它时，它会告诉你：“比我小，去我的左边找；比我大，去我的右边找。” 这种每次都能排除一半选项的机制，就是它效率极高的秘密。
实现二叉搜索树
实现节点
template<class K>
struct BTSNode
{
BTSNode(const K& key)
:_key(key)
,_left(nullptr)
,_right(nullptr)
{ }
K _key;
BTSNode<K>* _left;
BTSNode<K>* _right;
};实现二叉树的节点，将节点设置成stuct类 默认节点的内容都可以类外可以访问。
需要一个指向其他节点的左指针，需要拎一个指向其他指针的右指针
初始化列表来初始化节点储存的值、左指针、右指针
二叉搜索树的基本框架
template<class K>
class BSTree
{
typedef BTSNode<K> BTNode;
public:
private:
BTNode* _root=nullptr;
};
public 之后实现的是下面我们要实现的函数
private 中存放的是二叉搜索树的根节点
增加数据
typedef BTSNode<K> BTNode;
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new BTNode(key);
return true;
}
BTNode* cur = _root;
BTNode* parent = nullptr;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
return false;
}
if (parent->_key > key)
parent->_left = new BTNode(key);
else
parent->_right = new BTNode(key);
return true;
}如果在二叉搜索树插入数据时，二叉搜索树是一个空树，说明新插入的这个节点将作为根节点
二叉搜索树不是空树，我们需要定义2个节点指针cur 和 parent
cur 用来遍历来找到适合新插入节点的位置，parent 用来让原有二叉搜索树和新节点产生联系
接下来我们看cur 怎么遍历
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
return false;
}
cur起始位置从根节点开始
如果cur的值大于插入的值，那么插入的位置应该在根节点的左子树，先让parent 走到cur 的位置，然后让cur=cur->left
如果cur的值小于插入的值，那么插入的位置应该在根节点的右子树，先让parent 走到cur 的位置，然后让cur=cur->right
在这里我是实现的是没有相同值的二叉搜索树，当检测到新插入的值等于cur 时，返回false .
cur 走完这个遍历后，cur就来到了新节点要插入的位置了，此时要继续判断是父节点的左指针指向新节点 还是右指针指向新节点
if (parent->_key > key)
parent->_left = new BTNode(key);
else
parent->_right = new BTNode(key);
如果父节点的值大于新插入的结点的值，父节点的左指针指向新节点
如果父节点的值小于新插入的结点的值，父节点的右指针指向新节点
最后返回true
查找数据
bool Find(const K& key)
{
BTNode* cur = _root;
while (cur)
{
if (cur->_key > key)
{
cur = cur->_left;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else
return true;
}
return false;
}通过遍历cur 来查找
cur起始位置从根节点开始
如果cur的值大于插入的值，那么插入的位置应该在根节点的左子树，让cur=cur->left
如果cur的值小于插入的值，那么插入的位置应该在根节点的右子树，让cur=cur->right
如果cur 的值等于 要查找的值，说明已经找到了。
完成while 循环还未找到，返回false
删除数据
bool Erase(const K& key)
{
BTNode* cur = _root;
BTNode* parent = nullptr;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
else if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else
{
BTNode* replaceParent = cur;
BTNode* replace = cur->_right;
while (replace->_left)
{
replaceParent = replace;
replace = replace->_left;
}
cur->_key = replace->_key;
if (replaceParent->_left == replace)
replaceParent->_left = replace->_right;
else
replaceParent->_right = replace->_right;
delete replace;
}
return true;
}
}
return false;
}删除节点的方法是：
通过while 循环先找到该节点位置。
如果出了循环还未找到，直接返回false即可
cur起始位置从根节点开始
如果cur的值大于插入的值，那么要删除的位置应该在根节点的左子树，先让parent 走到cur 的位置，然后让cur=cur->left
如果cur的值小于插入的值，那么要删除的位置应该在根节点的右子树，先让parent 走到cur 的位置，然后让cur=cur->right
删除节点分为2类：
1.只有一个孩子的节点和叶子节点（没有孩子）
if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}else
{
parent->_right = cur->_left;
}
}
delete cur;
}else if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}else
{
parent->_right = cur->_right;
}
}
delete cur;
}
删除只有一个孩子的节点，
我们以右指针指向空 画图示例：
结合示例来解析代码
首先我们要判断这个要删除的节点是不是根节点
如果是，需要判断要删除的节点的左右指针哪个指向空
if (cur == _root)
{
_root = cur->_left;
}
不是根节点
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}else
{
parent->_right = cur->_left;
}
}
delete cur;
左指针为空和上面的方式相同
2.有2个孩子的节点
else
{
BTNode* replaceParent = cur;
BTNode* replace = cur->_right;
while (replace->_left)
{
replaceParent = replace;
replace = replace->_left;
}
cur->_key = replace->_key;
if (replaceParent->_left == replace)
replaceParent->_left = replace->_right;
else
replaceParent->_right = replace->_right;
delete replace;
}采用替换法删除N
N左子树的值最大结点R(最右结点)或者N右子树的值最小结点R(最左结点)替代N，
我们这里采用 N右子树的值最小结点R(最左结点)替代N
循环找到右子树中最左的的节点。
while (replace->_left)
{
replaceParent = replace;
replace = replace->_left;
}
替换
cur->_key = replace->_key;
拷贝构造
BSTree(BSTree<K>&t )
{
_root=Copy(t._root);
}
BTNode* Copy(BTNode* root)
{
if (root == nullptr)
return nullptr;
BTNode* newRoot=new BTNode(root->key);
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
return newRoot;
}此处是深拷贝，需要借助函数实现，并且采用递归的方式
因为是传参 传的是指向节点的指针，我们给的形参也必须是 BTNode*
BTNode* newRoot=new BTNode(root->key);
运算符重载
BSTree& operator=(BSTree tmp)
{
swap(_root, tmp._root);
return *this;
}简单来说，它的作用是把另一个二叉搜索树（右值）的内容安全地赋值给当前树（左值），同时自动清理当前树原本的旧数据。
以下是它的核心运作原理和分步实现细节：
1. 核心奥秘：传值传参 (BSTree tmp)
注意参数列表中，tmp 是按值传递 (Pass-by-value)，而不是按引用传递 (const BSTree& tmp)。
-
当你执行
tree1 = tree2;时，编译器会自动调用BSTree的拷贝构造函数。 -
这个拷贝构造函数会克隆一份
tree2的数据，并用这些数据生成一个局部的临时对象，也就是参数tmp。 -
此时，
tmp拥有了一棵和tree2一模一样的新树（深拷贝），而tree1还是原来的旧树。
2. (乾坤大挪移)：交换指针 (swap(_root, tmp._root))
进入函数体后，调用了 swap 函数。
-
这里仅仅交换了当前对象 (
this) 的根节点指针_root和临时对象tmp的根节点指针tmp._root。 -
交换后： 当前对象 (
this) 的_root指向了刚才拷贝出来的新树；而tmp的_root则指向了当前对象原本的“旧树”。
3. (借刀杀人)自动清理旧内存 (函数结束时)
当函数执行完毕准备 return 时，局部对象 tmp 会离开它的作用域，因此它的生命周期结束了。
-
编译器会自动调用
tmp的析构函数。 -
记住，刚才交换之后，
tmp此时手里拿着的是当前对象 (tree1) 的旧数据。 -
所以，
tmp销毁时，顺手就把你原来树里的那些不需要的旧节点内存全部释放干净了。
4. 完美收尾
返回当前对象的引用，这是为了支持连续赋值操作，例如 tree1 = tree2 = tree3;
析构函数
~BSTree()
{
Destory(_root);
_root = nullptr;
}
void Destory(BTNode* root)
{
if (root == nullptr)
return;
Destory(root->_left);
Destory(root->_right);
delete root;
}因为有深拷贝，所以我们的析构函数要手动实现
采用递归函数
别忘记将_root置为nullptr
中序遍历
public:
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(BTNode* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}利用递归完成中序遍历
中序遍历：左节点 根节点 右节点
需要注意的是我们的中序遍历直接写的话需要访问类的私有成员_root ,这样我们在类外面使用中序遍历就不能正常使用
所以我们设计1个
void InOrder()
{
_InOrder(_root);
cout << endl;
}
在类外使用中序遍历时 直接调用InOrder()
将 _InOrder(_root)函数规定成类的成员函数，可以访问_root ，相当于在InOrder() 中调用_InOrder()
而_InOrder() 实现方法是
void _InOrder(BTNode* root)
{
if (root == nullptr)
return;_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
如果root 为空，直接返回
采用递归的方法实现中序遍历
二叉树搜索的应用场景
key搜索场景
只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断key在不在。key的搜索场景实现的二叉搜索树支持增删查，但是不支持修改，修改key破坏搜索树结构了。
场景1：小区无人值守车库，小区车库买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌在不在系统中，在则抬杆，不在则提示非本小区车辆，无法进入。
场景2：检查⼀篇英文章单词拼写是否正确，将词库中所有单词放⼊二叉搜索树，读取文章中的单
词，查找是否在二叉搜索树中，不在则波浪线标红提示。
key/value搜索场景
每⼀个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value，增/删/查还是以key为关键字走二叉搜索树的规则进行比较，可以快速查找到key对应的value。key/value的搜索场景实现的二叉树搜索树支持修改，但是不支持修改key，修改key破坏搜索树性质了，可以修改value。
场景1：简单中英互译字典，树的结构中(结点)存储key(英文)和vlaue(中文)，搜索时输入英文，则同时查找到了英文对应的中文。
key/value二叉搜索树代码实现
namespace key_value
{
template<class K,class V>
struct BTSNode
{
BTSNode(const K& key,const V& value)
:_key(key)
,_value(value)
,_left(nullptr)
,_right(nullptr)
{ }
K _key;
V _value;
BTSNode<K,V>* _left;
BTSNode<K,V>* _right;
};
template<class K, class V>
class BSTree
{
typedef BTSNode<K,V> BTNode;
public:
BSTree() = default;
BSTree(BSTree<K,V>&t )
{
_root=Copy(t._root);
}
BSTree& operator=(BSTree tmp)
{
swap(_root, tmp._root);
return *this;
}
~BSTree()
{
Destory(_root);
_root = nullptr;
}
bool Insert(const K& key,const V& value)
{
if (_root == nullptr)
{
_root = new BTNode(key,value);
return true;
}
BTNode* cur = _root;
BTNode* parent = nullptr;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
return false;
}
if (parent->_key > key)
parent->_left = new BTNode(key,value);
else
parent->_right = new BTNode(key,value);
return true;
}
BTNode* Find(const K& key)
{
BTNode* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
bool Erase(const K& key)
{
BTNode* cur = _root;
BTNode* parent = nullptr;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
else if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else
{
BTNode* replaceParent = cur;
BTNode* replace = cur->_right;
while (replace->_left)
{
replaceParent = replace;
replace = replace->_left;
}
cur->_key = replace->_key;
if (replaceParent->_left == replace)
replaceParent->_left = replace->_right;
else
replaceParent->_right = replace->_right;
delete replace;
}
return true;
}
}
return false;
}
BTNode* Copy(BTNode* root)
{
if (root == nullptr)
return nullptr;
BTNode* newRoot=new BTNode(root->key);
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
return newRoot;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
void Destory(BTNode* root)
{
if (root == nullptr)
return;
Destory(root->_left);
Destory(root->_right);
delete root;
}
private:
void _InOrder(BTNode* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
private:
BTNode* _root=nullptr;
};
}BSTree() = default;
强制生成默认构造，因为在这段代码中已经有了拷贝构造，编译器就不会生成构造了，必须要强制生成默认构造
template<class K,class V>
struct BTSNode
{
BTSNode(const K& key,const V& value)
:_key(key)
,_value(value)
,_left(nullptr)
,_right(nullptr)
{ }
K _key;
V _value;
BTSNode<K,V>* _left;
BTSNode<K,V>* _right;
};新增加了一个值_value 每一个_key 对应一个_value
_value 不参与到具体函数的实现逻辑，只是一个外显的值
相当于投屏的显示器。
所以代码和之前实现二叉搜索树的基本逻辑相同，在插入时别忘了_value
new BTNode(key,value);
注意：
查找函数的返回类型改变，逻辑不变
BTNode* Find(const K& key)
{
BTNode* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}感谢花时间阅读这篇内容！
如果觉得有价值，欢迎点赞支持、收藏备用，或分享给同行。你的认可，是我持续输出高质量内容的最大动力。
我们下期再见喽！！！
更多推荐
13
0- 0
已为社区贡献10条内容
所有评论(0)