数据结构：二叉排序树

1. 需求

• 一个数列 (7, 3, 10, 12, 5, 1, 9)，要求能够高效的完成对数据的查询和添加。

2. 解决方案

2.1 使用数组

1. 数组未排序， 优点：直接在数组尾添加，速度快。 缺点：查找速度慢
2. 数组排序，优点：可以使用二分查找，查找速度快，缺点：为了保证数组有序，在添加新数据时，找到插入位置后，后面的数据需整体移动，速度慢

2.2 使用链式存储-链表

• 不管链表是否有序，查找速度都慢，添加数据速度比数组快，不需要数据整体移动

2.3 使用二叉排序树

3. 二叉排序树介绍

• BST: (Binary Sort Tree), 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。
  特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点

• 比如针对前面的数据 (7, 3, 10, 12, 5, 1, 9) ，对应的二叉排序树为：

4. 二叉排序树创建和遍历

• 一个数组创建成对应的二叉排序树，并使用中序遍历二叉排序树，比如: 数组为 Array(7, 3, 10, 12, 5, 1, 9) ， 创建成对应的二叉排序树为 :

    static class Node {
        int value;

        Node left;

        Node right;

        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{" + "value=" + value + '}';
        }

        /**
         * 递归添加节点，注意满足二叉排序树的要求
         *
         * @param node
         */
        public void add(Node node) {
            if (node == null) {
                return;
            }
            // 判断传入节点的值，和当前子树的根节点值的关系
            if (node.value < this.value) {
                // 如果当前节点左子节点为null
                if (this.left == null) {
                    this.left = node;
                } else {
                    // 递归向左子树添加
                    this.left.add(node);
                }
            } else { // 添加节点的值大于当前节点的值
                if (this.right == null) {
                    this.right = node;
                } else {
                    // 递归向右子树添加
                    this.right.add(node);
                }
            }
        }

        /**
         * 中序遍历
         */
        public void infixOrder() {
            if (this.left != null) {
                this.left.infixOrder();
            }
            System.out.println(this);
            if (this.right != null) {
                this.right.infixOrder();
            }
        }
      
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

5. 二叉排序树的删除

• 二叉排序树的删除情况比较复杂，有下面三种情况需要考虑

1. 删除叶子节点 (比如：2, 5, 9, 12)
2. 删除只有一颗子树的节点 (比如：1)
3. 删除有两颗子树的节点. (比如：7, 3, 10 )

情况一:删除叶子节点 (比如：2, 5, 9, 12)
思路
(1) 需求先去找到要删除的结点 targetNode
(2) 找到targetNode 的父结点 parent
(3) 确定 targetNode 是 parent的左子结点 还是右子结点
(4) 根据前面的情况来对应删除
左子结点 parent.left = null
右子结点 parent.right = null;
第二种情况: 删除只有一颗子树的节点 比如 1
思路
(1) 需求先去找到要删除的结点 targetNode
(2) 找到targetNode 的父结点 parent
(3) 确定targetNode 的子结点是左子结点还是右子结点
(4) targetNode 是 parent 的左子结点还是右子结点
(5) 如果targetNode 有左子结点
5.1 如果 targetNode 是 parent 的左子结点
parent.left = targetNode.left;
5.2 如果 targetNode 是 parent 的右子结点
parent.right = targetNode.left;
(6) 如果targetNode 有右子结点
6.1 如果 targetNode 是 parent 的左子结点
parent.left = targetNode.right;
6.2 如果 targetNode 是 parent 的右子结点
parent.right = targetNode.right
情况三 ： 删除有两颗子树的节点. (比如：7, 3，10 )
思路
(1) 需求先去找到要删除的结点 targetNode
(2) 找到targetNode 的 父结点 parent
(3) 从targetNode 的右子树找到最小的结点
(4) 用一个临时变量，将 最小结点的值保存 temp = 9
(5) 删除该最小结点
(6) targetNode.value = temp

• 情况三的结果如下

• 完整代码

package com.datastructure.二叉树;

public class BinarySortTreeDemo {

    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
        BinarySortTree binarySortTree = new BinarySortTree();
        // 循环添加节点到二叉排序树
        for (int i = 0; i < arr.length; i++) {
            binarySortTree.add(new Node(arr[i]));
        }
        // 中序遍历
        System.out.println("中序遍历二叉排序树");
        System.out.println("root=" + binarySortTree.getRoot());
        binarySortTree.infixOrder();
        // 删除节点
        binarySortTree.delNode(12);
        binarySortTree.delNode(1);
        binarySortTree.delNode(7);
        System.out.println("root=" + binarySortTree.getRoot());
        System.out.println("删除节点后");
        binarySortTree.infixOrder();

    }

    static class Node {
        int value;

        Node left;

        Node right;

        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{" + "value=" + value + '}';
        }

        /**
         * 递归添加节点，注意满足二叉排序树的要求
         *
         * @param node
         */
        public void add(Node node) {
            if (node == null) {
                return;
            }
            // 判断传入节点的值，和当前子树的根节点值的关系
            if (node.value < this.value) {
                // 如果当前节点左子节点为null
                if (this.left == null) {
                    this.left = node;
                } else {
                    // 递归向左子树添加
                    this.left.add(node);
                }
            } else { // 添加节点的值大于当前节点的值
                if (this.right == null) {
                    this.right = node;
                } else {
                    // 递归向右子树添加
                    this.right.add(node);
                }
            }
        }

        /**
         * 中序遍历
         */
        public void infixOrder() {
            if (this.left != null) {
                this.left.infixOrder();
            }
            System.out.println(this);
            if (this.right != null) {
                this.right.infixOrder();
            }
        }

        /**
         * 查找要删除的节点
         *
         * @param value
         * @return
         */
        public Node search(int value) {
            // 找到就是该节点
            if (value == this.value) {
                return this;
            } else if (value < this.value) {
                // 如果要查找的值小于当前节点，向左子树递归查找
                if (this.left == null) {
                    return null;
                }
                return this.left.search(value);
            } else {
                // 如果带查找的值不小于当前节点，向右子树递归查找
                if (this.right == null) {
                    return null;
                }
                return this.right.search(value);
            }
        }

        /**
         * 查找带删除节点的父节点
         *
         * @param value 带查找的值
         * @return 要删除节点的父节点，如果没有就返回null
         */
        public Node searchParent(int value) {
            // 如果当前节点就是要删除的节点的父节点
            if ((this.left != null && this.left.value == value) ||
                    (this.right != null && this.right.value == value)) {
                return this;
            } else {
                // 如果查找的值小于当前节点的值，并且当前节点左子节点不为空
                if (value < this.value && this.left != null) {
                    // 向左子树递归查找
                    return this.left.searchParent(value);
                } else if (value > this.value && this.right != null) {
                    // 向右子树递归查找
                    return this.right.searchParent(value);
                } else {
                    // 没有找到父节点
                    return null;
                }
            }
        }
    }

    static class BinarySortTree {

        private Node root;

        public Node getRoot() {
            return root;
        }

        // 添加节点的方法
        public void add(Node node) {
            if (root == null) {
                // 如果root为空，则直接让root指向node
                root = node;
            } else {
                root.add(node);
            }
        }

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

        // 查找要删除的节点
        public Node search(int value) {
            if (root == null) {
                return null;
            } else {
                return root.search(value);
            }
        }

        // 查找父节点
        public Node searchParent(int value) {
            if (root == null) {
                return null;
            } else {
                return root.searchParent(value);
            }
        }

        /**
         * 删除node为根节点的二叉排序树的最小节点
         *
         * @param node 传入的节点，作为二叉排序树的根节点
         * @return 返回以node为根节点的二叉排序树的最小节点的值
         */
        public int delRightTreeMin(Node node) {
            Node target = node;
            // 循环的查找左子节点，就会找到最小值
            while (target.left != null) {
                target = target.left;
            }
            // 这时target就指向了最小节点
            // 删除最小节点
            delNode(target.value);
            // 返回最小节点
            return target.value;
        }

        public void delNode(int value) {
            if (root == null) {
                return;
            } else {
                // 1.需要先找到待删除的节点
                Node targetNode = search(value);
                // 如果没有找到待删除的节点
                if (targetNode == null) {
                    return;
                }
                // 如果当前这个二叉排序树只有一个节点
                if (root.left == null && root.right == null) {
                    root = null;
                    return;
                }
                // 找到targetNode的父节点
                Node parent = searchParent(value);
                // 如果待删除节点是叶子节点
                if (targetNode.left == null && targetNode.right == null) {
                    // 判断target是父节点的左子节点，还是右子节点
                    if (parent.left != null && parent.left.value == value) {
                        // 左子节点
                        parent.left = null;
                    } else if (parent.right != null && parent.right.value == value) {
                        // 右子节点
                        parent.right = null;
                    }
                } else if (targetNode.left != null && targetNode.right != null) {
                    // 删除有两颗子树的节点
                    int minVal = delRightTreeMin(targetNode.right);
                    targetNode.value = minVal;
                } else {
                    // 删除只有一颗子树的节点
                    // 如果待删除的节点有左子节点
                    if (targetNode.left != null) {
                        if (parent != null) {
                            // 如果targetNode是parent的左子节点
                            if (parent.left.value == value) {
                                parent.left = targetNode.left;
                            } else {
                                // target是parent的右子节点
                                parent.right = targetNode.left;
                            }
                        } else {
                            // 如果待删除节点没有父节点，说明待删除节点是根节点
                            // 则让待删除节点的子节点作为根节点
                            root = targetNode.left;
                        }
                    } else {
                        // 如果要删除的节点有右子节点
                        if (parent != null) {
                            // 如果targetNode是parent的左子节点
                            if (parent.left.value == value) {
                                parent.left = targetNode.right;
                            } else {
                                // 如果targetNode是parent的右子节点
                                parent.right = targetNode.right;
                            }
                        } else {
                            root = targetNode.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