二叉树的递归、非递归遍历
介绍：
本文简单的介绍一下二叉树的前、中、后序遍历的递归和非递归的实现方法。最后再来看看一道折纸问题来加深对遍历的理解。
先简单说说概念：
顾名思义：
前序遍历：二叉树结点的访问顺序为 ： 根节点、左节点、右节点。
中序遍历：二叉树结点的访问顺序为 ： 左节点、根节点、右节点。
后序遍历：二叉树结点的访问顺序为 ： 左节点、右节点、根节点。
递归和非递归的关系。理论上来说可以用递归方法实现的，也可以用非递归方法实现。因为递归的实现无非就是利用了函数栈来保存信息，方便进行下一次递归回来的时候还能找到现场。如果我们可以自己创建一个数据结构来代替这个函数栈，也是可以实现同样的功能的。
正文开始：
我们先用一个二叉树来举例，这个二叉树长成这种样子：
前序遍历
遍历结果为：1、2、4、5、3、6、7
递归方法实现：
public static void preOrderRecur(Node head){
if(head == null){
return;
}
System.out.println(head.value);
preOrderRecur(head.left);
preOrderRecur(head.right);
}
非递归方法实现：
思路： 记住栈装进去元素的顺序和弹出来元素的顺序是相反的。
因为顺序是 前、左、右。
所以就先弄个栈，把根节点放进去，再弹出来打印其值。先看右节点，再看左节点，不是空的时候放入栈中，弹出来就是左右了。直到这个栈为空为止，这时这棵树也遍历完了。
public static void preOrderUnrecur(Node head){
if(head != null){
Stack<Node> stack = new Stack<Node>();
stack.add(head);
while( !stack.isEmpty() ){
head = stack.pop();
System.out.println(head.value);
if(head.right != null){
stack.add(head.right);
}
if(head.left != null){
stack.add(head.left);
}
}
}
}
中序遍历
遍历结果为：4、2、5、1、6、3、7
递归实现方法：
public static void inOrderRecur(Node head){
if(head == null){
return ;
}
inOrderRecur(head.left);
System.out.println(head.value);
inOrderRecur(head.right);
}
非递归实现方法：
思路：一直往左边界找，依次加入栈中。知道最后的节点的左孩子为空，弹出它并打印它，这完成了“前”这位置的遍历。再看其有没有右孩子，有的话，再找其左边界，依次加入栈中，总之就是先把他们的左边界全部找完。直到左右孩子都没有了，弹出栈顶元素，这完成了“中”这个位置的遍历。如果该元素有右孩子，再将其有孩子加入栈中，重复，再弹出，这完成了“后”这个位置的遍历。
public static void inOrderUnrecur(Node head){
if(head != null){
Stack<Node> stack = new Stack<Node>();
while( !stack.isEmpty() || head != null){
if(head != null){
stack.add(head);
head = head.left;
}else{
head = stack.pop();
System.out.println(head.value);
head = head.right;
}
}
}
}
后序遍历
遍历结果为：4 、5、2、6、7、3、1
递归实现方法：
public static void posOrderRecur(Node head){
if(head == null){
return ;
}
posOrderRecur(head.left);
posOrderRecur(head.right);
System.out.println(head.value);
}
非递归实现方法：
思路： 记住栈装进去元素的顺序和弹出来元素的顺序是相反的。
因为遍历顺序是 左、右、中。
所以： 准备2个栈，分别为s1、s2。最后弹出s2全部元素即可。
在s1中先加入根节点，弹出转入s2中，此时根先加入，所以弹出时在最后。
然后看弹出的元素是否有左、右孩子（先看左，再看右），有的话加入s1中，重复之前的步骤。这样弹出到s2时先右后左，出来就是左、右、中这个顺序了。
public static void posOrderUnrecur(Node head){
if(head != null){
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
s1.add(head);
while( !s1.isEmpty() ){
head = s1.pop();
s2.add(head);
if(head.left != null){
s1.add(head.left);
}
if(head.right != null){
s1.add(head.right);
}
}
while( !s2.isEmpty() ){
System.out.println(s2.pop().value);
}
}
}
折纸问题
思路：
其实很简单，找张纸来试着折一下就好了。对折一次，折痕在中间向下，以后每次对折，都会在折痕的上下两方多出一个折痕，上面为朝向下的折痕，下面为朝向上的折痕。
也就是说可以把折痕的方向当成一颗二叉树，示意图如下，图中框起来的部分就是题目所要求的答案。
所以的答案就是看怎么遍历这颗树了，从上往下看的话，就是右、中、左这个顺序遍历二叉树了。（每个节点都是折痕，都要用到，都要出现在答案里）
实现代码：
/**
* 解决折纸问题的函数
* @param N： 一共折了多少次
*/
public static void printAllFolds(int N){
printProcess(1, N, true);
}
public static void printProcess(int i, int N, boolean down){
if(i > N){
return;
}
printProcess(i+1, N, true); // 先是“右”这个位置，折痕是向下的。
System.out.println(down ? "down" : "up"); // “中”这个位置，打印出来即可。
printProcess(i+1, N, false); // 再是“左”这个位置，折痕是向上的。
}