当前位置: 首页 > news >正文

[c++高阶]二叉搜索树深度剖析

1.前言

从二叉搜索树开始,后面慢慢学的AVL树,红黑树,map,set,哈希表等等都会慢慢的变得更难了,也更加难以理解了。希望大家能够坚持下去,只要坚持,就是胜利。

本章重点

着重讲解什么是二叉搜索树,二叉搜索树的定义、性质以及二叉搜索树的正删查的模拟实现。

2.二叉搜索树的概念 

二叉搜索树:从中序遍历来看就是一颗有序树,即左边比我大,右边比我小。并且左子树也符合这个要求,右子树也符合这个要求。

        也可以称二叉搜索树为二叉查找树,并且他也可以是一棵空树

例:如果这棵树不为空的话

由于左子树中10的右边5比10小,所以这不是一颗二叉搜索树

30的左边15比30小,15作为左子树,没有左右孩子,天然是一棵二叉搜索树,而30的右边全都比30大,且右子树以41为根的左边比其小,右边比其大。所以这棵树是一棵二叉搜索树

3.二叉搜索树的定义及性质

如何定义一棵二叉树呢?

代入如下:

//创建节点
template <class T>
struct BstreeNode
{BstreeNode<T>* left;BstreeNode<T>* right;T  val;//构造函数BstreeNode(const T& key):left(nullptr),right(nullptr),val(key){}
};

解释:二叉树由一个一个的节点组成,所以只需要定义出来了节点,再把不同的节点链接起来,那么就组成了一棵二叉树

二叉树的性质:

1.二叉搜索树在用中序遍历时,得到的值就是一个已经排好序的序列了。

例:

用中序遍历可得:1 3 4 6 7 8 10 13 14

2.二叉搜索树只支持增加,删除,查找,不支持修改。

这是因为如果一旦改动了二叉搜索树里面的某一个值,那么这棵二叉搜索树就有可能不是二叉搜索树了,只是一棵普通的二叉树。

3.二叉搜索树的时间复杂度是0(N)

如果二叉树一旦出现最坏的情况,那么就是所有的值都比根小。

例:

由于这个原因,二叉搜索树是不稳定的,所以后续很少用到二叉搜索树,更多的是使用AVL树,和红黑树。

PS:二叉搜索树中是不能够出现相同的值的,如果出现了相同的值,就默认他不是一棵二叉搜索树 

 4.二叉树的模拟实现

 先构造地基,把基本的框架搞出来

//先构造单节点
template <class T>
struct BstreeNode
{BstreeNode<T>* left;BstreeNode<T>* right;T  val;//构造函数BstreeNode(const T& key):left(nullptr),right(nullptr),val(key){}
};//这里模拟实现二叉搜索树
template <class T>
class Bstree
{
public:typedef BstreeNode<T> Node;
private:Node* _root;
}

4.1 二叉搜索树的查找

例:

要在这一棵二叉搜索树中查找到7,查找代码如下。

迭代版本:

	bool Find(const T& key){Node* cur = _root;while (cur){if (cur->val < key)cur = cur->right;else if (cur->val > key)cur = cur->left;else if (cur->val == key)return true;}return false;}

递归版本:

bool FindR(const T& key)
{if (_FindR(_root, key)) return true;else return false;
}bool _FindR(Node* root, const T& key)
{if (root == nullptr) return false;if (root->val > key) return _FindR(root->left, key);else if (root->val < key) return _FindR(root->right, key);else return true;
}

简单来说就是总结成一句话:如果当前值比我小,我就去右子树里面找,如果当前值比我大,那我就去左子树里面找。最后的结果要么就是找到了,要么就是这棵二叉搜索树里面根本没有这个值。

4.2 二叉搜索树的插入

1.当树为空的时候,那么直接插入即可

2.如果树不为空,那么就需要先找到是具体插入在哪一个位置的后面,然后再进行插入。

例:

如果要插入一个2

代码如下:

bool Insert(const T& key)
{if (_root == nullptr){_root = new Node(key);return true;}//先找到要插入的位置Node* prev = nullptr;Node* cur = _root;while (cur){if (cur->val > key){prev = cur;cur = cur->left;}else if (cur->val < key){prev = cur;cur = cur->right;}else return false;}//到这就找到了要插入的位置cur = new Node(key);if (prev->val > key)prev->left = cur;else if (prev->val < key)prev->right = cur;return true;
}

PS:这里在找的时候,也记录了要插入的位置的前一个节点,这是因为你需要把插入的值链接到前一个节点的左边或者右边,形成一棵二叉搜索树。

 4.3 二叉搜索树的删除

 先判断要删除的节点是否在二叉搜索树里面,如果不在,那就返回。如果在的话,那么就有以下四种情况

1.要删除的节点左为空

2.要删除的节点右为空

3.要删除的节点左右都为空(这种情况包含在1.2两种情况里面)

4.要删除的节点左右都不为空。(这种情况就需要进行特殊处理了,找出左子树的最右值,即最大值,然后与删除的节点值进行交换,那么就转换成了删除这个左子树的最右值所在的节点的位置了。或者找出右子树的最左值,即最小值。)

代码如下:

bool Erase(const T& key)
{//1.在删除之前要先找到Node* prev = nullptr;Node* cur = _root;while (cur){if (cur->val > key){prev = cur;cur = cur->left;}else if (cur->val < key){prev = cur;cur = cur->right;}else{//找到了--三种情况--左为空,右为空,左右均不为空//1.左为空if (cur->left == nullptr){//1.先判断是不是根节点if (_root == cur)_root = cur->right;else{//不是根节点--那么就是链接的问题了if (cur == prev->left)prev->left = cur->right;else if (cur == prev->right)prev->right = cur->right;}delete cur;cur = nullptr;return true;}//2.右为空else if (cur->right == nullptr){//1.先判断是不是根节点if (_root == cur)_root = cur->left;else{//不是根节点--那么就是链接的问题了if (cur == prev->left)prev->left = cur->left;else if (cur == prev->right)prev->right = cur->left;}delete cur;cur = nullptr;return true;}else{//左右均不为空--那么找左子树的最右,或者右子树的最左来进行替换Node* prev = cur;Node* minleft = cur->right;while (1){if (minleft->left != nullptr){prev = minleft;minleft = minleft->left;}elsebreak;}//找到了右子树的最左为minleftcur->val = minleft->val;//还是分两种情况--左为空或者右为空if (minleft->left == nullptr){if (prev == cur)prev->right = minleft->right;elseprev->left = minleft->right;}else if (minleft->right == nullptr){//右为空,那么左右一定是空的,因为minleft就是最左了if (prev == cur)prev->right = nullptr;elseprev->left = nullptr;}delete minleft;minleft = nullptr;return true;}}}return false;
}

5.总结

二叉树的模拟实现肯定不只是单单的这么简单,而模拟实现他的目的只是为了更好的理解他的相关操作,以及理解增删查代码的相关写法。我们不是为了造轮子,而是为了更好的理解这个轮子是如何造出来的。

此外:本次只给出来查找函数的迭代写法和递归写法,插入函数和删除函数的递归写法还没有给出,有兴趣的小伙伴参考以下链接。

二叉搜索树的增删改模拟实现 · e87b2ae · 青酒余成/初识数据结构 - Gitee.com


http://www.mrgr.cn/news/62648.html

相关文章:

  • Microsoft Entity Framework Core 8 示例
  • xmuoj [蒙德里安的梦想] 状压dp个人笔记
  • 追寻时间管理大师足迹—学习伟人感悟
  • linux-UART
  • 安宝特分享 | AR技术引领:跨国工业远程协作创新模式
  • 计组-层次化存储结构
  • 如何进行商标注册?
  • Vivo开奖了,劝退价。。
  • 【Nextcloud】在 Ubuntu 22.04.3 LTS 上的 Nextcloud Hub 8 (29.0.0) 优化
  • 你的Mac book多久没有清洁键盘屏幕了,Mac清洁好帮手来了
  • 学习算力网络必会关键词
  • 哈希表应用(位图和布隆过滤器)
  • HTB-Cicada 靶机笔记
  • ETL处理全流程
  • Linux 命令解释器-shell
  • stm32入门教程--USART外设 超详细!!!
  • Linux:线程池
  • qt QSlider详解
  • 软设每日打卡——折半查找二叉判定树、平衡二叉树
  • 多线程案例---单例模式
  • 2024年NSSCTF秋季招新赛-WEB
  • Convolution 卷积
  • 前端笔面试查漏补缺
  • 鸿蒙系统:核心特性、发展历程与面临的机遇与挑战
  • JSP水果商城管理系统WEB项目
  • Vue中path和component属性