【数据结构与算法】二叉树的层序遍历

﹏ヽ暗。殇╰゛Y 2022-08-21 03:07 149阅读 0赞

**转载请注明出处：****[http://blog.csdn.net/ns\_code/article/details/13169703][http_blog.csdn.net_ns_code_article_details_13169703]**

前面有篇博客详细分析了二叉树三种遍历（前序、中序、后序）方式的递归与非递归实现，参见：[**http://blog.csdn.net/ns\_code/article/details/12977901**][http_blog.csdn.net_ns_code_article_details_12977901]，但把二叉树的层序遍历算法给漏掉了，实际上也不能说漏掉了，毕竟层序遍历的实现方法与这三种遍历的实现方法有所不同，因此单独拿出来分析比较合适。

二叉树的层序遍历的实现还是比较简单的，由于其层级的关系，很明显要用到队列来辅助实现，主要是从左向右，自上而下，依次将二叉树的各节点入队，这样便可以保证输出的顺序是层序排列的。下面是算法的实现思想：

先将树的根节点入队，

如果队列不空，则进入循环

将队首元素出队，并输出它；

如果该队首元素有左孩子，则将其左孩子入队；

如果该队首元素有右孩子，则将其右孩子入队

C语言代码如下：

**\[cpp\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **void** LevelOrderTraverse(BiTree T,Status(\*Visit)(TElemType)) 
2.  \{ 
3.  //Visit是对节点操作的应用函数,
4.  //在这里，对每个数据元素调用函数Visit,也即是遍历了该节点 
5.   SqQueue q; 
6.   QElemType p; 
7.  **if**(T) 
8.   \{ 
9.   InitQueue(&q); 
10.  EnQueue(&q,T); 
11. **while**(!QueueEmpty(q)) 
12.  \{ 
13.  DeQueue(&q,&p); 
14.  Visit(p->data); 
15. **if**(p->lchild!=NULL) EnQueue(&q,p->lchild); 
16. **if**(p->rchild!=NULL) EnQueue(&q,p->rchild); 
17.  \} 
18.  printf("/n"); 
19.  \} 
20. \}

[http_blog.csdn.net_ns_code_article_details_13169703]: http://blog.csdn.net/ns_code/article/details/13169703
[http_blog.csdn.net_ns_code_article_details_12977901]: http://blog.csdn.net/ns_code/article/details/12977901
[view plain]: http://blog.csdn.net/ns_code/article/details/13169703#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/317586
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/317586/fork