二叉树的层次遍历

在上一篇文章

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

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

}

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

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