数据结构与算法 系列教程（笔记）

# 二叉树

# 为什么需要该数据结构

# 数组存储方式的分析

  • 优点：
    • 通过 下标 方式访问元素，速度快
    • 对于 有序数组，还可以使用二分查找提高检索速度
  • 缺点：如果要检索具体某个值或插入值（按一定顺序）会整体移动，效率较低，如下的示意图

image-20201116143825510

# 链表存储方式的分析

  • 优点：在一定程度上对数组存储方式有优化

    例如：插入一个数值节点，只需要将插入节点，链接到链表中即可，同理，删除效率也很好

    image-20201116144728699

  • 缺点：检索效率较低

    需要从头结点开始遍历查找。

简单说：

  • 数组访问快，增删慢
  • 链表增删快，访问慢

那么就出现了 树 这种数据结构

# 树存储数据方式分析

提供数据 存储 、读取 效率。

例如：利用 二叉排序树（Binary Sort Tree），既可以保证数据的检索速度，同时也可以保证数据的插入、删除、修改 的速度

image-20201116145853845

如图所示：

  • 插入时，小的数在 左节点、大的数在 右节点
  • 查找时：根据插入事的特性，基本上就类似折半查找了，每次都过滤一半的节点
  • 删除时：只需要移动相邻的节点的引用

# 树的常用术语

image-20201116150501717

  • 节点：每一个圆圈表示一个节点，也称节点对象

  • 根节点：最上面，最顶部的那个节点，也就是一棵树的入口

  • 父节点：有子节点的节点

  • 子节点

  • 叶子节点：没有子节点的节点

  • 节点的权：可以简单的理解为节点值

    有时候也用 路径 来表示

  • 路径：从 root 节点找到该节点的路线

  • 层

  • 子树：有子节点的父子两层就可以称为是一个子树

  • 树的高度：最大层数

  • 森林：多颗子树构成森林

# 二叉树的概念

  • 树有很多种，每个节点 最多只能有两个子节点 的一种形式称为 二叉树

  • 二叉树的子节点分为 左节点 和 右节点

    image-20201116151129752

  • 如果该二叉树的所有 叶子节点 都在 最后一层，并且 节点总数 = 2n-1 （n 为层数），则我们称为 满二叉树

    image-20201116151616119

  • 如果该二叉树的所有叶子节点都在最 后一层或倒数第二层，而且 最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为 完全二叉树

    image-20201116151828693

# 二叉树的遍历说明

有三种：

  • 前序遍历：先输出父节点，再遍历左子树（递归）和右子树（递归）
  • 中序遍历：先遍历左子树（递归），再输出父节点，再遍历右子树（递归）
  • 后序遍历：先遍历左子树（递归），再遍历右子树（递归），最后输出父节点

看上述粗体部分：前中后说的就是父节点的输出时机。

注意理描述中的递归，这关乎着你如何找到下一个输出节点

# 二叉树遍历思路分析

image-20201116152811909

  • 前序遍历：

    1. 先输出当前节点（初始节点是 root 节点）
    2. 如果左子节点不为空，则递归继续前序遍历
    3. 如果右子节点不为空，则递归继续前序遍历

    上图的输出顺序为：1、2、3、4

  • 中序遍历：

    1. 如果当前节点的左子节点不为空，则递归中序遍历
    2. 输出当前节点
    3. 如果当前节点的右子节点不为空，则递归中序

    上图的输出顺序为：2、1、3、4

  • 后序遍历：

    1. 如果左子节点不为空，则递归继续前序遍历
    2. 如果右子节点不为空，则递归继续前序遍历
    3. 输出当前节点

    上图的输出顺序为：2、4、3、1

# 二叉树遍历代码实现

package cn.mrcode.study.dsalgtutorialdemo.datastructure.tree;

import org.junit.Test;

/**
 * 二叉树测试
 */
public class BinaryTreeTest {

    // 先编写二叉树节点
    class HeroNode {
        public int id;
        public String name;
        public HeroNode left;
        public HeroNode right;

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

        @Override
        public String toString() {
            return "HeroNode{" +
                    "id=" + id +
                    ", name='" + name + '\'' +
                    '}';
        }

        /**
         * 前序遍历
         */
        public void preOrder() {
            // 1. 先输出当前节点
            System.out.println(this);
            // 2. 如果左子节点不为空，则递归继续前序遍历
            if (this.left != null) {
                this.left.preOrder();
            }
            // 3. 如果右子节点不为空，则递归继续前序遍历
            if (this.right != null) {
                this.right.preOrder();
            }
        }

        /**
         * 中序遍历
         */
        public void infixOrder() {
            // 1. 如果左子节点不为空，则递归继续前序遍历
            if (this.left != null) {
                this.left.infixOrder();
            }
            // 2. 先输出当前节点
            System.out.println(this);

            // 3. 如果右子节点不为空，则递归继续前序遍历
            if (this.right != null) {
                this.right.infixOrder();
            }
        }

        /**
         * 后序遍历
         */
        public void postOrder() {
            // 1. 如果左子节点不为空，则递归继续前序遍历
            if (this.left != null) {
                this.left.postOrder();
            }
            // 2. 如果右子节点不为空，则递归继续前序遍历
            if (this.right != null) {
                this.right.postOrder();
            }
            // 3. 先输出当前节点
            System.out.println(this);
        }
    }

    // 编写二叉树对象
    class BinaryTree {
        public HeroNode root;

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

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

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

    // 编写二叉树对象

    /**
     * 前、中、后 遍历测试
     */
    @Test
    public void fun1() {
        // 创建节点与构建二叉树
        HeroNode n1 = new HeroNode(1, "宋江");
        HeroNode n2 = new HeroNode(2, "无用");
        HeroNode n3 = new HeroNode(3, "卢俊");
        HeroNode n4 = new HeroNode(4, "林冲");
        n1.left = n2;
        n1.right = n3;
        n3.right = n4;
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.root = n1;

        System.out.println("\n 前序遍历：");
        binaryTree.preOrder();
        System.out.println("\n 中序遍历：");
        binaryTree.infixOrder();
        System.out.println("\n 后序遍历：");
        binaryTree.postOrder();
    }

}
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

测试输出

 前序遍历：
HeroNode{id=1, name='宋江'}
HeroNode{id=2, name='无用'}
HeroNode{id=3, name='卢俊'}
HeroNode{id=4, name='林冲'}

 中序遍历：
HeroNode{id=2, name='无用'}
HeroNode{id=1, name='宋江'}
HeroNode{id=3, name='卢俊'}
HeroNode{id=4, name='林冲'}

 后序遍历：
HeroNode{id=2, name='无用'}
HeroNode{id=4, name='林冲'}
HeroNode{id=3, name='卢俊'}
HeroNode{id=1, name='宋江'}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

那么现在来考考你：

image-20201116163114510

给 卢俊义 增加一个节点 关胜，写出他的前、中、后序的打印顺序：

注意的是：上面这个新增的节点，并不是按照顺序增加的，这里考的知识点是 前、中、后序的遍历规则

  • 前序：1、2、3、5、4

  • 中序：2、1、5、3，4

  • 后序：2、1、5、4、3 -> 正确答案为： 2、5、4、3、1

    通过后面的程序检测，发现这里的确是答案错误了！

那么下面通过程序来检测答案是否正确：

    /**
     * 考题：给卢俊新增一个 left 节点，然后打印前、中、后 遍历顺序
     */
    @Test
    public void fun2() {
        // 创建节点与构建二叉树
        HeroNode n1 = new HeroNode(1, "宋江");
        HeroNode n2 = new HeroNode(2, "无用");
        HeroNode n3 = new HeroNode(3, "卢俊");
        HeroNode n4 = new HeroNode(4, "林冲");
        HeroNode n5 = new HeroNode(5, "关胜");
        n1.left = n2;
        n1.right = n3;
        n3.right = n4;
        n3.left = n5;
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.root = n1;

        System.out.println("\n 前序遍历：");
        binaryTree.preOrder();
        System.out.println("\n 中序遍历：");
        binaryTree.infixOrder();
        System.out.println("\n 后序遍历：");
        binaryTree.postOrder();
    }
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

输出信息

 前序遍历：
HeroNode{id=1, name='宋江'}
HeroNode{id=2, name='无用'}
HeroNode{id=3, name='卢俊'}
HeroNode{id=5, name='关胜'}
HeroNode{id=4, name='林冲'}

 中序遍历：
HeroNode{id=2, name='无用'}
HeroNode{id=1, name='宋江'}
HeroNode{id=5, name='关胜'}
HeroNode{id=3, name='卢俊'}
HeroNode{id=4, name='林冲'}

 后序遍历：
HeroNode{id=2, name='无用'}
HeroNode{id=5, name='关胜'}
HeroNode{id=4, name='林冲'}
HeroNode{id=3, name='卢俊'}
HeroNode{id=1, name='宋江'}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

可以看到，后序是最容易弄错的规则，所以在后续上，一定要多多 debug ，看下他的调用轨迹。

# 二叉树的查找

要求：

  1. 编写前、中、后序查找方法
  2. 并分别使用三种查找方式，查找 id=5 的节点
  3. 并分析各种查找方式，分别比较了多少次

由于二叉树的查找是遍历查找，所以就简单了，前面遍历规则已经写过了，改写成查找即可

package cn.mrcode.study.dsalgtutorialdemo.datastructure.tree;

import org.junit.Test;

/**
 * 二叉树测试
 */
public class BinaryTreeTest {

    // 先编写二叉树节点
    class HeroNode {
        public int id;
        public String name;
        public HeroNode left;
        public HeroNode right;

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

        @Override
        public String toString() {
            return "HeroNode{" +
                    "id=" + id +
                    ", name='" + name + '\'' +
                    '}';
        }

        /**
         * 前序遍历
         */
        public void preOrder() {
            // 1. 先输出当前节点
            System.out.println(this);
            // 2. 如果左子节点不为空，则递归继续前序遍历
            if (this.left != null) {
                this.left.preOrder();
            }
            // 3. 如果右子节点不为空，则递归继续前序遍历
            if (this.right != null) {
                this.right.preOrder();
            }
        }

        /**
         * 中序遍历
         */
        public void infixOrder() {
            // 1. 如果左子节点不为空，则递归继续前序遍历
            if (this.left != null) {
                this.left.infixOrder();
            }
            // 2. 先输出当前节点
            System.out.println(this);

            // 3. 如果右子节点不为空，则递归继续前序遍历
            if (this.right != null) {
                this.right.infixOrder();
            }
        }

        /**
         * 后序遍历
         */
        public void postOrder() {
            // 1. 如果左子节点不为空，则递归继续前序遍历
            if (this.left != null) {
                this.left.postOrder();
            }
            // 2. 如果右子节点不为空，则递归继续前序遍历
            if (this.right != null) {
                this.right.postOrder();
            }
            // 3. 先输出当前节点
            System.out.println(this);
        }

        /**
         * 前序查找
         */
        public HeroNode preOrderSearch(int id) {
            System.out.println("  进入前序遍历");  // 用来统计查找了几次
            // 1. 如何相等，则返回
            if (this.id == id) {
                return this;
            }
            // 2. 如果左子节点不为空，则递归继续前序遍历
            if (this.left != null) {
                HeroNode result = this.left.preOrderSearch(id);
                if (result != null) {
                    return result;
                }
            }
            // 3. 如果右子节点不为空，则递归继续前序遍历
            if (this.right != null) {
                HeroNode result = this.right.preOrderSearch(id);
                if (result != null) {
                    return result;
                }
            }
            return null;
        }

        /**
         * 中序查找
         */
        public HeroNode infixOrderSearch(int id) {
//            System.out.println("  进入中序遍历");  // 用来统计查找了几次，不能在这里打印，这里打印是进入了方法几次，看的是比较了几次
            // 1. 如果左子节点不为空，则递归继续前序遍历
            if (this.left != null) {
                HeroNode result = this.left.infixOrderSearch(id);
                if (result != null) {
                    return result;
                }
            }
            System.out.println("  进入中序遍历");
            // 2. 如果相等，则返回
            if (this.id == id) {
                return this;
            }

            // 3. 如果右子节点不为空，则递归继续前序遍历
            if (this.right != null) {
                HeroNode result = this.right.infixOrderSearch(id);
                if (result != null) {
                    return result;
                }
            }
            return null;
        }

        /**
         * 后序查找
         */
        public HeroNode postOrderSearch(int id) {
//            System.out.println("  进入后序遍历");  // 用来统计查找了几次，不能在这里打印，这里打印是进入了方法几次，看的是比较了几次
            // 1. 如果左子节点不为空，则递归继续前序遍历
            if (this.left != null) {
                HeroNode result = this.left.postOrderSearch(id);
                if (result != null) {
                    return result;
                }
            }
            // 2. 如果右子节点不为空，则递归继续前序遍历
            if (this.right != null) {
                HeroNode result = this.right.postOrderSearch(id);
                if (result != null) {
                    return result;
                }
            }
            System.out.println("  进入后序遍历");
            // 3. 如果相等，则返回
            if (this.id == id) {
                return this;
            }
            return null;
        }
    }

    // 编写二叉树对象
    class BinaryTree {
        public HeroNode root;

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

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

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

        /**
         * 前序查找
         */
        public HeroNode preOrderSearch(int id) {
            if (root == null) {
                System.out.println("二叉树为空");
                return null;
            }
            return root.preOrderSearch(id);
        }

        /**
         * 中序查找
         */
        public HeroNode infixOrderSearch(int id) {
            if (root == null) {
                System.out.println("二叉树为空");
                return null;
            }
            return root.infixOrderSearch(id);
        }

        /**
         * 后序查找
         */
        public HeroNode postOrderSearch(int id) {
            if (root == null) {
                System.out.println("二叉树为空");
                return null;
            }
            return root.postOrderSearch(id);
        }
    }

    


    /**
     * 查找 id=5 的前、中、后序测试
     */
    @Test
    public void fun3() {
        // 创建节点与构建二叉树
        HeroNode n1 = new HeroNode(1, "宋江");
        HeroNode n2 = new HeroNode(2, "无用");
        HeroNode n3 = new HeroNode(3, "卢俊");
        HeroNode n4 = new HeroNode(4, "林冲");
        HeroNode n5 = new HeroNode(5, "关胜");
        n1.left = n2;
        n1.right = n3;
        n3.right = n4;
        n3.left = n5;
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.root = n1;

        System.out.println("找到测试：");
        int id = 5;
        System.out.println("\n前序遍历查找 id=" + id);
        System.out.println(binaryTree.preOrderSearch(id));
        System.out.println("\n中序遍历查找 id=" + id);
        System.out.println(binaryTree.infixOrderSearch(id));
        System.out.println("\n后序遍历查找 id=" + id);
        System.out.println(binaryTree.postOrderSearch(id));

        System.out.println("找不到测试：");
        id = 15;
        System.out.println("\n前序遍历查找 id=" + id);
        System.out.println(binaryTree.preOrderSearch(id));
        System.out.println("\n中序遍历查找 id=" + id);
        System.out.println(binaryTree.infixOrderSearch(id));
        System.out.println("\n后序遍历查找 id=" + id);
        System.out.println(binaryTree.postOrderSearch(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

测试输出

找到测试：

前序遍历查找 id=5   # 共查找 4 次
  进入前序遍历
  进入前序遍历
  进入前序遍历
  进入前序遍历
HeroNode{id=5, name='关胜'}

中序遍历查找 id=5  # 共查找 3 次
  进入中序遍历
  进入中序遍历
  进入中序遍历
HeroNode{id=5, name='关胜'}

后序遍历查找 id=5  # 共查找 2 次
  进入后序遍历
  进入后序遍历
HeroNode{id=5, name='关胜'}
找不到测试：

前序遍历查找 id=15
  进入前序遍历
  进入前序遍历
  进入前序遍历
  进入前序遍历
  进入前序遍历
null

中序遍历查找 id=15
  进入中序遍历
  进入中序遍历
  进入中序遍历
  进入中序遍历
  进入中序遍历
null

后序遍历查找 id=15
  进入后序遍历
  进入后序遍历
  进入后序遍历
  进入后序遍历
  进入后序遍历
null
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

可以看出：

  • 找到的次数和 查找的顺序 有关，而查找顺序就是哪一序有关
  • 找不到的次数则是相当于都遍历完成，所以是相等的次数

# 二叉树的删除

image-20201116163114510

要求：

  1. 如果删除的节点是 叶子节点，则删除该节点
  2. 如果删除的节点是非叶子节点，则删除该子树

测试：删除 5 号叶子节点和 3 号子树。

说明：目前的二叉树不是规则的，如果不删除子树，则需要考虑哪一个节点会被上提作为父节点。这个后续讲解排序二叉树时再来实现。先实现简单的

思路分析：

  • 由于我们的二叉树是单向的

  • 所以我们判定一个节点是否可以删除，是判断它的 子节点，是否可删除，否则则没法回到父节点删除了，因为要判断被删除的节点满足前面的两点要求

    1. 当前节点的 左子节点 不为空，并且左子节点就是要删除的节点，则 left = null，并且返回（结束递归删除）
    2. 当前节点的 右子节点 不为空，并且右子节点就是要删除的节点，则 right = null，并且返回（结束递归删除）

    如果前面都没有删除，则继续递归删除。上面的要求是 2 点，实际上是，找到符合条件的节点则直接删除（因为不考虑是否有子树）

    如果树只有一个 root 节点，则将 root 节点置空

// BinaryTree 新增删除方法

 /**
 * 删除节点
 *
 * @param id
 * @return
 */
public HeroNode delete(int id) {
  if (root == null) {
    System.out.println("树为空");
    return null;
  }
  HeroNode target = null;
  // 如果 root 节点就是要删除的节点，则直接置空
  if (root.id == id) {
    target = root;
    root = null;
  } else {
    target = this.root.delete(id);
  }

  return target;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// HeroNode 中新增删除方法

/**
* 删除节点，老师的思路写法，先看左右，看完再递归
* @param id
* @return 如果删除成功，则返回删除的节点
*/
public HeroNode delete(int id) {
  // 判断左子节点是否是要删除的节点
  HeroNode target = null;
  if (this.left != null && this.left.id == id) {
    target = this.left;
    this.left = null;
    return target;
  }

  if (this.right != null && this.right.id == id) {
    target = this.right;
    this.right = null;
    return target;
  }

  // 尝试左递归
  if (this.left != null) {
    target = this.left.delete(id);
    if (target != null) {
      return target;
    }
  }

  // 尝试右递归
  if (this.right != null) {
    target = this.right.delete(id);
    if (target != null) {
      return target;
    }
  }
  return null;
}
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

删除方法测试用例

    /**
     * 构建当前这个树
     *
     * @return
     */
    private BinaryTree buildBinaryTree() {
        HeroNode n1 = new HeroNode(1, "宋江");
        HeroNode n2 = new HeroNode(2, "无用");
        HeroNode n3 = new HeroNode(3, "卢俊");
        HeroNode n4 = new HeroNode(4, "林冲");
        HeroNode n5 = new HeroNode(5, "关胜");
        n1.left = n2;
        n1.right = n3;
        n3.right = n4;
        n3.left = n5;
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.root = n1;
        return binaryTree;
    }

    /**
     * 不考虑子节点的删除
     */
    @Test
    public void delete() {
        System.out.println("\n删除 3 号节点");
        delete3();
        System.out.println("\n删除 5 号节点");
        delete5();
        System.out.println("\n删除一个不存在的节点");
        deleteFail();
        System.out.println("\n删除 root 节点");
        deleteRoot();
    }

    @Test
    public void delete3() {
        // 创建节点与构建二叉树
        BinaryTree binaryTree = buildBinaryTree();
        binaryTree.preOrder();

        // 删除 3 号节点
        HeroNode target = binaryTree.delete(3);
        String msg = (target == null ? "删除失败，未找到" : "删除成功：" + target.toString());
        System.out.println(msg);
        binaryTree.preOrder();
    }


    @Test
    public void delete5() {
        // 创建节点与构建二叉树
        BinaryTree binaryTree = buildBinaryTree();
        binaryTree.preOrder();

        // 删除 5 号节点
        HeroNode target = binaryTree.delete(5);
        String msg = (target == null ? "删除失败，未找到" : "删除成功：" + target.toString());
        System.out.println(msg);
        binaryTree.preOrder();
    }

    /**
     * 删除一个不存在的节点
     */
    @Test
    public void deleteFail() {
        // 创建节点与构建二叉树
        BinaryTree binaryTree = buildBinaryTree();
        binaryTree.preOrder();

        // 删除 5 号节点
        HeroNode target = binaryTree.delete(9);
        String msg = (target == null ? "删除失败，未找到" : "删除成功：" + target.toString());
        System.out.println(msg);
        binaryTree.preOrder();
    }

    /**
     * 删除 root 节点
     */
    @Test
    public void deleteRoot() {
        // 创建节点与构建二叉树
        BinaryTree binaryTree = buildBinaryTree();
        binaryTree.preOrder();

        // 删除 1 号节点
        HeroNode target = binaryTree.delete(1);
        String msg = (target == null ? "删除失败，未找到" : "删除成功：" + target.toString());
        System.out.println(msg);
        binaryTree.preOrder();
    }
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

分别输出信息如下

删除 3 号节点
HeroNode{id=1, name='宋江'}
HeroNode{id=2, name='无用'}
HeroNode{id=3, name='卢俊'}
HeroNode{id=5, name='关胜'}
HeroNode{id=4, name='林冲'}
删除成功：HeroNode{id=3, name='卢俊'}
HeroNode{id=1, name='宋江'}
HeroNode{id=2, name='无用'}

删除 5 号节点
HeroNode{id=1, name='宋江'}
HeroNode{id=2, name='无用'}
HeroNode{id=3, name='卢俊'}
HeroNode{id=5, name='关胜'}
HeroNode{id=4, name='林冲'}
删除成功：HeroNode{id=5, name='关胜'}
HeroNode{id=1, name='宋江'}
HeroNode{id=2, name='无用'}
HeroNode{id=3, name='卢俊'}
HeroNode{id=4, name='林冲'}

删除一个不存在的节点
HeroNode{id=1, name='宋江'}
HeroNode{id=2, name='无用'}
HeroNode{id=3, name='卢俊'}
HeroNode{id=5, name='关胜'}
HeroNode{id=4, name='林冲'}
删除失败，未找到
HeroNode{id=1, name='宋江'}
HeroNode{id=2, name='无用'}
HeroNode{id=3, name='卢俊'}
HeroNode{id=5, name='关胜'}
HeroNode{id=4, name='林冲'}

删除 root 节点
HeroNode{id=1, name='宋江'}
HeroNode{id=2, name='无用'}
HeroNode{id=3, name='卢俊'}
HeroNode{id=5, name='关胜'}
HeroNode{id=4, name='林冲'}
删除成功：HeroNode{id=1, name='宋江'}
二叉树为空
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

# 二叉树的删除-课后练习

上面讲解了二叉树的删除，但是没有考虑子树的情况。

image-20201129163427823

如上二叉树：

  • 删除 1，则所有都删除了
  • 删除 3，则删除的有 3、5、4

现在要求，考虑子树的情况，如：

  • 删除 1，则保留 2，但是 1， 3，5，4 会被删除掉
  • 删除 3，则保留 5，但是 3，4 会被删除掉

因为要考虑如何提升节点的问题，那么 就需要一个规则，现在制定规则如下：

  1. 如果该非叶子节点 A 只有一个 子节点 B，则子 节点 B 替代节点 A

  2. 如果该非叶子节点 A 有 左子节点 B 和 右子节点 C，则让 左子节点 B 替代节点 A

    注意这里：如果删除节点 3，那么节点 5 会保留下来，节点 4 会被删除掉

这里暂时实现这一一个规则。后续讲解 二叉排序树 时，再来考虑如何完整的提升节点

// cn.mrcode.study.dsalgtutorialdemo.datastructure.tree.BinaryTreeTest.HeroNode#deleteV2
  
/**
         * 删除节点，考虑子节点
         * 1. 如果该非叶子节点 A 只有一个 **子节点 B**，则子 **节点 B 替代节点 A**
         * 2. 如果该非叶子节点 A 有 **左子节点 B** 和 **右子节点 C**，则让 **左子节点 B 替代节点 A**
         *
         * @param id
         * @return
         */
        public HeroNode deleteV2(int id) {
            // 先判断左是否有要删除的节点
            HeroNode target = null;
            // 如果是要删除的节点
            if (this.left != null && this.left.id == id) {
                target = this.left;
                // 如果当前删除的节点就是叶子节点，则直接删除
                if (left.left == null && left.right == null) {
                    this.left = null;
                    return target;
                }
                // 如果有两个子节点,则让左子节点替代该节点
                if (left.left != null && left.right != null) {
                    left = left.left;
                    return target;
                }
                // 如果只有一个子节点，则子节点替代该节点
                if (left.left != null) {
                    left = left.left;
                    return target;
                }

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

            if (this.right != null && this.right.id == id) {
                target = this.right;
                // 如果当前删除的节点就是叶子节点，则直接删除
                if (right.left == null && right.right == null) {
                    this.right = null;
                    return target;
                }
                // 如果有两个子节点,则让左子节点替代该节点
                if (right.left != null && right.right != null) {
                    right = right.left;
                    return target;
                }
                // 如果只有一个子节点，则子节点替代该节点
                if (right.left != null) {
                    right = right.left;
                    return target;
                }

                if (right.right != null) {
                    right = right.right;
                    return target;
                }
                return target;
            }

            // 尝试左递归
            if (this.left != null) {
                target = this.left.delete(id);
                if (target != null) {
                    return target;
                }
            }

            // 尝试右递归
            if (this.right != null) {
                target = this.right.delete(id);
                if (target != null) {
                    return target;
                }
            }
            return null;
        }
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
// cn.mrcode.study.dsalgtutorialdemo.datastructure.tree.BinaryTreeTest.BinaryTree#deleteV2

        /**
         * 删除节点，考虑子节点
         * 1. 如果该非叶子节点 A 只有一个 **子节点 B**，则子 **节点 B 替代节点 A**
         * 2. 如果该非叶子节点 A 有 **左子节点 B** 和 **右子节点 C**，则让 **左子节点 B 替代节点 A**
         *
         * @param id
         * @return
         */
        public HeroNode deleteV2(int id) {
            if (root == null) {
                System.out.println("树为空");
            }
            HeroNode target = null;
            // 如果是 root 节点，则按照上述的规则进行提升节点
            if (root.id == id) {
                target = root;
                // 如果当前删除的节点就是叶子节点，则直接删除
                if (root.left == null && root.right == null) {
                    root = null;
                    return target;
                }
                // 如果有两个子节点,则让左子节点替代该节点
                if (root.left != null && root.right != null) {
                    root = root.left;
                    return target;
                }
                // 如果只有一个子节点，则子节点替代该节点
                if (root.left != null) {
                    root = root.left;
                    return target;
                }

                if (root.right != null) {
                    root = root.right;
                    return target;
                }
            } else {
                target = this.root.deleteV2(id);
            }
            return target;
        }
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

测试代码

 @Test
    public void deleteV2() {
        System.out.println("\n删除 3 号节点");
        delete3V2();
        System.out.println("\n删除 5 号节点");
        delete5V2();
        System.out.println("\n删除一个不存在的节点");
        deleteFailV2();
        System.out.println("\n删除 root 节点");
        deleteRootV2();
    }

    @Test
    public void delete3V2() {
        // 创建节点与构建二叉树
        BinaryTree binaryTree = buildBinaryTree();
        binaryTree.preOrder();

        // 删除 3 号节点
        HeroNode target = binaryTree.deleteV2(3);
        String msg = (target == null ? "删除失败，未找到" : "删除成功：" + target.toString());
        System.out.println(msg);
        binaryTree.preOrder();
    }


    @Test
    public void delete5V2() {
        // 创建节点与构建二叉树
        BinaryTree binaryTree = buildBinaryTree();
        binaryTree.preOrder();

        // 删除 5 号节点
        HeroNode target = binaryTree.deleteV2(5);
        String msg = (target == null ? "删除失败，未找到" : "删除成功：" + target.toString());
        System.out.println(msg);
        binaryTree.preOrder();
    }

    /**
     * 删除一个不存在的节点
     */
    @Test
    public void deleteFailV2() {
        // 创建节点与构建二叉树
        BinaryTree binaryTree = buildBinaryTree();
        binaryTree.preOrder();

        // 删除 5 号节点
        HeroNode target = binaryTree.deleteV2(9);
        String msg = (target == null ? "删除失败，未找到" : "删除成功：" + target.toString());
        System.out.println(msg);
        binaryTree.preOrder();
    }

    /**
     * 删除 root 节点
     */
    @Test
    public void deleteRootV2() {
        // 创建节点与构建二叉树
        BinaryTree binaryTree = buildBinaryTree();
        binaryTree.preOrder();

        // 删除 1 号节点
        HeroNode target = binaryTree.deleteV2(1);
        String msg = (target == null ? "删除失败，未找到" : "删除成功：" + target.toString());
        System.out.println(msg);
        binaryTree.preOrder();
    }
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

测试输出

删除 3 号节点
HeroNode{id=1, name='宋江'}
HeroNode{id=2, name='无用'}
HeroNode{id=3, name='卢俊'}
HeroNode{id=5, name='关胜'}
HeroNode{id=4, name='林冲'}
删除成功：HeroNode{id=3, name='卢俊'}
HeroNode{id=1, name='宋江'}
HeroNode{id=2, name='无用'}
HeroNode{id=5, name='关胜'}

删除 5 号节点
HeroNode{id=1, name='宋江'}
HeroNode{id=2, name='无用'}
HeroNode{id=3, name='卢俊'}
HeroNode{id=5, name='关胜'}
HeroNode{id=4, name='林冲'}
删除成功：HeroNode{id=5, name='关胜'}
HeroNode{id=1, name='宋江'}
HeroNode{id=2, name='无用'}
HeroNode{id=3, name='卢俊'}
HeroNode{id=4, name='林冲'}

删除一个不存在的节点
HeroNode{id=1, name='宋江'}
HeroNode{id=2, name='无用'}
HeroNode{id=3, name='卢俊'}
HeroNode{id=5, name='关胜'}
HeroNode{id=4, name='林冲'}
删除失败，未找到
HeroNode{id=1, name='宋江'}
HeroNode{id=2, name='无用'}
HeroNode{id=3, name='卢俊'}
HeroNode{id=5, name='关胜'}
HeroNode{id=4, name='林冲'}

删除 root 节点
HeroNode{id=1, name='宋江'}
HeroNode{id=2, name='无用'}
HeroNode{id=3, name='卢俊'}
HeroNode{id=5, name='关胜'}
HeroNode{id=4, name='林冲'}
删除成功：HeroNode{id=1, name='宋江'}
HeroNode{id=2, name='无用'}
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

← 顺序存储二叉树 →