二叉树的前序，中序，后序遍历的递归实现
树的遍历方式都多种，其中树的前序，中序，后序遍历方，在原理和代码实现上都有很大相似性，所以放在一块总结。前序，中序，后序这三种遍历方式的不同点在于根节点的遍历的顺序不同。
前序遍历：先输出根节点，在依次前序遍历左子树和右子树。
中序遍历：先中序遍历左子树，在输出根节点，最后中序遍历又子树
后序遍历：先后序遍历左子树，接着后序遍历右子树，最后输出根节点
对于图3-1所示的二叉树而言，三种遍历的结果如下：
前序遍历：1，2，4，5，3，6，7；
中序遍历：4，2，5，1，3，7，6
后序遍历：4，5，2，7，6，3，1
三种遍历方式的递归实现代码如下：
一丶 前序遍历：
public void PreOrder(TreeNode node){
if(node!=null){
System.out.print(node.val)
PreOrder(node.left);
PreOrder(node.right);
}
}
二丶中序遍历：
public void InOrder(TreeNode node){
if(node!=null){
PreOrder(node.left);
System.out.print(node.val)
PreOrder(node.right);
}
}
三丶后序遍历：
public void PostOrder(TreeNode node){
if(node!=null){
PreOrder(node.left);
PreOrder(node.right);
System.out.print(node.val)
}
}
从上述的代码中，可以看出递归实现二叉树的遍历代码是相当简介的，三种遍历方式的区别在于节点值输出的时机不同。
四丶二叉树的层次遍历
树的层次遍历，是从上往下，从左往右的一种遍历方式，对图4-1所示的树结构而言，其层次遍历的顺序如下：1-2-3-4-5-6-7。
树的层次遍历实现方式和树的前序，中序，后序等遍历方式不同，树的层次遍历利用队列的来实现，而其他三种遍历方式，多用栈和递归的代码来实现。下面利用图的方式来描述下层次遍历的过程，同时给出java代码的实现。
-
将根节点入队，此时队列情况如下
image -
判断队列是否为空，如果不空，则出队队首元素(非空，如果为空继续出队，直到非空)，并且打印，如图
image -
将出队元素的左节点和右节点压入队列中，如图
image -
重复步骤2-3，直到2队列为空，循环结束。
对于如图4-1所示的二叉树，其层次遍历的剩余过程如下：
image
通过如上的流程图，对二叉树层次遍历的过程就十分清楚了，在这个过程中，也许存在一个疑惑:在上述过程中，我们对null元素，也进入了入队操作，这个操作为什么不省略的，只对非空的节点入队? 如果我们只需要按照层次遍历的结果，从上往下，从左往右的打印二叉树的元素，那么对非空元素入队是可取的操作，但是节点的层次信息会丢失。比如先要求按照如下格式输出二叉树的层次遍历结果，就必须将非空元素入队，保留节点的层次信息。
[[1],[2,3],[4,5,6],[7]]
java代码的实现如下：
public voidprintLevel(TreeNode root){
inti=1; //每层应该有多少节点
intj=0;//每层的空节点数
Queue<Integer>queue= new LinkedList<Integer>();
queue.add(root);
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer>list = new ArrayList<Integer>();
while(queue.isEmpty()){
TreeNodenode =queue.remove();
j++;
continue;
}
list.add(node.val);
queue.add(node.left);
queue.add(node.right);
//如果非空节点数+空节点数=该层节点数，则存储层信息
if( i==(list.size()+j) &&list.size()>0 ){
List<Integer> temp =new ArrayList<Integer>();
//复制链接操作，自己实现
copy(temp,list);
result.add(temp);
list.clear();
i=i*2;//节点总数每层倍增
j=j*2;//空节点数每层倍增
}
}
System.out.println(result);
}
Reference:
[1] 数据结构与算法 java语言描述版
[2] 原文博客链接
