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

这篇具有很好参考价值的文章主要介绍了【C++高阶(一)】二叉搜索树深度剖析。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

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

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

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


【C++高阶(一)】二叉搜索树深度剖析,C++从入门到精通,c++,开发语言

1. 前言

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

本章重点:

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


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

二叉搜索树又称二叉排序树
它或者是一棵空树

或者是具有以下性质的二叉树:

  • 若它的左子树不为空,则左子树的
    所有节点的值都小于根节点的值

  • 若它的右子树不为空,则右子树的
    所有节点的值都大于根节点的值

  • 它的左右子树也分别为二叉搜索树

比如:

【C++高阶(一)】二叉搜索树深度剖析,C++从入门到精通,c++,开发语言


3. 二叉搜索树的性质

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

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

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

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

【C++高阶(一)】二叉搜索树深度剖析,C++从入门到精通,c++,开发语言

一点小细节,二叉搜索树中不能出现
值相同的节点,若插入时出现值相同的
节点就直接返回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;
	else
		prev->_right = cur;
	return true;
}

对代码的解释:

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


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

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

  1. 被删除的节点无孩子

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

  1. 被删除的节点只有左孩子

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

【C++高阶(一)】二叉搜索树深度剖析,C++从入门到精通,c++,开发语言
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;
				else
					prev->_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;
				else
					prev->_right = cur->_left;
			}
			delete cur;
			return true;
		}
}

对代码的解释:

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


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

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

替换法

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

  1. 小于所有右子树的值
  2. 大于所有左子树的值

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

【C++高阶(一)】二叉搜索树深度剖析,C++从入门到精通,c++,开发语言

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

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

代码解释已放在代码注释中


8. 总结以及拓展

二叉搜索树的模拟实现远远不止于此
但是我们只是想了解它的底层,而不是
写一个更好的二叉树出来,在插入和删除
这两个函数的非递归写法后,还有它们的
递归写法,毕竟一想到树总能想到递归,
递归的插入和删除留给大家自己实现

拓展链接:二叉搜索树的全部代码:

二叉搜索树模拟实现文章来源地址https://www.toymoban.com/news/detail-788342.html


🔎 下期预告:AVL树深度剖析 🔍

到了这里,关于【C++高阶(一)】二叉搜索树深度剖析的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++算法】dfs深度优先搜索(上) ——【全面深度剖析+经典例题展示】

    💃🏼 本人简介:男 👶🏼 年龄:18 📕 ps:七八天没更新了欸,这几天刚搞完元宇宙,上午一直练🚗,下午背四级单词和刷题来着,还在忙一些学弟学妹录制视频和准备开学一些事,一直没空出时间来,等 20号练完车,也马上开学了QAQ。不过今天倒是空出来一些时间,恰好这

    2024年02月02日
    浏览(43)
  • 安卓上最好用的Linux终端仿真软件:Termux 从入门到精通深度剖析

    用过Linux的都知道,Linux里面最好用的就是terminal(终端),他提供了对Linux的所有操作,可以轻松的对文件,权限等进行管理,在安卓下也是一样,只不过我们平时在使用安卓的时候接触不到命令行,全部都是图形化操作,如果都像这样依赖可视化软件的话,那么很难有更高

    2024年02月21日
    浏览(48)
  • 【C++从入门到放弃】vector深度剖析及模拟实现

    🧑‍💻作者: @情话0.0 📝专栏:《C++从入门到放弃》 👦个人简介:一名双非编程菜鸟,在这里分享自己的编程学习笔记,欢迎大家的指正与点赞,谢谢! vector 是表示 可变大小数组 的序列容器。 就像数组一样,vector也采用的 连续存储空间 来存储元素。也就是意味着可以

    2024年02月07日
    浏览(47)
  • 【C++从入门到放弃】list深度剖析及模拟实现

    🧑‍💻作者: @情话0.0 📝专栏:《C++从入门到放弃》 👦个人简介:一名双非编程菜鸟,在这里分享自己的编程学习笔记,欢迎大家的指正与点赞,谢谢! list 是允许在序列内的任何位置进行 常量时间的插入和删除 操作的序列容器,并且该容器可以前后双向迭代。 list 的底

    2024年02月10日
    浏览(46)
  • C++入门之stl六大组件--List源码深度剖析及模拟实现

    文章目录 前言 一、List源码阅读 二、List常用接口模拟实现 1.定义一个list节点 2.实现一个迭代器 2.2const迭代器 3.定义一个链表,以及实现链表的常用接口 三、List和Vector 总结 本文中出现的模拟实现经过本地vs测试无误,文件已上传gitee,地址:list: 模仿实现stl的list - Gitee.com 首

    2024年02月13日
    浏览(50)
  • C++入门之stl六大组件--stack和queue源码深度剖析及模拟实现

    目录 前言 一、stack的介绍和使用 1.stack的介绍 2.stack的使用 3.stack的模拟实现 二、queue的介绍和使用 1.queue的介绍 2.queue的使用 3.queue的模拟实现 三、priority_queue的介绍和使用 1.priority_queue的介绍 2.priority_queue的使用 3.priority_queue的模拟实现 3.1解决一个topK问题 四、容器适配器 1

    2024年02月14日
    浏览(47)
  • 【C++从入门到放弃】stack和queue的深度剖析及空间适配器的介绍

    🧑‍💻作者: @情话0.0 📝专栏:《C++从入门到放弃》 👦个人简介:一名双非编程菜鸟,在这里分享自己的编程学习笔记,欢迎大家的指正与点赞,谢谢!   此篇博客将谈及到的stack、queue和priority_queue都不是STL的标准容器,而是一种空间适配器。它是通过对一种容器进行

    2024年02月11日
    浏览(42)
  • 爬虫高阶攻略:从入门到精通!

    引言:作为一名程序员,想必大家都有了解过爬虫的基本原理,也写过一些简单的爬虫程序。但要想成为爬虫高手,需要更深入的学习和实践。本文将带领大家探究爬虫高阶技巧,从入门到精通的学习资料,让你成为实战型的爬虫攻略专家! 1. 爬虫反反爬 爬虫反爬是指网站

    2024年02月03日
    浏览(40)
  • Redis从入门到精通【高阶篇】之底层数据结构字典(Dictionary)详解

    上个篇章回顾,我们上个章节,讲了Redis中的快表(QuickList),它是一种特殊的数据结构,用于存储一系列的连续节点,每个节点可以是一个整数或一个字节数组。快表是Redis中的底层数据结构之一,常用于存储有序集合(Sorted Set)等数据类型的底层实现。 那么本章讲解Red

    2024年02月09日
    浏览(50)
  • Redis从入门到精通【高阶篇】之底层数据结构跳表(SkipList)

    上个篇章回顾,我们上个章节我们学习了《Redis从入门到精通【高阶篇】之底层数据结构整数集(IntSet)详解》,我们从源码层了解整数集由一个头部和多个数据块组成。头部中存储了整数集的元素个数、编码方式和数据块的起始地址等信息。数据块中存储了实际的整型数据,当

    2024年02月09日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包