数据结构学习分享之链式二叉树(二)

这篇具有很好参考价值的文章主要介绍了数据结构学习分享之链式二叉树(二)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

⏩专栏分类:数据结构学习分享⏪

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

🌹关注我🫵带你了解更多数据结构的知识
  🔝🔝


数据结构学习分享之链式二叉树(二)



1. 前言🚩

本节是上一节二叉树知识的延申,这一节中会用到队列的相关知识和二叉树的结构配合使用,如果你还没有接触过队列,那么请先跳转栈和队列详解.如果对二叉树结构与一些基础问题感兴趣的可以跳转二叉树(一)

这里我们直接接着上一章往后介绍


2. 求二叉树的高度🚩

我们还是用之前的二叉树结构来分析:

数据结构学习分享之链式二叉树(二)这里的空节点我们给赋值成了,1~7.方便我们识别

首先我们要想到的是,当这棵树为空树时,二叉树的高度应该是0,所以当数为空我们返回0,然而当树不等于空时,我们可以以大事化小,小事化了的思想,将当前树的高度转换成左右子树两个中的最大高度再加上一,然后左右子树中最大高度的树的高度又可以转换成我们刚刚的思想,就这样不断递归下去直接我们遇见空节点.

int BinaryTreeDepth(BTNode* root)//求树的高度(按第一层为1的标准)
{
	if (root == NULL)//树为空或节点为空时返回0
	{
		return 0;
	}
	//还有一种写法是:
	//return BinaryTreeDepth(root->left) > BinaryTreeDepth(root->right) ?
	//BinaryTreeDepth(root->left) + 1 : BinaryTreeDepth(root->right) + 1
	int left = BinaryTreeDepth(root->left);//将值保存起来,否则开辟的栈帧过多
	int right = BinaryTreeDepth(root->right);
	return left > right ? left + 1 : right + 1;
}

这里第一步的节点等于空还是有两个涵义,一是我们拿到的树本身就是空树,二是我们递归下去时,遇见了空节点.值得注意的是,这里有两种写法,但是第一种被注释的写法不太好,因为在三目操作符中会不断调用递归函数,这个方法会严重消耗栈帧,所以定义变量将它的值保存起来再比较是优解!


3. 查找值为X的节点🚩

首先我们查找到值后,应该将对应的节点返回到函数外面去,所以这里函数的返回值应该是BTNode*.还是一样的思想

  • 第一步,当树为空树时,里面根本没有节点,所以外面返回空,
  • 第二步,当树或节点不为空时,就应该判断当前节点对应的值是不是与X相同,如果当前节点的值与X相同就应该返回当前节点.
  • 第三步,当我们把一二步都走完后,走到第三步这个位置说明当前节点即不为空节点,并且当前节点对应的值也不为X,那么这时我们就应该去当前节点的左右子树去寻找.

现在来实现代码:

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)//查找值为x的节点,返回节点地址
{
	if (root == NULL)//空树或空节点就返回空
	{
		return NULL;
	}
	if (root->data == x)//对应上了就返回节点的地址
	{
		return root;
	}
	BTNode* left = BinaryTreeFind(root->left, x);
	if (left != NULL)//left会再次进入到此函数直到遇见NULL或对应值X
	{
		return left;//当left不为空时,代表left中一定存储着对应值X的地址
	}
	BTNode* right = BinaryTreeFind(root->right, x);
	if (right != NULL)
	{
		return right;
	}
	return NULL;//当左右子树都为空时,左右子树都不返回,这个节点下面所有的节点都不能与X对应上
}

这里需要解释的是当left不为空指针时,那么left一定是找到了与X值对应上的节点了,因为除了找到对应节点以外,其他情况都是返回空指针,我们就把找到的left返回到上一层函数后,上一层函数发现我们返回的值不为空,又会将这个节点地址返回到上上一层函数,就这样一直返回直到走完所有递归的函数

并且我们这样左子树判断后再定义右子树判断有一个好处,那就是如果左子树找到了,我们就不会走右子树,假如我们像下面这样写的话,不管左子树有没有找到,右子树都会走

    BTNode* left = BinaryTreeFind(root->left, x);
    BTNode* right = BinaryTreeFind(root->right, x);
    if (left != NULL)//left会再次进入到此函数直到遇见NULL或对应值X
	{
		return left;//当left不为空时,代表left中一定存储着对应值X的地址
	}
	if (right != NULL)
	{
		return right;
	}
	return NULL;

这里如果你感到很难理解,应该画一幅递归展开图来分析,假设这里这个图中我需要想找字符’E’.

数据结构学习分享之链式二叉树(二)

递归展开图:

数据结构学习分享之链式二叉树(二)

这里就很好的体现出这样写代码的优势,左子树找到后就直接返回不会进入右子树了


4. 二叉树的层序遍历🚩

层序遍历:除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。

层序遍历的顺序:

数据结构学习分享之链式二叉树(二)


4.1 借助队列实现层序遍历🏁

我们已经了解了层序遍历的顺序,我们自己画一个二叉树的图模拟一下怎样借助队列来实现层序遍历:

数据结构学习分享之链式二叉树(二)
基本步骤是:

  1. 先将根入队列
  2. 当前节点出队列后,将次此节点的左右孩子入队列
  3. 一直这样循环往复直到队列为空,说明最后一层已经没有节点了,遍历结束

我们再来画个图理解一下:

数据结构学习分享之链式二叉树(二)

一直这样循环往复直到队列为空!


4.2 层序遍历的代码实现🏁

void BinaryTreeLevelOrder(BTNode* root)//层序遍历,需要使用队列
{
	if (root == NULL)
	{
		return;
	}
	Queue q;
	QueueInit(&q);//先定义一个队列后初始化它,再将根入队
	QueuePush(&q, root);
	while (!QueueEmpty(&q))//当队列不为空时就继续
	{
		BTNode* front = QueueFront(&q);//将队头出来并打印
		QueuePop(&q);//取出队头元素并保存在front后将队头删除掉
		printf("%c ", front->data);
		if (front->left != NULL)//若孩子不为空就将孩子入队
		{
			QueuePush(&q, front->left);
		}
		if (front->right != NULL)
		{
			QueuePush(&q, front->right);
		}
	}
	printf("\n");
	QueueDestroy(&q);//使用完后销毁队列
}

这样我们就可以将二叉树以层序遍历的方式打印出来:

数据结构学习分享之链式二叉树(二)


5. 判断一个二叉树是不是完全二叉树🚩

判断二叉树是否为完全实际上需要借助我们刚刚介绍的层序遍历的内容,那么怎么判断呢?这里我先不剧透,我们先用一个完全二叉树和一个非完全二叉树来走一走层序遍历看看有没有规律.

1. 完全二叉树的层序遍历

数据结构学习分享之链式二叉树(二)


2. 非完全二叉树的层序遍历:

数据结构学习分享之链式二叉树(二)


我们可以发现一个规律,就是完全二叉树在队列中只要遇见了第一个NULL,那么队列后面的内容就全是NULL,而非完全二叉树在队列中遇见了第一个NULL后,后面还会遇见非空元素


5.1 代码实现🏁

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front == NULL)//当遇见第一个NULL时就直接跳出循环来到下面的语句
		{
			break;
		}
		else
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}

	// 遇到空了以后,检查队列中剩下的节点
	// 1、剩下全是空,则是完全二叉树
	// 2、剩下存在非空,则不是完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front)//如果不为空就返回false
		{
			QueueDestroy(&q);
			return false;
		}
	}

	QueueDestroy(&q);
	return true;//全部节点都走完了没有发现非空,说明队列里全是空就返回true.
}

代码的详解已经注释出来了,如果你还不太理解的话,可以直接手动画一个二叉树再来画图判断


6. 二叉树的销毁🚩

这里销毁二叉树右两种写法,一种是传二级指针在函数中将我们事先创建的节点给销毁了,第二种是传一级指针,我们就需要在main函数中将root置空.这里也是用递归的思想.

// 二叉树销毁
//void BinaryTreeDestory(BTNode** root)传二级指针就不用在main函数中将root置空
void BinaryTreeDestory(BTNode* root)//后序遍历释放所有节点(先释放了根会找不到儿子)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}

7. 链式二叉树题目分享🚩

这一块的OJ题考的也是比较多的,这里我给大家分享几道:

  1. 单值二叉树 力扣965题
  2. 检查两颗树是否相同 力扣100题
  3. 对称二叉树 力扣101题
  4. 二叉树的前序遍历 力扣144题
  5. 二叉树的中序遍历 力扣94题
  6. 二叉树的后序遍历 力扣145题
  7. 另一颗树的子树 力扣572题
  8. 二叉树的构建以及遍历 牛客网试题

题目的讲解会在后面给大家一一做出来!


8. 总结🚩

总体来说链式二叉树这个部分还是有一点难度了,这里的思想基本上都是递归,其实不要认为递归难,对于链式二叉树而言,使用非递归的方法来解题才难!这一模块最重要的还是画图分析,并且要有把大事化小,把小事化了的态度.文章来源地址https://www.toymoban.com/news/detail-456548.html

🔎 下期预告:八大排序详解 🔍

到了这里,关于数据结构学习分享之链式二叉树(二)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构】二叉树链式结构

    🚀write in front🚀 📜所属专栏:初阶数据结构 🛰️博客主页:睿睿的博客主页 🛰️代码仓库:🎉VS2022_C语言仓库 🎡您的点赞、关注、收藏、评论,是对我最大的激励和支持!!! 关注我,关注我,关注我 , 你们将会看到更多的优质内容!!   在之前的二叉树的顺序结

    2024年02月03日
    浏览(39)
  • 【数据结构】二叉树(链式)

    😛作者:日出等日落 📘 专栏:数据结构           抱怨是一件最没意义的事情。如果实在难以忍受周围的环境,那就暗自努力练好本领,然后跳出那个圈子。 目录  🎄二叉树 ✔二叉树的结构:  ✔BuyNode(创建二叉树节点): 🎄基本函数操作: ✔PreOrder(前序递归遍历):

    2024年02月01日
    浏览(43)
  • 【数据结构】二叉树之链式结构

    🔥 博客主页 : 小羊失眠啦. 🎥 系列专栏 : 《C语言》 《数据结构》 《Linux》 《Cpolar》 ❤️ 感谢大家点赞👍收藏⭐评论✍️ 在学习二叉树各种各样的操作前,我们先来回顾一下二叉树的概念: 二叉树是度不超过2的树,由根结点和左右2个子树组成,每个子树也可以看作

    2024年02月04日
    浏览(43)
  • 【数据结构】二叉树的链式结构

    学习链式二叉树要知道三种遍历方式,便于对二叉树的节点以及左子树和右子树进行操作。 前序遍历:根、左子树、右子树 中序遍历:左子树、根、右子树 后序遍历:左子树、右子树、根 以下图为例: 得到的结果: 前序遍历:1 2 3 4 5 6 中序遍历:3 2 1 5 4 6 后序遍历:3 2

    2024年02月08日
    浏览(52)
  • 数据结构:二叉树的链式结构

    朋友们、伙计们,我们又见面了,本期来给大家解读一下链式二叉树的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! 数据结构与算法专栏 :数据结构与算法 个  人  主  页 :stackY、 C 语 言 专 栏 :C语言:从入门到精通 目录 前言

    2024年02月07日
    浏览(56)
  • 数据结构——二叉树的链式结构

      个人主页 : 日刷百题 系列专栏 : 〖C语言小游戏〗〖Linux〗〖数据结构〗  〖C语言〗 🌎 欢迎各位 → 点赞 👍+ 收藏 ⭐️+ 留言 📝  ​ 这里我们使用先序遍历的思想来创建二叉树,这里的内容对于刚接触二叉树的朋友可能有些难理解,不妨先看完下面的二叉树各种遍历

    2024年02月05日
    浏览(43)
  • 【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)

    在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,且为了方便后面的介绍,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研

    2024年01月25日
    浏览(59)
  • 【数据结构】二叉树的链式存储结构

    前序遍历,又叫先根遍历。 遍历顺序:根 - 左子树 - 右子树 代码: 中序遍历,又叫中根遍历。 遍历顺序:左子树 - 根 - 右子树 代码 : 后序遍历,又叫后根遍历。 遍历顺序:左子树 - 右子树 - 根 代码 : 除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍

    2024年02月09日
    浏览(42)
  • 【数据结构 —— 二叉树的链式结构实现】

    树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 1.有一个 特殊的结点,称为根结点 ,根节点没有前驱结点 2.除根节点外, 其余结点被分成M(M0)个互不相交

    2024年02月05日
    浏览(54)
  • 【数据结构—二叉树的链式结构实现】

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 一、二叉树的存储结构 二、二叉树链式结构的实现 2.1手动构建一课树 2.2二叉树的遍历 三、二叉树链式结构的实现 3.1前序遍历(递归) 3.2中序遍历(递归) 3.3后序遍历(递归) 3.4层序遍历(非递

    2024年02月03日
    浏览(56)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包