二叉树的层次遍历算法

本文主要是介绍二叉树的层次遍历算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

前面学的二叉树的遍历是把二叉树看作3个部分：根，左子树，右子树，然后我们以此来访问3个部分

而层次遍历是把树看成从上到下的若干层：根结点在第一层，根结点的孩子在第二层，根结点的孩子的孩子在第三层，然后依次类推，从上到下一层一层来访问，每一层从左到右依次访问，每个结点只访问一次

如何实现？

思路：用队列

先将根结点入队，接下来就不断从队伍中去出队一个结点，同时，如果他有左右孩子，就分别将他的左右孩子入队，这就是访问顺序：首先是根结点，然后是他的左右孩子，左右孩子后面是他的左孩子的左右孩子，右孩子的左右孩子......

例子：

将a出队的同时，将他的两个孩子b,f入队

b出队的同时将c,d入队.....

这就是层次遍历的思路：先从根节点开始，依次是他的左右孩子，到左右孩子时，再分别把左右孩子的孩子继续入队，然后再将下一层入队，一层一层入队，再按入队的顺序一个一个出队

算法：

用顺序循环队列。用数组data[MaxSize]来存放队中的元素，另外我们有两个指针分别表示队头和队尾

首先初始化这个队列，InitQueue(qu)

然后将根节点b入队qu

再从队列中出队元素，出队前判断队列是否为空！QueueEmpty

若为空，就将队头元素用出队deQueue(qu,p)

输出他的值p->data,

若存在左孩子，就将左孩子入队

若存在右孩子，就将右孩子入队

当队列中没有元素时，循环结束

用到了队列初始化，入队，判断队空，出队操作

这篇关于二叉树的层次遍历算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！