在上一篇文章
【数据结构】二叉树的中序遍历
中我们学会了前中后序遍历,并着重讲述了中序遍历的思路及其实现代码(1 + 2),今天我们讲一讲二叉树的层次遍历。
层次遍历,顾名思义,就是按层次来遍历整棵二叉树。层次是怎么定义的呢?二叉树的根节点为第一层,就如同倒过来的楼层一样。
要想实现层次遍历,我们需要借助另一个数据结构「 队列 」。至于为什么嘛?因为队列的特点是先进先出。利用这个特点,我们可以将已经访问过的结点的子节点存进队列里,实现每个层次的顺序不变。
以上图为例,进队出队的顺序如下:1 入队,2 入队,3 入队;1 出队;4 入队,5 入队;2 出队;6 入队; 3 出队;4 出队;5 出队;6 出队;结束。
简单的说,就是根节点进队,其子节点也跟着进队,随后根节点出队(或者根节点先出队,子节点再进队),直至队列为空,函数结束。
那么用代码如何实现呢?我们先来看一个比较麻烦点的:
//层次遍历二叉排序树
voidCengcibianli(BiTree &T)
{
printf("以下为层次遍历结果。\n");
QueueQ;
InitQueue(Q); //初始化队列
if(T)
Enqueue(Q,T); //进队
while(!QueueEmpty(Q)) //队非空
{
Delqueue(Q); //出队
}
printf("\n");
}
paste.ubuntu.com/p/PcFNtNpYr2/
和中序遍历一样,层次遍历也有个简单的代码实现方式:
status Level_view(BTpoint T,Quence Q)//层次遍历
{
if(T!=NULL)
{
*Q.rear++=T;
while(Q.front!=Q.rear)
{
if(T->lchild!=NULL) *Q.rear++=T->lchild;
if(T->rchild!=NULL) *Q.rear++=T->rchild;
T=*Q.front++;
printf("%d ",T->data);
T=*Q.front;
}
}
returnOK;
}
具体代码实现可借鉴上篇文章【数据结构】二叉树的中序遍历,我把代码放在了评论区,请自行查看。
那么,今天的分享就到此结束了,谢谢查阅,欢迎留言交流。
领取专属 10元无门槛券
私享最新 技术干货