二叉树层序遍历
目录
二、层序遍历的实现
三、判断一棵树是否为完全二叉树
总结:
学习二叉树结构,最简单的就是遍历。
所谓二叉树遍历就是按照某种规则对二叉树中的节点进行相应操作,每个节点值操作一次。
遍历是二叉树的重要运算之一,也是二叉树进行其它运算的基础。
二叉树遍历有:前序遍历、中序遍历、后序遍历、层序遍历。本文即讨论层序遍历,掌握程序遍历的思路,写法以及简单应用。
一、什么是层序遍历
设根所在的节点层数为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;
}
总结:
本文介绍二叉树的层序遍历,层序遍历是一种较为特别的遍历方式,有它独特的用处。
另外介绍了完全二叉树的判断方法。即出队列,入队列的层序遍历,再加上简单的判断
作者知识有限,希望能给大家带来一点帮助。
深度搜索: 感谢纠正!这里是不够严谨。
shallwe?: 是的,MySQL针对快照读和当前读分别使用了MVCC机制和临键锁机制在一定程度上避免了可重复读隔离级别下的幻读现象,但是没有完全避免。如果在一个事务中,前后不是统一使用快照读或者当前读中某个,而是混着用的话,还是会出现幻读现象。所以我认为表里标了“×”的话不够严谨。
深度搜索: 关于幻读(Phantom Reads),它指的是当一个事务重新读取某个范围的记录时,另一个事务插入了符合该查询条件的新记录,导致第一次和第二次读取的结果不一致。 在MySQL的REPEATABLE READ隔离级别下,由于使用了MVCC和Next-Key Locks(索引记录上的锁和索引记录之间的间隙上的锁),MySQL避免了传统的幻读现象,即通过在索引上锁定记录的范围来防止其他事务插入新的记录到已锁定的范围内。需要注意的是,如果查询没有使用索引(或索引选择不佳),那么MySQL的REPEATABLE READ隔离级别可能无法完全防止幻读,因为此时MySQL可能无法有效地锁定足够的范围来阻止新记录的插入。所以我们可以认为针对mysql,不会产生幻读
shallwe?: 最后的总结里,“可重复读”隔离级别中,“幻读”现象是不是标错了,表里打了个“×”
CSDN-Ada助手: 恭喜你这篇博客进入【CSDN每天值得看】榜单,全部的排名请看 https://bbs.csdn.net/topics/619258339。