【算法】【算法杂谈】折纸问题（完全二叉树解法）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法】【算法杂谈】折纸问题（完全二叉树解法）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
一张纸从下往上对折之后，出现一条折痕，该折痕凸起向下，所以叫“下折痕”，反之如果摊开之后，凸起向上，则叫上折痕。
如果一张纸从下往上对折两次，则折痕为 [下，下，上]如下图所示
【算法】【算法杂谈】折纸问题（完全二叉树解法）
问：
给定整数num，表示这张纸按照从下往上折叠的方式折叠num次，摊开之后，从上往下的折痕方向顺序是什么？
如：
num = 2
结果为：下下上

解决方案

原问题：
1、首先想一个问题，如果当前纸有一个向下的折痕，那么对于向下的折痕，我们再次对折时，在下面的纸张摊开后会形成向下的折痕，在上面的纸张会形成向上的折痕，因此我们能够确定，对于每一个向下的折痕都有这个规律
2、同理我们也可以发现，对于折叠好的向上的折痕，如果我们再次折叠会出现下上上
3、综合上面，还有一个规律就是每一次的折叠都是对当前折痕中的上上下下再次进行折叠，所以通过当前折痕是上和下即可判断出折好之后的三元组是什么，如当前折痕是下，那么折叠好摊开一定是下下上三元组，如果是上，那么一定是下上上三元组。
4、理解了上面三条我们就很容易的可以使用完全二叉树来进行折纸问题的计算，下图是折叠三次的示例
【算法】【算法杂谈】折纸问题（完全二叉树解法）

自己可以拿一张纸来折叠一下看看是不是这个规律，整体的就是这个完全二叉树的中序遍历！

代码编写

java语言版本

原问题：
方法一:

     /**
     * 二轮测试：纸张折叠num次之后，打印折痕
     * @param num
     */
    private static void printAllFoldersCp1(int num) {
        if (num <= 0) {
            return;
        }
        processCp1(num, null, null);
    }

    /**
     * 中序遍历，递归打印折痕
     * @param num
     * @param parent 父节点是上还是下
     * @param isLeft 是否左子节点
     */
    private static void processCp1(int num, Boolean parent, Boolean isLeft) {
        if (num == 0) {
            // 已经减到0了直接返回
            return;
        }
        Boolean cur = false;
        // 先判断自己的是上还是下
        if (parent == null || isLeft == null) {
            // 根节点直接下
            cur = false;
        }else if (!parent && isLeft) {
            // 根节点是下并且自己是左子树
            cur = false;
        }else if (!parent && !isLeft) {
            // 根节点是下，并且自己是右子树
            cur = true;
        }else if (parent && isLeft) {
            // 上左子树
            cur = false;
        }else if (parent && !isLeft) {
            cur = true;
        }
        // 判断完成后开始下一轮
        processCp1(num - 1, cur, true);
        // 输出自己
        System.out.println(cur ? "上" : "下");
        // 输出右边
        processCp1(num - 1, cur, false);
    }


    public static void main(String[] args) {
        printAllFolders(4);
    }

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

发现规律是一个难点：这个规律文字其实解释起来很麻烦，但是如果自己找一张纸折叠一下就会发现其实过程就是一个递归的过程，
对折这个动作就非常的“递归”，当对折的时候折痕两边的纸片都会被折叠，同样是折叠，只是下面的纸片向上折叠，而上面的纸片其实是一个向下折叠的过程，因为摊开的过程是一个翻转的过程，这个需要自己去慢慢体会一下
构造遍历方式也是一个难点：第一想法是先构造一个完全二叉树再遍历，如此一来，感觉有点憨憨
那么接下来如何能够节省空间的中序遍历呢？
首先num = 3，我们认为root节点高度为3，那么整体的顺序为左子树 -> root -> 右子树
其次，构造递归函数的入参，第一个入参：num不解释，第二个入参，parent，第三个入参当前是左子节点还是右子节点
因为只有知道自己的父节点和自己的位置是左边还是右边才能计算出来自己当前应该是上还是下。