折纸问题（二叉树实现）_二叉树模拟折纸

折纸问题

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

• 第一次对折，发现折痕是向下的，用笔在对折处标记（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);

	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18