模拟数据结构：二叉树_有啥模拟二叉树的结构

package com.zc.study;

/**
 * @author zc
 * 二叉树模拟
 * 包含了：二叉树的增删改查功能
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        Hero h1 = new Hero(1,"鸣人");
        Hero h2 = new Hero(2,"佐助");
        Hero h3 = new Hero(3,"小樱");
        Hero h4 = new Hero(4,"宁次");

        BinaryTree bt = new BinaryTree();
        bt.setRoot(h1);
        h1.setLeft(h2);
        h1.setRight(h3);
        h3.setRight(h4);

        System.out.println("前序遍历");
        bt.preOrder();
        System.out.println();

        System.out.println("中序遍历");
        bt.midOrder();
        System.out.println();

        System.out.println("后序遍历");
        bt.postOrder();
        System.out.println();

        System.out.println("前序查找");
        Hero hero1 = bt.preFind(4);
        System.out.println(hero1);
        System.out.println();

        System.out.println("中序查找");
        Hero hero2 = bt.preFind(3);
        System.out.println(hero2);
        System.out.println();

        System.out.println("后序查找");
        Hero hero3 = bt.preFind(2);
        System.out.println(hero3);
        System.out.println();

        System.out.println("清空指定ID节点");
        bt.deleteNode(2);
        bt.deleteNode(3);
        System.out.println();

        System.out.println("清空节点后的前序遍历");
        bt.preOrder();
        System.out.println();
    }
}

/**
 * 英雄类
 */
class Hero{
    private int id;
    private String name;

    /**左指针*/
    private Hero left;

    /**右指针*/
    private Hero right;

    public Hero(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Hero getLeft() {
        return left;
    }

    public void setLeft(Hero left) {
        this.left = left;
    }

    public Hero getRight() {
        return right;
    }

    public void setRight(Hero right) {
        this.right = right;
    }

    /**
     * 前序遍历
     * 步骤：先输出根节点，然后输出左节点、最后输出右节点，按层数输出
     */
    public void preOrder(){
        //输出主节点，不用非空判断，能调用方法证明就有了根节点
        System.out.println(this);
        //递归遍历左左节点
        if(this.left != null){
            this.left.preOrder();
        }
        //递归遍历右节点
        if(this.right != null){
            this.right.preOrder();
        }
    }

    /**
     * 中序遍历
     * 步骤：先输出左节点，然后输出根节点、最后输出右节点，按层数输出
     */
    public void midOrder(){
        //输出左节点
        if(this.left != null){
            this.left.midOrder();
        }
        //输出根节点
        System.out.println(this);
        //输出右节点
        if(this.right != null){
            this.right.midOrder();
        }
    }

    /**
     * 后序遍历
     * 步骤：先输出左节点，然后输出右节点、最后输出根节点，按层数输出
     */
    public void postOrder(){
        //输出左节点
        if(this.left != null){
            this.left.postOrder();
        }
        //输出右节点
        if(this.right != null){
            this.right.postOrder();
        }
        //输出根节点
        System.out.println(this);
    }

    /**
     * 前序查找：先根节点，再左节点，最后右节点
     * @return
     */
    public Hero findPreById(int id){
        //先主节点：判断当前主节点是否是被查找的节点
        if(this.id == id){
            return this;
        }
        Hero result = null;
        //再左节点：遍历左节点
        if(this.left != null){
            result = this.left.findPreById(id);
        }
        //假设左节点找到了，就返回
        if(result != null){
            return result;
        }
        //最后右节点
        if(this.right != null){
            result = this.right.findPreById(id);
        }
        //无论右节点是否找到，都返回
        return result;
    }

    /**
     * 中序查找：左节点 --> 根节点 --> 右节点
     * @return
     */
    public Hero findMid(int id){
        Hero result = null;
        //左节点
        if(this.left != null){
            result = this.left.findMid(id);
        }
        if(result != null){
            return result;
        }
        //根节点
        if(this.id == id){
            return this;
        }
        //右节点
        if(this.right != null){
            result = this.right.findMid(id);
        }
        //无论右节点是否找到，都要返回
        return result;
    }

    /**
     * 后序查找；左节点 --> 右节点 --> 根节点
     * @return
     */
    public Hero findPost(int id){
        Hero result = null;
        //左节点
        if(this.left != null){
            result = this.left.findPost(id);
        }
        if(result != null){
            return result;
        }
        //右节点
        if(this.right != null){
            result = this.right.findPost(id);
        }
        //根节点
        if(this.id == id){
            return this;
        }
        //无论右节点是否找到，都要返回
        return result;
    }

    /**
     * 删除节点
     * 规定：如果删除的是叶子节点，则直接删除该节点；如果删除的是非叶子节点，则直接删除该子树
     * 注意事项：由于我们的二叉树是单向的，所以我们只能通过判断该节点下一级的左节点或右节点是否是要删除的节点，而不是直接判断该节点是否是需要删除的节点
     * 步骤：先判断当前节点的左节点，再判断它的右节点，如果都不是，则继续递归循环该操作
     * 如果删除的是根节点，则直接将根节点的指针指向null即可，根节点的删除的在二叉树类中完成
     * @return
     */
    public void deleteNode(int id){
        //清空左节点：判断左节点是否是要删除的节点
        if(this.left != null && this.left.id == id){
            //清空左节点的指针
            this.left = null;
            //结束递归
            return;
        }
        //清空右节点：判断右节点是否是要删除的节点
        if(this.right != null && this.right.id == id){
            //清空右节点的指针
            this.right = null;
            //结束递归
            return;
        }

        //继续从当前节点的左节点递归
        if(this.left != null){
            this.left.deleteNode(id);
        }
        //继续从当前节点的右节点递归
        if(this.right != null){
            this.right.deleteNode(id);
        }
    }


    @Override
    public String toString() {
        return this.id + "-" + this.name;
    }
}

/**
 * 二叉树类
 */
class BinaryTree{
    /**二叉树根节点*/
    private Hero root;

    /**初始化二叉树根节点*/
    public void setRoot(Hero root) {
        this.root = root;
    }

    /**
     * 前序遍历
     */
    public void preOrder(){
        if(root != null){
            root.preOrder();
        }else{
            System.out.println("二叉树为空");
        }
    }

    /**
     * 中序遍历
     */
    public void midOrder(){
        if(root != null){
            root.midOrder();
        }else{
            System.out.println("二叉树为空");
        }
    }

    /**
     * 后序遍历
     */
    public void postOrder(){
        if(root != null){
            root.postOrder();
        }else{
            System.out.println("二叉树为空");
        }
    }

    /**
     * 前序查找
     */
    public Hero preFind(int id){
        Hero result = null;
        if(root != null){
            result = root.findPreById(id);
        }
        return result;
    }

    /**
     * 中序查找
     */
    public Hero midFind(int id){
        Hero result = null;
        if(root != null){
           result = root.findMid(id);
        }
        return result;
    }

    /**
     * 后序查找
     */
    public Hero postFind(int id){
        Hero result = null;
        if(root != null){
            result = root.findPost(id);
        }
        return result;
    }

    /**
     * 删除节点
     */
    public void deleteNode(int id){
        if(root == null){
            System.out.println("二叉树为空，无法删除");
            return;
        }
        //清空根节点的指针并终止代码运行
        if(root != null && root.getId() == id){
            root = null;
            return;
        }
        //如果删除的不是根节点，则继续向下寻找
        root.deleteNode(id);
    }
}



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
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374