二叉树层序遍历

这篇具有很好参考价值的文章主要介绍了二叉树层序遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、什么是层序遍历

二、层序遍历的实现

三、判断一棵树是否为完全二叉树

总结:


学习二叉树结构,最简单的就是遍历。

所谓二叉树遍历就是按照某种规则对二叉树中的节点进行相应操作,每个节点值操作一次。

遍历是二叉树的重要运算之一,也是二叉树进行其它运算的基础。

二叉树遍历有:前序遍历、中序遍历、后序遍历、层序遍历。本文即讨论层序遍历,掌握程序遍历的思路,写法以及简单应用。

一、什么是层序遍历

设根所在的节点层数为1,层序遍历就是从二叉树的根节点出发,首先访问第一层的根节点,然后从左到右访问第2层节点,接着第三层,直到访问全部节点。这一自上而下,自左向右的访问方式就叫层序遍历。

图解:
二叉树层序遍历,数据结构,数据结构,c语言,leetcode

这颗二叉树的层序遍历为:
A->B->C->D->E->F->G->H->I

二、层序遍历的实现

方法:
根节点出队列,带左右孩子入队列

图解:
二叉树层序遍历,数据结构,数据结构,c语言,leetcode

 层序遍历,需要借助队列数据结构,先把根节点入队列,依次出队列,每次出一个数据,就带节点的孩子入队列(先入左孩子,后入右节点),直到全部节点出过队列,队列为空,循坏结束。

层序遍历完成。

代码实现:

void BinaryTreeLevelOrder(BTNode* root)
{
	Queue qu;
	BTNode * cur;

	QueueInit(&qu);

	QueuePush(&qu, root);  //入根节点

	while (!QueueIsEmpty(&qu))  //队列不为空,重复出队列,入队列
	{
		cur = QueueTop(&qu);

		putchar(cur->_data);

		if (cur->_left)    //入孩子
		{
			QueuePush(&qu, cur->_left);
		}

		if (cur->_right)
		{
			QueuePush(&qu, cur->_right);
		}

		QueuePop(&qu);   //头删,出队列
	}

	QueueDestory(&qu);
}

三、判断一棵树是否为完全二叉树

1.完全二叉树

二叉树层序遍历,数据结构,数据结构,c语言,leetcode

完全二叉树:

第K层从左到右,无空缺节点。 

满二叉树是完全二叉树的一种特殊情况

二叉树层序遍历,数据结构,数据结构,c语言,leetcode

 

2.判断?

判断是否为完全二叉树,利用完全二叉树的定义,中途没有孤立的孩子节点。

思路:

利用层序遍历的思路

入队列---->出队列......带孩子入队列----> 1.遇到为空的孩子 2.队列为空  ---->停下 

队列不为空——非完全二叉树

队列为空——是完全二叉树

图解:

二叉树层序遍历,数据结构,数据结构,c语言,leetcode

 

代码实现:

bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);

	if (root)
		QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);

		if (front == NULL)  //遇到空节点 1.结束 2.不是完全二叉树
			break;
		QueuePop(&q);

		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}

	while (!QueueEmpty(&q))  //结束则为完全二叉树,否则不是
	{
		if (QueueFront(&q))
		{
			return false;
		}
		QueuePop(&q);
	}
	return true;

}

总结:

本文介绍二叉树的层序遍历,层序遍历是一种较为特别的遍历方式,有它独特的用处。

另外介绍了完全二叉树的判断方法。即出队列,入队列的层序遍历,再加上简单的判断

作者知识有限,希望能给大家带来一点帮助。文章来源地址https://www.toymoban.com/news/detail-544846.html

到了这里,关于二叉树层序遍历的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包