介绍：

本文简单的介绍一下二叉树的前、中、后序遍历的递归和非递归的实现方法。最后再来看看一道折纸问题来加深对遍历的理解。
先简单说说概念：
顾名思义：
前序遍历：二叉树结点的访问顺序为 ： 根节点、左节点、右节点。
中序遍历：二叉树结点的访问顺序为 ： 左节点、根节点、右节点。
后序遍历：二叉树结点的访问顺序为 ： 左节点、右节点、根节点。

递归和非递归的关系。理论上来说可以用递归方法实现的，也可以用非递归方法实现。因为递归的实现无非就是利用了函数栈来保存信息，方便进行下一次递归回来的时候还能找到现场。如果我们可以自己创建一个数据结构来代替这个函数栈，也是可以实现同样的功能的。

正文开始：

我们先用一个二叉树来举例，这个二叉树长成这种样子：

前序遍历

遍历结果为：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);    // 再是“左”这个位置，折痕是向上的。
    }