【C++高阶(一)】二叉搜索树深度剖析

💓博主CSDN主页:杭电码农-NEO💓

⏩专栏分类:C++从入门到精通⏪

🚚代码仓库:NEO的学习日记🚚

🌹关注我🫵带你学习C++
🔝🔝

在这里插入图片描述

这里写目录标题

1. 前言
2. 二叉搜索树的概念以及定义
3. 二叉搜索树的性质
4. 二叉搜索树模拟实现
5. 二叉搜索树的插入操作
6. 二叉搜索树的删除分析(一)
7. 二叉搜索树的删除分析(二)
8. 总结以及拓展

1. 前言

从本篇文章开始正式进入C++高阶
的学习,C++高阶主要包括二叉搜索树
,AVL树,红黑树,哈希等高阶数据结构,
以及C++11和智能指针,抛异常等等.
高阶的内容往往是与普通人拉开差距的
内容,请同学们耐心学习!

本章重点:

本篇文章着重讲解二叉搜索树的概念
以及定义,以及二叉搜索树的模拟实现!
最后拓展讲解二叉搜索树的应用场景.

2. 二叉搜索树的概念以及定义

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

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

比如:

在这里插入图片描述

3. 二叉搜索树的性质

首先,二叉搜索树是有序的!
它的中序遍历出来就是一个有序的序列

上面的图片中,中序遍历出来如下

[1,3,4,6,7,8,10,14,13] 有序序列

其次,二叉搜索树只支持增删查,并不
支持改,因为随意修改会导致这棵树
可能不满足二叉搜索树的条件,比如
将上图中的14改为9,它就不是二叉
搜索树了,这一点很好理解!

在这里插入图片描述

一点小细节,二叉搜索树中不能出现
值相同的节点,若插入时出现值相同的
节点就直接返回false,插入失败!

4. 二叉搜索树模拟实现

我们先把基本的框架搭建一下:

template<class K>
struct BSTreeNode //二叉搜索树封装的节点信息
{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){ }
};template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
private:Node* _root = nullptr;
}

对代码的解释:

基本框架比较容易,就是套一层
结构体后使用root,不多解释!

5. 二叉搜索树的插入操作

插入函数是最容易实现的,插入的
值比较大就往右走,比较小就往左走
如果遇见和插入值相同的值,返回false!

bool insert(const K& key)//左小右大
{if (_root == nullptr)//第一次插入时的操作{_root = new Node(key);return true;}Node* cur = _root;Node* prev = nullptr;while (cur != nullptr){if (cur->_key < key){prev = cur;cur = cur->_right;}	else if (cur->_key > key){prev = cur;cur = cur->_left;}else if (cur->_key == key)return false;}cur = new Node(key);if (prev->_key > key)prev->_left = cur;elseprev->_right = cur;return true;
}

对代码的解释:

定义prev的意义是最后cur找到自己的
位置后,要把cur和它的父亲链接起来,
prev起到一个连接作用!最后一步代码
在判断cur是prev的左孩子还是右孩子

6. 二叉搜索树的删除分析(一)

搜索树的删除操作较为复杂
先分析前三种比较简单的情况
我们一步一步来分析:

被删除的节点无孩子

这种情况是最简单的,直接将此
节点删除了即可,不用做特殊处理!

被删除的节点只有左孩子

此节点被删除后,将此节点的左孩子
连接到此节点的父亲节点即可!

在这里插入图片描述
3. 被删除的节点只有右孩子

此节点被删除后,将此节点的右孩子
连接到此节点的父亲节点即可!

前三种情况的代码比较容易,直接上菜!

bool erase(const K& key)//非递归版本
{
Node* prev = nullptr;
Node* cur = _root;
while (cur != nullptr)//先找到此节点再删除
{if (cur->_key < key){prev = cur;cur = cur->_right;}else if (cur->_key > key){prev = cur;cur = cur->_left;}else//找到了此节点后,开始删除{//1. 左边为空//2. 右边为空//3. 左右都不为空if (cur->_left == nullptr)//左孩子为空情况{if (cur == _root)_root = cur->_right;else{if (cur == prev->_left)prev->_left = cur->_right;elseprev->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr)//右孩子为空情况{if (cur == _root)_root = cur->_left;else{if (cur == prev->_left)prev->_left = cur->_left;elseprev->_right = cur->_left;}delete cur;return true;}
}

对代码的解释:

看似只写了两种情况,其实把左右都为
空的情况也给算进去了!

7. 二叉搜索树的删除分析(二)

当被删除的节点存在左右孩子时,
此时不再是简单的指向问题了,
这里我使用的是一个常用的方法:

替换法

替换法替换法,和谁替换呢?这个
被替换的节点一定要满足两个条件:

小于所有右子树的值
大于所有左子树的值

那么现在就有两个人选了:
一个是左子树中的最右节点
一个是右子树中的最左节点
简单画个图来理解一下:

在这里插入图片描述

假设这里统一使用右子树中最左边的
节点来替换,替换完成后,还有问题!
那就是被替换的节点的左肯定是空了
因为此节点就是最左节点了,但是它的右
不一定为空,还需要分情况讨论,
具体代码如下:

//注,此时的cur即为要删除的节点
Node* tmp = cur->_right;
Node* prevtmp = cur;
while (1) //寻找右子树中的最左节点
{if (tmp->_left != nullptr){prevtmp = tmp;tmp = tmp->_left;}elsebreak;
}
cur->_key = tmp->_key;
if (tmp->_right == nullptr)//如果被替换的节点的右为空
{if (prevtmp == cur)//被删除节点右边只有一个节点,直接将被删除节点的右置空prevtmp->_right = nullptr;elseprevtmp->_left = nullptr;delete tmp;tmp = nullptr;
}
else
{if (prevtmp == cur)prevtmp->_right = tmp->_right;elseprevtmp->_left = tmp->_right;delete tmp;tmp = nullptr;
}