折纸问题（二叉树实现）

折纸问题（二叉树实现）

折纸问题

思路：
可以自己手动拿一个字条模拟这个过程。

• 第一次对折，发现折痕是向下的，用笔在对折处标记（1 下）
• 第二次对折，发现（1下）的上面的折痕是向下的，标记（2下）。下面的折痕是向上的，标记（2上）。
• 以此类推。
  
  发现规律：其实就是一个二叉树结构。根节点为下。每一个节点的左孩子节点都为下。右孩子节点都为上。输出结果即为二叉树的中序遍历

思路：构造一个函数。
public static void printProcess(int i, int N, boolean down)
参数含义：

• i : 当前在第i层
• N :折纸的次数。即为二叉树的总高度
• down: 初始值为true。即为向下的标识。false即为向上的标识。正是通过down的赋值来区分左子树还是右子树
  代码实现

public class PaperFolding {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 = 3;printAllFolds(N);}
}