说到树的层次遍历，就应该提到广度优先搜索算法------广度优先搜索算法（Breadth-First-Search），又译作宽度优先搜索，或横向优先搜索，简称BFS，是一种图形搜索算法。
可以说树层次遍历是广度优先遍历的一种直接应用吧，比较广度优先搜索是图形的一种搜索算法，图形是一种比较大的概念，但这个和深度优先齐名的算法，在树的层次遍历引用中，并没有那么复杂，或许是因为用在树的遍历，而非图吧。
树的层次遍历，故名思议，在一棵树中，把节点从左往右，一层一层的，从上往下，遍历输出，这里要用到一种很重要的数据结构，队列，一提到队列，我们就要想到先进先进先，即为先进入队列元素，先接受处理，我们在日常生活中排队时，就是先到的人，先接受服务。
理解好队列，可以很容易的解决树的层此遍历，步骤如下：
1.首先将根节点放入队列中。
2.当队列为非空时，循环执行步骤3到步骤5，否则执行6；
3.出队列取得一个结点，访问该结点；
4.若该结点的左子树为非空，则将该结点的左子树入队列；
5.若该结点的右子树为非空，则将该结点的右子树入队列；
6.结束。
代码：
/***************************************
* 时间：2013年12月2日
* author：lm
* 内容：二叉树的层次遍历
***************************************/
import java.util.ArrayDeque;
import java.util.Queue;
public class BinTree { private char date; private BinTree lchild; //左孩子 private BinTree rchild; //右孩子 private BinTree(char c ){ date = c; } public static void BFSOrder(BinTree t) { if(t==null) return ; Queue<BinTree> queue = new ArrayDeque<BinTree>(); //队列小知识：使用offer和poll优于add和remove之处在于它们返回值可以判断成功与否，而不抛出异常 queue.offer(t); //进入队列 while(!queue.isEmpty()) { t=queue.poll(); //当前节点出队列 System.out.print(t.date); if(t.lchild!=null) //当前节点左孩子去排队，在前面哦 queue.offer(t.lchild); if(t.rchild!=null) //右孩子排第二 queue.offer(t.rchild); } } public static void main(String[] args) { BinTree b1 = new BinTree('a'); BinTree b2 = new BinTree('b'); BinTree b3 = new BinTree('c'); BinTree b4 = new BinTree('d'); BinTree b5 = new BinTree('e'); BinTree b6 = new BinTree('f'); BinTree b7 = new BinTree('g'); /** * a * / * b c * / / * d e f g */ b1.lchild = b2; b1.rchild = b3; b2.lchild = b4; b2.rchild = b5; b3.lchild = b6; b3.rchild = b7; BinTree.BFSOrder(b1); System.out.println(); } }
另外还写了树的三种深度优先遍历的递归与非递归算法: