二叉树的层次遍历

思路：二叉树的遍历分为前序遍历、中序遍历和后序遍历。这是我们学习二叉树需要掌握的最基础的三个操作。那么除了前中后序遍历以外，还有一种层次遍历，即将树的某节点和它的兄弟节点所在位置称为一层。如图所示：

image.png

我们假设从左往右的方向进行访问，层次遍历结果为：A B C D E F G H I 。
为了完成这样的遍历，需要准备一个辅助队列Queue。

首先将根节点入队：

image.png

首先判断队列是否为空（这个时候肯定是不空的，根节点被放进去了），如果为空跳出循环。如果队列不为空，出队一个节点进行访问并判断是否有左子节点或者右子节点，如果有就将子节点入队；（注意：这个顺序如果颠倒 即右子节点先入队就是从右向左访问了）就变成了这个样子。

image.png

image.png

思路已经了解了，代码实现如下：
节点类：

public class BinaryTreeNode {

    private int no;
    private String info;
    private BinaryTreeNode left;
    private BinaryTreeNode right;
//省略set get 构造器等...
}

层次遍历方法：

public void levelList(){
        if(heroNode==null){
            return;
        }
        ArrayDeque<BinaryTreeNode> arrayDeque = new ArrayDeque();
        arrayDeque.add(heroNode);
        while (!arrayDeque.isEmpty()){
            BinaryTreeNode node = arrayDeque.poll();
            System.out.println(node.toString());
            if(node.getLeft()!=null){
                arrayDeque.add(node.getLeft());
            }
            if(node.getRight()!=null){
                arrayDeque.add(node.getRight());
            }
        }
    }

public class TestBinaryTree {
    public static void main(String[] args) {
        BinaryTreeNode binaryTreeNode = new BinaryTreeNode(1,"hu");
        BinaryTreeNode binaryTreeNode2 = new BinaryTreeNode(2,"shi");
        BinaryTreeNode binaryTreeNode3 = new BinaryTreeNode(3,"chen");
        BinaryTreeNode binaryTreeNode4 = new BinaryTreeNode(4,"guo");
        BinaryTreeNode binaryTreeNode5 = new BinaryTreeNode(5,"liu");
        
        binaryTreeNode.setLeft(binaryTreeNode2);
        binaryTreeNode.setRight(binaryTreeNode3);
        binaryTreeNode3.setLeft(binaryTreeNode4);
        binaryTreeNode3.setRight(binaryTreeNode5);
        
        BinaryTreeUtil binaryTreeUtil = new BinaryTreeUtil(binaryTreeNode);

        binaryTreeUtil.levelList();

    }
}

image.png