目录
一、什么是层序遍历
二、层序遍历的实现
三、判断一棵树是否为完全二叉树
总结:
学习二叉树结构,最简单的就是遍历。
所谓二叉树遍历就是按照某种规则对二叉树中的节点进行相应操作,每个节点值操作一次。
遍历是二叉树的重要运算之一,也是二叉树进行其它运算的基础。
二叉树遍历有:前序遍历、中序遍历、后序遍历、层序遍历。本文即讨论层序遍历,掌握程序遍历的思路,写法以及简单应用。
一、什么是层序遍历
设根所在的节点层数为1,层序遍历就是从二叉树的根节点出发,首先访问第一层的根节点,然后从左到右访问第2层节点,接着第三层,直到访问全部节点。这一自上而下,自左向右的访问方式就叫层序遍历。
图解:
这颗二叉树的层序遍历为:
A->B->C->D->E->F->G->H->I
二、层序遍历的实现
方法:
根节点出队列,带左右孩子入队列
图解:
层序遍历,需要借助队列数据结构,先把根节点入队列,依次出队列,每次出一个数据,就带节点的孩子入队列(先入左孩子,后入右节点),直到全部节点出过队列,队列为空,循坏结束。
层序遍历完成。
代码实现:
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.完全二叉树
完全二叉树:
第K层从左到右,无空缺节点。
满二叉树是完全二叉树的一种特殊情况
2.判断?
判断是否为完全二叉树,利用完全二叉树的定义,中途没有孤立的孩子节点。
思路:
利用层序遍历的思路
入队列---->出队列......带孩子入队列----> 1.遇到为空的孩子 2.队列为空 ---->停下
队列不为空——非完全二叉树
队列为空——是完全二叉树
图解:
代码实现:
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
作者知识有限,希望能给大家带来一点帮助。文章来源地址https://www.toymoban.com/news/detail-544846.html
到了这里,关于二叉树层序遍历的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!