1、层次遍历
层次遍历就是即逐层地，从左到右访问所有节点。如下
2、方法实现思路
对于层序遍历，无疑是一层一层结点查找。那我们能不能找一个队列，把每一层的结点依次放入队列中，这样我们就能实现程序遍历啦。
首先创建一个队列，然后把根节点放入队列中。
接着就把 queue 的头结点弹出，也就是A，放到 cur中去，并打印。此时 cur 指向 A结点
cur 设置的目的：方便我们把下一层结点结点放到队列当中。
队列特点： 先进先出。
我们判断 cur 的左结点是否为空，如果不为空就把左结点放入队列中。同时我们也要判断cur的右节点，操做相同。
每弹出一个结点，就会把该节点的左右孩子插入到队列中（左右孩子不为空的情况下！），然后弹出队列头结点。
也就是一层一层遍历，比如遍历完B后，把B的左右孩子放到C的后面，直到遍历完C后（第二层）才会遍历B的左右孩子（第三层）。
总结：
定义一个队列，把root根节点放入队列中。
弹出对头节点，并遍历打印。
判断当前节点的左右孩子是否为null，如果不为null，则入队。
检测队列，如果队列为空，则说明层序遍历结束。
层次遍历对于二叉树来说算是比较基础的一种算法，其拓展了许多。例如判断二叉树是否为满二叉树等。
大家还可以去做 leetcode 做一下这道题加以巩固：二叉树的层序遍历
3、代码实现
import java.util.Queue;//导入队列的包 public class BinaryTree { //内部类 static class TreeNode { public char val; public TreeNode left;//左孩子的引用 public TreeNode right;//右孩子的引用 public TreeNode(char val) { this.val = val; } } /** * 创建一棵二叉树 返回这棵树的根节点 * * @return */ public TreeNode createTree() { TreeNode A = new TreeNode('A'); TreeNode B = new TreeNode('B'); TreeNode C = new TreeNode('C'); TreeNode D = new TreeNode('D'); TreeNode E = new TreeNode('E'); TreeNode F = new TreeNode('F'); TreeNode G = new TreeNode('G'); TreeNode H = new TreeNode('H'); A.left = B; A.right = C; B.left = D; B.right = E; C.left = F; C.right = G; E.right = H; return A; } //层序遍历 void levelOrder(TreeNode root) { if(root == null) return; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ TreeNode cur = queue.poll(); System.out.print(cur.val); if(cur.left != null){ queue.offer(cur.left); } if(cur.right != null){ queue.offer(cur.right); } } } public static void main(String[] args) { BinaryTree bt = new BinaryTree(); TreeNode root = bt.createTree(); bt.levelOrder(root); } }
代码中树的形状，和代码结果如下
注：
Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。
在使用时我们要导入 import java.util.Queue ;
Queue中的方法：
