数据结构与算法分析之树（1）

1.1 树的相关概念

• 树的定义：树是由n(n>=1)个有限结点组成一个具有层次关系的集合。把它叫做树，是因为它看起来像是一个倒挂的树，也就是它根朝上，而叶朝下。
  
• 树的特点：
  • 每个结点有0或多个子结点
  • 没有父节点的结点称为根结点
  • 每一个非根结点只有一个父结点
  • 每个结点及其后代结点整体上可以看做是一棵树，称为当前结点的父结点的一个子树。
• 结点的度：一个结点含有的子树的个数称为该结点的度。
• 叶结点：度不为0的结点称为分支结点，也可以叫做非终端结点
• 结点的层次：从根结点开始，根结点的层次为1，根的直接后继结点层次为2，以此类推。
• 结点的层序编号：将树种的结点，按照从上层到下层，同层从左到右依次排序成一个线性序列，把他们编成连续的自然数。
• 树的度：树中所有结点的度的最大值。
• 树的高度（深度）：树中结点的最大层次。
• 森林：m(m>=0)个互不相交的树的集合，将一颗非空树的根结点删去，树就变成了一个森林；给森林增加一个统一的根结点，森林就变成一棵树。
  
• 孩子结点：一个结点的直接后继结点称为该结点的孩子结点。
• 双亲结点：一个结点的直接前驱结点称为该结点的双亲结点。
• 兄弟结点：同一双亲结点的孩子结点间互称兄弟结点。

1.2 二叉树

1.2.1 二叉树的基本定义

• 二叉树就是度不超过2的树(每个结点最多有两个子结点)
  
• 满二叉树：一个二叉树，如果每一个层的结点树都达到最大值，则这个二叉树就是满二叉树。
  
• 完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。
  
• 二叉树API设计
  

1.2.2 二叉查找树

• 二叉查找树的API设计：
  
  
  

1.2.3 二叉树的遍历

• 前序遍历：先访问根节点，然后再访问左子树，最后访问右子树。
• 中序遍历：先访问左子树，再访问根节点，最后访问右子树。
• 后序遍历：先访问左子树，再访问右子树，最后访问根节点。
• 层序遍历：从根节点开始，从上往下，从左往右访问所有节点。（EBGADFHC）
  

1.2.4 二叉树相关代码

package com.tiger.study.DataStructure.Tree;

import com.sun.corba.se.impl.resolver.SplitLocalResolverImpl;
import com.tiger.study.DataStructure.Linear.Queue;
import org.jetbrains.annotations.NotNull;

public class BinaryTree<Key extends Comparable<Key>, Value> {
    // 根节点
    private Node root;

    // 记录结点个数
    private int N;

    // 获取树中元素的个数
    public int size() {
        return N;
    }

    // 向树中添加元素key-value
    public void put(Key key, Value value) {
        root = put(root, key, value);
    }

    // 向树x中添加元素key-value，并返回添加元素后的新的树
    public Node put(Node x, Key key, Value value) {
        // 如果x子树为空，让新的结点成为root结点
        if (x == null) {
            N++;
            return new Node(key, value, null, null);
        }

        // 如果x不为空
        // 比较x结点的键和key的大小
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            // 如果key小于x结点的键，则继续找x结点的左子树
            x.right = put(x.right, key, value);
        } else if (cmp < 0) {
            // 如果key大于x结点的键，则继续找x结点的右子树
            x.left = put(x.left, key, value);
        } else {
            // 如果key等于x结点的键，则替换x结点的值
            x.value = value;
        }

        return x;
    }

    // 查询树中指定的key对应的value
    public Value get(Key key) {
        return get(root, key);
    }

    // 从指定树中查找key对应的值
    public Value get(Node x, Key key) {
        // 先判断x是否等于null
        if (x == null) {
            return null;
        }
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            return get(x.right, key);
        } else if (cmp < 0) {
            return get(x.left, key);
        } else {
            return x.value;
        }
    }

    // 删除树中key对应的value
    public void delete(Key key) {
        root = delete(root, key);
    }

    // 删除指定树x中的key对应的value，并返回删除后的新树
    public Node delete(Node x, Key key) {
        // x树为null
        if (x == null) {
            return null;
        }

        // x树不为null
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            // 如果key大于x的结点的键，则继续找x结点的右子树
            x.right = delete(x.right, key);
        } else if (cmp < 0) {
            // 如果key小于x结点的键，则继续找x结点的左子树
            x.left = delete(x.left, key);
        } else {
            // 让元素个数-1
            N--;
            // 真正的删除
            // 找到右子树中最小的结点
            if (x.right == null) {
                return x.left;
            }

            if (x.left == null) {
                return x.right;
            }

            Node minNode = x;
            while (minNode.left != null) {
                minNode = minNode.left;
            }
            // 删除右子树中最小的结点
            Node n = x;
            while (n.left != null) {
                if (n.left.left == null) {
                    n.left = null;
                } else {
                    n = n.left;
                }
            }
            // 让x结点的左子树成为minNode的左子树
            minNode.left = x.left;

            // 让x结点的右子树成为minNode的右子树
            minNode.right = x.right;

            // 让x结点的父节点指向minNode
            x = minNode;

        }
        return x;
    }

    // 找到整个树中最小的键
    public Key min() {
        return min(root).key;
    }

    // 找到指定树中最小的键
    public Node min(Node x) {
        if (x.left == null) {
            return x;
        } else {
            return min(x.left);
        }
    }

    // 找到整个树中最大的键
    public Key max() {
        return max(root).key;
    }

    // 找到指定树中最大的键
    public Node max(Node x) {
        if (x.right != null) {
            return max(x.right);
        } else {
            return x;
        }
    }

    // 使用前序遍历，获取整个树中的所有键
    public Queue<Key> preErgodic() {
        Queue<Key> keys = new Queue<>();
        preErgodic(root, keys);
        return keys;
    }

    // 获取指定数组x的所有键，并放到keys队列中
    private void preErgodic(Node x, Queue<Key> keys) {
        if (x == null) {
            return;
        }

        // 把结点key放入到keys中
        keys.enqueue(x.key);

        // 递归遍历左子树
        if (x.left != null) {
            preErgodic(x.left, keys);
        }

        // 递归遍历右子树
        if (x.right != null) {
            preErgodic(x.right, keys);
        }
    }

    // 使用中序遍历，获取整个树中的所有键
    public Queue<Key> midErgodic() {
        Queue<Key> keys = new Queue<>();
        midErgodic(root, keys);
        return keys;
    }

    // 获取指定数组x的所有键，并放到keys队列中
    private void midErgodic(Node x, Queue<Key> keys) {
        if (x == null) {
            return;
        }

        // 先将左子树中的键放到keys中
        if (x.left != null) {
            midErgodic(x.left, keys);
        }

        // 将中间的键放到keys中
        keys.enqueue(x.key);

        // 将右子树的键放到左子树中
        if (x.right != null) {
            midErgodic(x.right, keys);
        }
    }

    // 后续遍历
    public Queue<Key> afterErgodic() {
        Queue<Key> keys = new Queue<>();
        afterErgodic(root, keys);
        return keys;
    }

    // 后续遍历
    private void afterErgodic(Node x, Queue<Key> keys) {
        if (x == null) {
            return;
        }

        if (x.left != null) {
            afterErgodic(x.left, keys);
        }

        if (x.right != null) {
            afterErgodic(x.right, keys);
        }

        keys.enqueue(x.key);

    }

    // 层序遍历
    public Queue<Key> layerErgodic() {
        // 备用队列，用于存放结点，因为队列的先进先出的特性，这样我们每次可以将左结点放入队列，然后在将右子结点放入队列
        Queue<Node> nodes = new Queue<Node>();
        // 用于存储key
        Queue<Key> keys = new Queue<>();
        // 先将根节点放入队列中，这样while循环就可以使用了
        nodes.enqueue(root);
        // 判断nodes队列是否为空，空的话所有结点都遍历完了
        while (!nodes.isEmpty()) {
            // 先弹出一个结点
            Node dqNode = nodes.dequeue();

            // 如果该结点有左子节点，就把左子节点放入备用队列
            if (dqNode.left != null) {
                nodes.enqueue(dqNode.left);
            }

            // 如果该结点有右子节点，就把右子节点放入备用队列
            if (dqNode.right != null) {
                nodes.enqueue(dqNode.right);
            }

            // 将当前结点的key放入keys队列
            keys.enqueue(dqNode.key);
        }
        return keys;
    }

    // 最大深度
    public int maxDepth() {
        return maxDepth(root);
    }

    private int maxDepth(Node x) {
        if (x == null) {
            return 0;
        }

        // 左子树的最大深度
        int leftChildTreeDepth = 0;
        if (x.left != null) {
            leftChildTreeDepth = maxDepth(x.left);
        }

        // 右子树的最大深度
        int rightChildTreeDepth = 0;
        if (x.right != null) {
            rightChildTreeDepth = maxDepth(x.right);
        }

        return Math.max(leftChildTreeDepth, rightChildTreeDepth) + 1;
    }

    private class Node {
        Node left;
        Node right;
        Key key;
        Value value;

        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304

1.3 折纸问题

• 需求
  
• 分析
  
• 代码实现

package com.tiger.study.DataStructure.Test.Tree;

import com.tiger.study.DataStructure.Linear.Queue;
import com.tiger.study.DataStructure.Tree.BinaryTree;

public class PageFolding {
    public static void main(String[] args) {
        // 纸对折的次数
        int times = 2;

        // 创建树
        Node tree = createTree(times);

        // 中序遍历树
        printErgodic(tree);


    }

    public static Node<String> 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 tmp = queue.dequeue();
                // 如果有左子节点放入到队列中
                if (tmp.left != null) {
                    queue.enqueue(tmp.left);
                }
                // 如果有右子节点放入到队列中
                if (tmp.right != null) {
                    queue.enqueue(tmp.right);
                }

                // 如果左右子节点都没有，给该结点添加左右子节点
                if (tmp.left == null && tmp.right == null) {
                    tmp.left = new Node<>("down", null, null);
                    tmp.right = new Node<>("up", null, null);
                }

            }

        }
        return root;
    }

    // 打印数组中每个结点到控制台
    public static void printErgodic(Node<String> n) {
        if (n == null) {
            return;
        }

        if (n.left != null) {
            printErgodic(n.left);
        }

        System.out.printf(n.item + " ");

        if (n.right != null) {
            printErgodic(n.right);
        }
    }

    private static class Node<T> {
        public T item;
        public Node left;
        public 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
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