Java教程

二叉树的层次遍历算法

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

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

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

如何实现?

思路:用队列

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

例子:

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

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

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

算法:

 

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

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

 

然后将根节点b入队qu

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

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

输出他的值p->data,

 

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

 

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

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

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

 

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