二叉树的层次遍历

在上一篇文章

【数据结构】二叉树的中序遍历

中我们学会了前中后序遍历,并着重讲述了中序遍历的思路及其实现代码(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;

}

具体代码实现可借鉴上篇文章【数据结构】二叉树的中序遍历,我把代码放在了评论区,请自行查看。

那么,今天的分享就到此结束了,谢谢查阅,欢迎留言交流。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180625G0KGKW00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

同媒体快讯

扫码关注云+社区

领取腾讯云代金券