二叉树解决折纸问题_二叉树折纸

二叉树解决折纸问题

前言

请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时 折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2 次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。
给定一 个输入参数N，代表纸条都从下边向上方连续对折N次，请从上到下打印所有折痕的方向 例如：N=1时，打印： down；N=2时，打印： down down up

一、折纸问题转为二叉树

我们把对折后的纸张翻过来，让粉色朝下，这时把第一次对折产生的折痕看做是根结点，那第二次对折产生的下折痕就是该结点的左子结点，而第二次对折产生的上折痕就是该结点的右子结点，这样我们就可以使用树型数据结构来描述对折后产生的折痕。
这棵树有这样的特点：
1.根结点为下折痕；
2.每一次在所有的叶子结点添加左右子结点
3.每一个结点的左子结点为下折痕；
4.每一个结点的右子结点为上折痕；

二、具体实现

• 1.定义结点类

//树节点
    private static class Node<T>
    {
        T item;
        Node left;
        Node right;
        public Node(T item,Node left,Node right)
        {
            this.item=item;
            this.left=left;
            this.right=right;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

• 2.构建深度为N的折痕树；
  因为每次要在所有叶子结点上添加左右结点，所以首先要找到所有的叶子结点，而对于折纸问题的二叉树，叶子结点都在最后一层，可以利用层序遍历的思想找到所有叶子结点，然后添加左右子结点即可。

 //利用层序遍历的思想，创建树
    public static Node createTree(int n)
    {
        Node<String> root=null;
        for (int i = 0; i < n; i++) {
            //如果是第一次对折，则创建根节点
            if(i==0) {
                root = new Node<>("down", null, null);
                continue;
            }

            //如果不是第一次对折，找到叶子结点（利用层序遍历的思想找到叶子节点），然后添加叶子节点的左右子结点
            Queue<Node> queue = new Queue<>();//采用层序思想，用以存储结点的队列
            queue.enqueue(root);

            //循环遍历队列
            while (!queue.isempty()){
                //弹出一个节点
                Node<String> temp = queue.dequeue();
                //如果存在左子结点，则将其入队
                if (temp.left!=null)
                    queue.enqueue(temp.left);
                //如果存在右子结点，则将其入队
                if (temp.right!=null)
                    queue.enqueue(temp.right);
                //如果左右结点都不存在，则该节点即为叶子节点，添加左右子结点即可
                if (temp.left==null&&temp.right==null)
                {
                    temp.left=new Node<String>("down",null,null);
                    temp.right=new Node<String>("up",null,null);
                }
            }
        }
        return root;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

• 3.使用中序遍历，打印出树中所有结点的内容；

//中序遍历并打印子树x
    public static void midOrderPrint(Node x)
    {
        if(x==null)
            return;
        //打印左子树
        if (x.left!=null)
            midOrderPrint(x.left);
        //打印根节点
        System.out.print(x.item+" ");
        //打印右子树
        if (x.right!=null)
            midOrderPrint(x.right);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

三、代码运行

 public static void main(String[] args) {
        //1.生成n次对折后的二叉树
        Node tree = createTree(2);
        //2.遍历二叉树，打印出n次对折后，折痕情况
        midOrderPrint(tree);
    }
1
2
3
4
5
6

• 折2次结果

down down up
1

• 折6次结果

down down up down down up up down down down up up down up up down down down up down down up up up down down up up down up up down down down up down down up up down down down up up down up up up down down up down down up up up down down up up down up up 
1