折纸问题 C++实现

折纸问题 C++实现

题目描述：

把纸条竖着放在桌面上，然后从纸条的下边向上对折，压出折痕后再展开。如果每次都从下边向上对折，对折N次。

我们规定，对于每条折痕，如果突起的方向指向纸条的背面，那么这条折痕叫做“下”折痕 ；相反，突起的方向指向纸条正面的折痕叫做“上”折痕。

请从上到下打印所有折痕的方向。

分析：

当纸条从下向上对折一次后打开，有一条折痕，向下，记为0。

继续再向上对折一次，打开后，在原来0号折痕上下各出现一条新折痕，上边折痕向下，记为1号。下边折痕向上，记为2号。

继续再向上对折一次，打开后，在1号折痕和2号折痕上下各出现一条新折痕，仍旧上边向下，下边向上。

结论：

由以上分析可以看出，对于每一条折痕，其上下新产生的折痕必是：上边的那条向下，下边的那条向上。

这样看来，按照折痕产生的先后顺序，其实是满二叉树结构。该二叉树的特点是：根结点是下，每一个节点的左子结点是下，右子结点是上。该二叉树的中序遍历即为答案。

实现：

我们用一个假想的一维数组来模拟这个满二叉树，如果折叠N次，那么共有