二叉树应用

问题1：

打印二叉树.png

思路：

假设折三次，折完之后的折痕就是下下上下下上上，按照每次折的开始建立二叉树（建立过程中才知道是二叉树的）

1 下
/
2 下 上
/ \ /
3 下 上 下 上

这样的结构，再和打印的顺序对应，发现是二叉树的中序遍历，代码如下，递归实现

代码：

    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);
    }

    public static void main(String[] args) {
        int N = 4;
        printAllFolds(N);

    }

在这里说一下递归，注意递归就可以看作是系统帮你实现的一个栈，自动进出栈，以本题为例，如下图

栈实现递归过程.png