Python 每日一记248>>>Java二叉树实现折纸问题_python二叉树解决折纸问题

一、什么是折纸问题

上图摘自B站学习视频，再简单描述一下，将一张纸放在桌面上，为了方便，定义方向：
靠近你的方向是—近
远离你的方向是—远
左边方向是—左
右边方向是—右
纸面朝上方向是—上
纸面朝下方向是—下
从后往前折叠，折叠完毕后，原路展开，不要旋转也不要翻面，然后就会看到折痕，从远往近的折痕就是我们要输出的折痕，假如折叠了两次，那么折痕从远到近就是down—down—up。
要模拟成树的结构，先把纸顺时针旋转90度，直到正对你的是原来的右方向，然后翻面（左右翻转，而不是远近翻转），这个时候就变成了树结构，每个节点左节点都是down，右节点都是up。

二、Java代码实现

package mypackage;

import java.util.Iterator;

//队列类，用链表实现,遍历二叉树时需要用来装键
class Queue<T> implements Iterable<T>{
//    节点个数，头节点，尾节点
    private int N;
    private Node head;
    private Node last;
//节点类
    public class Node {
        public T data;
        public Node next;

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
//构造方法，初始化
    public Queue() {
        this.N = 0;
        this.head = new Node(null,null);
        this.last = null;
    }
//队列长度
    public int size(){
        return N;
    }
//队列是否为空
    public boolean isEmpty(){
        return N==0;
    }
//入队列
    public void enqueue(T data){
//        如果队列为空，说明尾节点为空，让新节点为尾节点，头借点指向尾节点
        if (isEmpty()){
            last=new Node(data,null);
            head.next=last;
//            如果队列不为空，让新节点为尾节点，老的尾节点指向新尾节点
        }else {
            Node oldlast=last;
            last=new Node(data,null);
            oldlast.next=last;
        }
//        最后元素+1
        N++;
    }
//出队列，注意先入先出，每次出的节点就是head指向的第一个节点，然后让head只想第二个节点即可
//    且注意，如果队列为空，要将last=null
    public T dequeue(){
//        如果为空，返回null
        if (isEmpty()){
            return null;
//            如果不为空，让head只想第二个节点，元素-1，且如果队列为空，要将last=null
        }else {
            Node oldfirst=head.next;
            head.next=oldfirst.next;
            N--;

            if (isEmpty()){
                last=null;
            }
//            返回弹出的元素
            return oldfirst.data;
        }
    }

    //    遍历
    @Override
    public Iterator iterator() {
        return new QIterator();
    }
    //    创建一个内部类实现Iterator接口
    public class QIterator implements Iterator {
        //        定义一个遍历的节点
        private Node n;

        public QIterator() {
//            初始化为0索引位置
            this.n = head;
        }

        //重写两个方法
        @Override
        public boolean hasNext() {
//            这个方法判断是否超出最大索引，如果超出会停止遍历
            return n.next != null;
        }

        @Override
        public Object next() {
//            这个方法会遍历得每个节点
            n = n.next;
            return n.data;
        }
    }
}


//测试
public class MyJava {

    public static void main(String[] args) {
//        返回树，其实是根节点
        Node tree=createtree(2);
        System.out.println("折叠2次，折痕从远到近依次如下:");
//        打印树，传入根节点
        midergodicPrint(tree);
    }
//    模拟折纸产生树,N为折叠次数，第一次折叠，为根节点down，此后每折叠一次，会将叶子节点左节点赋值为down，右节点赋值为up
    public static Node<String> createtree(int N){
//        定义根节点
        Node<String> root=null;
//        循环折叠次数
        for (int i = 1; i <=N ; i++) {
//            第一次折叠
            if (i==1){
                root=new Node<String>("down",null,null);
//             非第一次折叠，开始循环
            } else {
//                采用层序循环为叶子节点添加左右节点
//                先定义一个队列，用于层序循环
                Queue<Node> queue=new Queue<>();
//                先将root装进队列
                queue.enqueue(root);
//                如果队列不为空，开始循环，
//                循环中要经历的步骤为：
//                1、弹出队列中的一个元素
//                2、判断如果有左节点，将左节点加入到队列中
//                3、判断如果有右节点，将右节点加入到队列中
//                4、判断如果没有左右节点，将左节点赋值为down,右节点赋值为up
//                5、循环完毕后，返回根节点，后续通过这个根节点就可以遍历所有的节点
                while (!queue.isEmpty()){

                    Node node=queue.dequeue();
                    if (node.left!=null){
                        queue.enqueue(node.left);
                    }
                    if (node.right!=null){
                        queue.enqueue(node.right);
                    }
                    if (node.left==null&&node.right==null){
                        node.left=new Node("down",null,null);
                        node.right=new Node("up",null,null);
                    }
                }
            }
        }
//        返回根节点，代表整个数
        return root;
    }

//  遍历树并打印，采用中序遍历，左子树-根节点-右子树
    public static void midergodicPrint(Node<String> node){
//        如果为空，直接返回
        if (node==null){
            return;
        }
//        递归左子树
        if (node.left!=null){
            midergodicPrint(node.left);
        }
//        打印根节点
        System.out.print(node.data+"---");
//        递归左子树
        if (node.right!=null){
            midergodicPrint(node.right);
        }
    }
//    节点类
    public static class Node<T> {
        public T data;
        public Node left;
        public Node right;

        public Node( T data, Node left,Node right) {
            this.data = data;
            this.left =left;
            this.right =right;
        }
    }
}
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184

结果：
PS：折痕是从远到近距
折叠2次：

折叠3次：