【二叉树进阶】搜索二叉树（递归+非递归两种版本详解）
前言
<font color = black>map和set特性需要先铺垫二叉搜索树，而二叉搜索树也是一种树形结构。
<font color = black>二叉搜索树的特性了解，有助于更好的理解map和set的特性。
<font color = black>二叉树中部分面试题稍微有点难度，在前面讲解大家不容易接受，且时间长容易忘。
<font color = black>有些OJ题使用C语言方式实现比较麻烦，比如有些地方要返回动态开辟的二维数组，非常麻烦。
因此本节用C++语言对二叉树部分进行收尾总结。
我们之前学的普通的二叉树其实意义不大，因为如果只是用二叉树来存储数据的话，还不如直接用链表或者顺序表等这些顺序结构。
那二叉树搜索树相对来说，就比较有意义了。
1. 二叉搜索树的概念
那什么是二叉搜索树呢，先来了解一下它的概念
<font color = blue>二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
<font color = blue>若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
<font color = blue>若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
<font color = blue>它的左右子树也分别为二叉搜索树（即它的每一棵子树也满足其左子树所有结点的值都小于根结点的值，右子树的所有结点的值大于根结点的值）
为什么又叫二叉排序树呢？
<font color = black>仔细观察我们会发现如果对一棵搜索二叉树进行中序遍历的话
其实就能得到一个结点值的升序序列。
那了解了搜索二叉树的概念，接下来我们就来手撕一个搜索二叉树。
2. 二叉搜索树的结构
首先我们来定义一下结点和搜索二叉树的结构
<font color = black>我们之前定义一个模板类，一般都喜欢用T（type），但是在这里比较喜欢用K（key）
2.1 结点结构
2.2 树结构
相信大家很容易都能看懂，那这里我就不详细解释了。
3. 插入操作（非递归）
接下来我们来实现一下向搜索二叉树中插入元素的操作。
3.1 思路分析
首先对于搜索二叉树来说，它的插入应该有插入成功和插入失败（因为搜索二叉树一般不允许出现重复元素）两种情况。
我们来分析一下
首先看插入成功的情况：
<font color = black>在搜索二叉树中，要插入一个元素时，如果可以 插入，那么它插入的位置一定是确定的。 举个栗子
那失败的情况呢？
<font color = black>比如，我们现在要插入一个13
当然，如果插入的是第一个结点，那就不需要比较了，直接让它成为根结点。
3.2 代码实现
那我们来写一下代码 
首先第一个插入的结点是比较特殊的，因为第一个要作为根结点：
<font color = black>那怎么判断是不是第一个插入的呢？ 🆗，插入第一个的时候，根结点是不是还是空的啊 所以
那其它情况呢？
<font color = black>那后续的插入，就需要我们从根结点开始比较大小去找到合适的位置插入了，思路上面已经讲过了，这里就直接写代码了
那现在问题来了，如何正确的插入key对应的结点并链接到搜索二叉树上？
<font color = black>大家看这样可以吗
🆗，这样写会存在两个问题： 第一个
<font color = black>这里的cur是一个函数里面的局部变量，函数调用结束，cur这个指针变量就被销毁了，销毁了不说，目前我们这样写是不是还会存在内存泄漏啊，cur被销毁了，但是它指向的空间还没释放。 那cur指向的空间不是属于这棵二叉树了嘛，不是最终可以随着搜索树的析构释放吗？ 🆗，你把key的结点赋给cur，就链接到树上了嘛，并没有
这就是第二个问题：
<font color = black>把结点给cur，并没有链接到树上。 还看这个例子
parent->left）的一个指针变量，相当于是parent->left的拷贝，把结点赋给它，并没有真正链接到13的左孩子上。
那怎么解决呢？
<font color = black>🆗，我们在cur不断向左或向右去找到过程中，记录它的父亲结点，最终cur走到正确的位置，把key的结点直接链接到父亲结点上就可以了 我们来修改一下
代码：
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
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;
}
}
//走到这里cur为空，就是key应该插入的位置
cur = new Node(key);
//链接
if (key < parent->_key)
parent->left = cur;
if (key > parent->_key)
parent->right = cur;
return true;
}实现好了，行不行呢？测试一下：
<font color = black>构建我们示例中的那棵树，看看结果一不一样：
3.3 中序遍历（测试用）
那我们写个中序遍历
<font color = black>二叉树的遍历我们在初阶已经学过，相信现在对于大家已经很简单了
_，现在补上了
那写好我就可以调了，但会有一个问题：
<font color = black>
那大家思考一下这里可不可以给缺省值？
<font color = black>缺省值给一个root不就行了。 🆗是不行的，因为缺省值必须是常量或者全局变量（但一般不用全局变量） 这个我们在C++的第一篇文章有提到，大家可以去复习。 **而且在参数列表其实根本拿不到成员变量root，因为访问非静态成员要用this指针，而this指针只能在成员函数内部使用，参数列表也不行。**
两个解决方法：
<font color = black>提供一个GetRoot的成员函数/方法，传参的时候通过该方法获取_root。 但C++里不喜欢这样 那其实有另外一种比较简便的方法，给InOrder函数再套一层（封装一下）
_InOrder变成私有的了
然后我们来测试一下
<font color = black>
4. 查找操作（非递归）
接着我们来看一下查找：
4.1 思路分析
<font color = black>那查找其实是比较简单的： 我们要查找某个结点，那就从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找，找到的话返回true
4.2 代码实现
写一下代码：
bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key < cur->_key)
{
cur = cur->_left;
}
else if (key > cur->_key)
{
cur = cur->_right;
}
else
{
return true;
}
}
return false;
}测试一下：
<font color = black>
5. 删除操作（非递归）-重难点
那如果要删除二叉搜索树中的某个结点，应该怎么处理呢？
5.1 情况分类及思路分析
首先查找元素是否在二叉搜索树中，如果不存在，则直接返回false， 否则要删除的结点可能分下面四种情况：
-
要删除的结点无孩子结点
<font color = black>比如：
-
要删除的结点只有右孩子结点，左为空
<font color = black>比如我们现在要删除6
-
要删除的结点只有左孩子结点，右为空
<font color = black>
-
要删除的结点有左、右孩子结点
<font color = black>
对于这种情况我们使用的方法叫做——替换法删除法/伪删除法：
<font color = black>
<font color = black>左子树的最大值
<font color = black>右子树的最小值
<font color = black>
以用7为例，怎么进行替换删除呢？
<font color = black>
那总结一下：
<font color = black>虽然上面我们分析了四种情况，但是我们说了第一种即被删除结点没有孩子的情况可以归到左为空或者右为空的情况里面。 所以总共有三种：
<font color = black>左为空
<font color = black>右为空 这两种都是托管，但注意具体的代码处理是不一样的，因为一个右为空，一个左为空。
<font color = black>左右都不为空 替换删除/伪删除法
5.2 代码实现
那下面写一下代码吧
首先我们得查找要删除的元素：
<font color = black>
那接下来就是实现删除的逻辑了
左为空或者右为空的删除其实比较好处理，托管给父亲节点即可
<font color = black>
最后来实现一下比较难搞的替换删除：
<font color = black>那我们上面说了这个替换结点可以是左树的最大结点（最右边的那个结点），也可以是右树的最小结点（最左边）。 那这里我选择右树的最小结点。 这里的替换删除分为两步： 第一步——找到右树最小结点，然后替换要删除的结点
nullptr吗？pminRight不会更新，那后面托管的时候就会对空指针解引用，所以这里初始值可以赋cur，即要进行删除的那个结点（伪删除）。Node* pminRight = cur;另外我们上面的那个例子pminRight的右子树上了，所以要去看minRight（即替换结点）在pminRight的那边。 所以补充完毕应该是这样的
但是呢，其实改到现在还有一个问题：
<font color = black>
问题出在哪里呢？
<font color = black>
我们来分析一下：
<font color = black>
那然后我们再来测试
<font color = black>
bool Erase(const K& key)
{
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
{
//key == cur->_key就是找到了，进行删除
//1.左为空
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (cur == parent->_left)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
delete cur;
}
//2.右为空
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (cur == parent->_left)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
}
delete cur;
}
else//左右都不为空
{
//这里选择右树的最小结点（最左边）替换
Node* pminRight = cur;
Node* minRight = cur->_left;
while (minRight->_left)
{
pminRight = minRight;
minRight = minRight->_left;
}
cur->_key = minRight->_key;
//删除替换结点
if (pminRight->_left = minRight)
{
pminRight->_left = minRight->_right;
}
else
{
pminRight->_right = minRight->_right;
}
delete minRight;
}
return true;
}
}
//找不到直接返回false
return false;
}那搜索二叉树主要的操作其实就这些，但是呢，我们上面都是用循环实现的，那搜索二叉树这里呢其实也可以用递归去搞，这三个操作的递归实现我们也有必要去学一下。
6. 查找（递归版本）
查找用递归要怎么写呢？
<font color = black>
6.2 思路分析
那具体怎么实现呢？ 我们来分析一下：
<font color = black>首先来回顾一下递归的思想： 它通常把一个大型复杂问题层层转化为一个与原问题相似的规模较小的问题来求解，每个子问题都可以进一步分解为更小的子问题，直到达到基本情况（终止条件），然后逐层返回结果，最终得到整个问题的解。 所以这里的思路是这样的： 查找嘛，那就从根结点开始，如果大于根结点的值，就转换为去右子树里面查找，如果小于根结点，就转换为去左子树查找，如果等于就直接返回；那对于子树也是这样，一步步转换为子问题。 如果最后都没找到，一直到空，那就返回false。
那我们写一下代码：
6.2 代码实现
这个没什么难度，我就直接上代码了：
bool FindR(const K& key)
{
return _FindR(_root, key);
}
bool _FindR(Node* root, const K& key)
{
if (root == nullptr)
return false;
if (key < root->_key)
{
return _FindR(root->_left, key);
}
else if (key > root->_key)
{
return _FindR(root->_right, key);
}
else
{
retrun true;
}
}试一下：
7. 插入（递归版本）
7.1 思路分析
那插入用递归怎么做呢？
<font color = black>那也是类似的思路，从根节点开始，如果要插入的结点大于根，就转换为去右子树插入；如果要插入的结点小于根，就转换为去左子树插入；如果相等，返回flase；如果一直走到空，那就就在该位置插入就行了。
7.2 代码实现
但是有一个问题，我们找到空插入的时候，如何和它的父亲链接起来？
<font color = black>我们可能会想到这样的方法，比如把父亲作为递归的参数进行传递，或者去判断root的子树为空而不是它本身为空。 但是，最好的方法我觉得是这样：
测试一下：
8. 删除（递归版本）
然后是删除： 
8.1 思路分析
怎么实现呢？
<font color = black>那其实大致的思路还是一样的，从根结点开始判断，如果要删除的值大于根，转换为去右子树删，小于根，转换为去左子树删，等于，就进行删除，如果走到空，那就是找不到。
8.2 代码实现
那我们来分析一下：
<font color = black>其实还是我们上面分析的那三种情况： 左为空、右为空或者左右都不为空。 那这里我们用引用，写起来还是比较简便的。 先写一下左为空和右为空的情况，这两个比较好处理
然后看一下比较麻烦的左右都不为空的情况
<font color = black>我们之前非递归版本的实现是，找一个符合条件的结点替换它，然后把替换的结点删除掉
测试一下：
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
return false;
if (key < root->_key)
{
return _EraseR(root->_left, key);
}
else if (key > root->_key)
{
return _EraseR(root->_right, key);
}
else
{
//删除
Node* del = root;
if (root->_left == nullptr)
{
root = root->_right;
}
else if (root->_right == nullptr)
{
root = root->_left;
}
else
{
Node* maxLeft = root->_left;
while (maxLeft->_right)
{
maxLeft = maxLeft->_right;
}
swap(maxLeft->_key, root->_key);
return _EraseR(root->_left, key);
}
delete del;
return true;
}
}9. 其它相关成员函数的实现
如果我们想在相对搜索二叉树的对象进行拷贝构造可以吗？
<font color = black>
9.1 析构
那我们可以先来写一下析构。
那析构的话我们这里还是用递归来搞，也可以用循环，但是比较麻烦：
<font color = black>
那现在不出意外，有了析构我们的浅拷贝就要出错了
<font color = black>
9.2 构造和拷贝构造
那我们就来写一个深拷贝的拷贝构造，我们还是用递归来实现
<font color = black>那也比较简单，先去拷贝创建就行了
那有了拷贝构造我们得实现一下构造函数：
<font color = black>
9.3 赋值重载
那赋值重载我们也搞一下吧：
跟我们之前玩得一样
BSTree<K>& operator=(const BSTree<K> t)
{
swap(_root, t._root);
return *this;
}
那关于搜索二叉树的实现差不多就到这里了
10. 完整代码
10.1 BSTree.h
#pragma once
template <class K>
struct BSTreeNode
{
BSTreeNode(const K& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
};
template <class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
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;
}
}
//走到这里cur为空，就是key应该插入的位置
cur = new Node(key);
//链接
if (key < parent->_key)
parent->_left = cur;
if (key > parent->_key)
parent->_right = cur;
return true;
}
bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key < cur->_key)
{
cur = cur->_left;
}
else if (key > cur->_key)
{
cur = cur->_right;
}
else
{
return true;
}
}
return false;
}
bool Erase(const K& key)
{
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
{
//key == cur->_key就是找到了，进行删除
//1.左为空
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (cur == parent->_left)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
delete cur;
cur = nullptr;
}
//2.右为空
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (cur == parent->_left)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
}
delete cur;
cur = nullptr;
}
else//左右都不为空
{
//这里选择右树的最小结点（最左边）替换
Node* pminRight = cur;
Node* minRight = cur->_left;
while (minRight->_left)
{
pminRight = minRight;
minRight = minRight->_left;
}
cur->_key = minRight->_key;
//删除替换结点
if (pminRight->_left = minRight)
{
pminRight->_left = minRight->_right;
}
else
{
pminRight->_right = minRight->_right;
}
delete minRight;
minRight = nullptr;
}
return true;
}
}
//找不到直接返回false
return false;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool FindR(const K& key)
{
return _FindR(_root, key);
}
bool InsertR(const K& key)
{
return _InsertR(_root, key);
}
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
/*BSTree()
:_root(nullptr)
{}*/
BSTree() = default;
~BSTree()
{
Destory(_root);
}
BSTree(const BSTree<K>& t)
{
_root = copy(t._root);
}
BSTree<K>& operator=(const BSTree<K> t)
{
swap(_root, t._root);
return *this;
}
protected:
Node* copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* newRoot = new Node(root->_key);
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;
root = nullptr;
}
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
return false;
if (key < root->_key)
{
return _EraseR(root->_left, key);
}
else if (key > root->_key)
{
return _EraseR(root->_right, key);
}
else
{
//删除
Node* del = root;
if (root->_left == nullptr)
{
root = root->_right;
}
else if (root->_right == nullptr)
{
root = root->_left;
}
else
{
Node* maxLeft = root->_left;
while (maxLeft->_right)
{
maxLeft = maxLeft->_right;
}
swap(maxLeft->_key, root->_key);
return _EraseR(root->_left, key);
}
delete del;
return true;
}
}
bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (key > root->_key)
{
return _InsertR(root->_right, key);
}
else if (key < root->_key)
{
return _InsertR(root->_left, key);
}
else
{
return false;
}
}
bool _FindR(Node* root, const K& key)
{
if (root == nullptr)
return false;
if (key < root->_key)
{
return _FindR(root->_left, key);
}
else if (key > root->_key)
{
return _FindR(root->_right, key);
}
else
{
return true;
}
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
private:
Node* _root = nullptr;
};10.2 BSTree.cpp
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include "BSTRee.h"
void BSTreeTest1()
{
BSTree<int> t1;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto e:a)
{
t1.Insert(e);
}
t1.InOrder();
cout << t1.FindR(10) << endl;
cout << t1.FindR(19) << endl;
}
void BSTreeTest2()
{
BSTree<int> t1;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto e : a)
{
t1.Insert(e);
}
t1.InOrder();
t1.Erase(10);
t1.InOrder();
t1.Erase(14);
t1.InOrder();
t1.Erase(13);
t1.InOrder();
t1.Erase(8);
t1.InOrder();
for (auto e : a)
{
t1.Erase(e);
t1.InOrder();
}
}
void BSTreeTest3()
{
BSTree<int> t1;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto e : a)
{
t1.InsertR(e);
}
t1.InOrder();
for (auto e : a)
{
t1.EraseR(e);
t1.InOrder();
}
}
void BSTreeTest4()
{
BSTree<int> t1;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto e : a)
{
t1.InsertR(e);
}
t1.InOrder();
BSTree<int> t2=t1;
t2.InOrder();
}
int main()
{
BSTreeTest4();
return 0;
}
- 点赞
- 收藏
- 关注作者
评论（0）