一、二叉树的层次遍历原理
如图所示为二叉树的层次遍历，即按照箭头所指方向，按照1、2、3、4的层次顺序，对二叉树中各个结点进行访问(此图反映的是自左至右的层次遍历，自右至左的方式类似)。
二叉树层次遍历
要进行层次遍历，需要建立一个循环队列。先将二叉树头结点入队列，然后出队列，访问该结点，如果它有左子树，则将左子树的根结点入队:如果它有右子树，则将右子树的根结点入队。然后出队列，对出队结点访问，如此反复，直到队列为空为止。
整体上结合具体数据还是比较好理解的
这里需要注意的是对出队列的结点进行访问
二、实现代码
创建二叉树的方法前面文章已经写到了，这里直接调用，下面来看实现的方法
（注：队列方面我们使用java提供的ArrayDeque工具类）
public static void level(BTNode node) {
ArrayDeque<BTNode> queue = new ArrayDeque<>(20);
//首先将根节点加入栈中
queue.add(node);
//遍历二叉树
while (!queue.isEmpty()) {
BTNode tempNode = queue.poll();
System.out.print(tempNode.data + " ");
if(tempNode.leftChild != null){
queue.add(tempNode.leftChild);
}
if(tempNode.rightChild != null){
queue.add(tempNode.rightChild);
}
}
}
三、测试代码
/**
* 构建二叉树
* 3
* 2 4
* 5 2 2 4
* 5
* @param args
*/
public static void main(String[] args) {
int[] a = {3,2,4,5,2,2,4,5};
BTNode root = BTNodeUtil.createBTNodebyArray(a);
System.out.print("层次遍历为：");
level(root);
}
输出结果为：
层次遍历为：3 2 4 5 2 2 4 5
