二叉排序树(BST)介绍

二叉排序树例子

需求

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

解决方案分析

  1. 使用数组
    • 数组未排序，优点：直接再数组末尾添加，速度快；缺点：查找速度慢。
    • 数组排序，优点：可以使用二分查找，查找速度快；缺点：为了保证数组有序，在添加新数据时，找到插入位置后，数据需要整体移动，速度慢。
  2. 使用链式存储(链表)
    • 不管链表是否有序，查找速度都慢，添加数据不需要整体移动，添加速度比数组快。
  3. 使用二叉排序树

二叉排序树介绍

二叉排序树：BST(Binary Sort(Search) Tree)，对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。

特别说明：如果有相同值，可以将该节点放在左子节点或右子节点。

例如上方例子中的数组的二叉排序树应该为：

image-20221112103704001

二叉排序树创建和遍历

创建数列{7,3,10,12,5,1,9}对应的二叉排序树并使用中序遍历；

代码

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
package com.jokerdig.binarySortTree;

/**
 * @author Joker大雄
 * @data 2022/11/12 - 10:42
 **/
public class BinarySortTreeDemo {
    public static void main(String[] args) {
        int [] arr = {7,3,10,12,5,1,9};
        BinarySortTree binarySortTree = new BinarySortTree();
        for(int value:arr){
            // 创建二叉树
            binarySortTree.add(new Node(value));
        }
        // 遍历
        binarySortTree.infixOrder();
    }
}
// 创建二叉排序树
class BinarySortTree{
    private Node root;
    // 添加节点方法
    public void add(Node node){
        if(root==null){
            root = node; // 根节点
        }else{
            root.add(node); // 添加节点
        }
    }
    // 中序遍历
    public void infixOrder(){
        if(root!=null){
            root.infixOrder();
        }else{
            System.out.println("没有数据");
        }
    }
}
// 创建节点
class Node{
    int value;
    Node left;
    Node right;

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

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

    // 二叉排序树添加节点
    public void add(Node node){
        if(node==null) {
            return;
        }
        // 判断传入节点的值和当前子树的根节点值的关系
        if(node.value<this.value){
            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
Node{value=1}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}

Process finished with exit code 0

二叉排序树删除节点思路图解

思路分析

二叉排序树的删除情况比较复杂，有以下三种情况考虑：

  1. 删除叶子节点(例如：2,5,9,12)

  2. 删除只有一棵子树的节点(例如：1)

  3. 删除有两棵子树的节点(例如：7,3,10)

    示意图：

    image-20221114164137558

步骤分析

  • 删除叶子节点

    1. 需要先去定位要删除的节点targetNode；

    2. 找到targetNode的父节点parent；

    3. 判断targetNode是parent的左子节点还是右子节点；

    4. 根据上方的情况来对应删除；

      左子节点：parent.left = null;

      右子节点：parent.right = null;

  • 删除只有一棵子树的节点

    1. 需要先去定位要删除的节点targetNode；
    2. 找到targetNode的父节点parent；
    3. 确定targetNode的子节点是左子节点还是右子节点；
    4. targetNode是parent的左子节点还是右子节点；
    5. 如果targetNode有左子节点：
      • 如果targetNode是parent的左子节点：parent.left = targetNode.left;
      • 如果targetNode是parent的右子节点：parent.right = targetNode.left;
    6. 如果targetNode有右子节点：
      • 如果targetNode是parent的左子节点：parent.left = targetNode.right;
      • 如果targetNode是parent的右子节点：parent.right = targetNode.right;

  • 删除有两棵子树的节点

    1. 需要先去定位要删除的节点targetNode；
    2. 找到targetNode的父节点parent；
    3. 从targetNode的右子树找到最小的节点(或左子树找到最大节点)；
    4. 用一个临时变量temp，将最小节点值保存；
    5. 删除该最小节点；
    6. targetNode.value = temp;

二叉排序树删除叶子节点

代码

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
package com.jokerdig.binarySortTree;

/**
 * @author Joker大雄
 * @data 2022/11/12 - 10:42
 **/
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 value:arr){
            // 创建二叉树
            binarySortTree.add(new Node(value));
        }
        // 遍历
        binarySortTree.infixOrder();

        // 测试删除叶子节点
        binarySortTree.delNode(2);
        System.out.println("删除叶子节点2后的二叉排序树");
        binarySortTree.infixOrder();
    }
}
// 创建二叉排序树
class BinarySortTree{
    private Node root;
    // 添加节点方法
    public void add(Node node){
        if(root==null){
            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);
        }
    }

    // 删除节点
    public void delNode(int value){
        if(root==null){
            return;
        }else{
            // 先去找到要删除的节点 targetNode
            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){
                // 判断targetNode是父节点的左子节点，还是右子节点
                if(parent.left != null && parent.left.value ==value){ // 是父节点的左子节点
                    parent.left = null; // 删除
                }else if(parent.right !=null && parent.right.value == value){// 是父节点的右子节点
                    parent.right = null; // 删除
                }
            }
        }
    }
}
// 创建节点
class Node{
    int value;
    Node left;
    Node right;

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

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
    // 查找要删除的节点
    /**
     *
     * @param value 要删除的节点的值
     * @return  如果找到，返回该节点，否则返回null
     */
    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; // 没有找到父节点
            }
        }
    }
    // 二叉排序树添加节点
    public void add(Node node){
        if(node==null) {
            return;
        }
        // 判断传入节点的值和当前子树的根节点值的关系
        if(node.value<this.value){
            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
Node{value=1}
Node{value=2}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}
删除叶子节点2后的二叉排序树
Node{value=1}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}

Process finished with exit code 0

二叉排序树删除有一棵子树的节点

代码

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
package com.jokerdig.binarySortTree;

/**
 * @author Joker大雄
 * @data 2022/11/12 - 10:42
 **/
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 value:arr){
            // 创建二叉树
            binarySortTree.add(new Node(value));
        }
        // 遍历
        binarySortTree.infixOrder();

        // 测试删除叶子节点
        // binarySortTree.delNode(2);
        // System.out.println("删除叶子节点2后的二叉排序树");
        // binarySortTree.infixOrder();

        // 删除有一棵子树的节点
         binarySortTree.delNode(1);
         System.out.println("删除有一棵子树的节点的二叉排序树");
         binarySortTree.infixOrder();
    }
}
// 创建二叉排序树
class BinarySortTree{
    private Node root;
    // 添加节点方法
    public void add(Node node){
        if(root==null){
            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);
        }
    }
    // 删除节点
    public void delNode(int value){
        if(root==null){
            return;
        }else{
            // 先去找到要删除的节点 targetNode
            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){
                // 判断targetNode是父节点的左子节点，还是右子节点
                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){ // 有左右子树


            }else{ // 删除只有一棵子树的节点
                // 如果要删除的节点有左子节点
                if(targetNode.left!=null){
                    // 如果targetNode是parent的左子节点
                    if(parent.left.value == value){
                        parent.left = targetNode.left;
                    }else{// 如果targetNode是parent的右子节点
                        parent.right = targetNode.left;
                    }
                } else{// 如果要删除的节点有右子节点
                    // 如果targetNode是parent的左子节点
                    if(parent.left.value == value){
                        parent.left = targetNode.right;
                    }else{// 如果targetNode是parent的右子节点
                        parent.right = targetNode.right;
                    }
                }
            }
        }
    }
}
// 创建节点
class Node{
    int value;
    Node left;
    Node right;

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

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
    // 查找要删除的节点
    /**
     *
     * @param value 要删除的节点的值
     * @return  如果找到，返回该节点，否则返回null
     */
    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; // 没有找到父节点
            }
        }
    }
    // 二叉排序树添加节点
    public void add(Node node){
        if(node==null) {
            return;
        }
        // 判断传入节点的值和当前子树的根节点值的关系
        if(node.value<this.value){
            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
Node{value=1}
Node{value=2}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}
删除有一棵子树的节点的二叉排序树
Node{value=2}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}

Process finished with exit code 0

二叉排序树删除有两棵子树的节点

代码

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
package com.jokerdig.binarySortTree;

/**
 * @author Joker大雄
 * @data 2022/11/12 - 10:42
 **/
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 value:arr){
            // 创建二叉树
            binarySortTree.add(new Node(value));
        }
        // 遍历
        binarySortTree.infixOrder();

        // 测试删除叶子节点
        // binarySortTree.delNode(2);
        // System.out.println("删除叶子节点2后的二叉排序树");
        // binarySortTree.infixOrder();

        // 删除有一棵子树的节点
        // binarySortTree.delNode(1);
        // System.out.println("删除有一棵子树的节点的二叉排序树");
        // binarySortTree.infixOrder();

        // 删除有两棵子树的节点
        binarySortTree.delNode(3);
        System.out.println("删除有两棵子树的节点的二叉排序树");
        binarySortTree.infixOrder();
    }
}
// 创建二叉排序树
class BinarySortTree{
    private Node root;
    // 添加节点方法
    public void add(Node node){
        if(root==null){
            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);
        }
    }
    // 删除节点
    public void delNode(int value){
        if(root==null){
            return;
        }else{
            // 先去找到要删除的节点 targetNode
            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){
                // 判断targetNode是父节点的左子节点，还是右子节点
                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 min = delRightTreeMin(targetNode.right);// 从右子树开始找最小值(或者左子树开始找最大值)
                targetNode.value = min;
            }else{ // 删除只有一棵子树的节点
                // 如果要删除的节点有左子节点
                if(targetNode.left!=null){
                    // 如果targetNode是parent的左子节点
                    if(parent.left.value == value){
                        parent.left = targetNode.left;
                    }else{// 如果targetNode是parent的右子节点
                        parent.right = targetNode.left;
                    }
                } else{// 如果要删除的节点有右子节点
                    // 如果targetNode是parent的左子节点
                    if(parent.left.value == value){
                        parent.left = targetNode.right;
                    }else{// 如果targetNode是parent的右子节点
                        parent.right = targetNode.right;
                    }
                }
            }
        }
    }
    // 返回以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;
    }
}
// 创建节点
class Node{
    int value;
    Node left;
    Node right;

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

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
    // 查找要删除的节点
    /**
     *
     * @param value 要删除的节点的值
     * @return  如果找到，返回该节点，否则返回null
     */
    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; // 没有找到父节点
            }
        }
    }
    // 二叉排序树添加节点
    public void add(Node node){
        if(node==null) {
            return;
        }
        // 判断传入节点的值和当前子树的根节点值的关系
        if(node.value<this.value){
            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
Node{value=1}
Node{value=2}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}
删除有两棵子树的节点的二叉排序树
Node{value=1}
Node{value=2}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}

Process finished with exit code 0

二叉排序树删除节点注意事项

问题

在删除节点的时候，如果我们删除带有一棵子树的根节点，就会出现空指针异常，因为这时根节点的父节点为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
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
package com.jokerdig.binarySortTree;

/**
 * @author Joker大雄
 * @data 2022/11/12 - 10:42
 **/
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 value:arr){
            // 创建二叉树
            binarySortTree.add(new Node(value));
        }
        // 遍历
        binarySortTree.infixOrder();

        // 测试删除叶子节点
        // binarySortTree.delNode(2);
        // System.out.println("删除叶子节点2后的二叉排序树");
        // binarySortTree.infixOrder();

        // 删除有一棵子树的节点
        // binarySortTree.delNode(1);
        // System.out.println("删除有一棵子树的节点的二叉排序树");
        // binarySortTree.infixOrder();

        // 删除有两棵子树的节点
        // binarySortTree.delNode(3);
        // System.out.println("删除有两棵子树的节点的二叉排序树");
        // binarySortTree.infixOrder();

        // 测试删除根节点是否空指针
         binarySortTree.delNode(7);
         System.out.println("删除根节点后的二叉排序树");
         binarySortTree.infixOrder();
    }
}
// 创建二叉排序树
class BinarySortTree{
    private Node root;
    // 添加节点方法
    public void add(Node node){
        if(root==null){
            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);
        }
    }
    // 删除节点
    public void delNode(int value){
        if(root==null){
            return;
        }else{
            // 先去找到要删除的节点 targetNode
            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){
                // 判断targetNode是父节点的左子节点，还是右子节点
                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 min = delRightTreeMin(targetNode.right);// 从右子树开始找最小值(或者左子树开始找最大值)
                targetNode.value = min;
            }else{ // 删除只有一棵子树的节点
                // 如果要删除的节点有左子节点
                if(targetNode.left!=null){
                   if(parent!=null){ // 防止删除根节点空指针
                       // 如果targetNode是parent的左子节点
                       if(parent.left.value == value){
                           parent.left = targetNode.left;
                       }else{// 如果targetNode是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; // 让根节点指向待删除节点的右子树
                    }

                }
            }
        }
    }
    // 返回以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;
    }
}
// 创建节点
class Node{
    int value;
    Node left;
    Node right;

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

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
    // 查找要删除的节点
    /**
     *
     * @param value 要删除的节点的值
     * @return  如果找到，返回该节点，否则返回null
     */
    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; // 没有找到父节点
            }
        }
    }
    // 二叉排序树添加节点
    public void add(Node node){
        if(node==null) {
            return;
        }
        // 判断传入节点的值和当前子树的根节点值的关系
        if(node.value<this.value){
            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
Node{value=1}
Node{value=2}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}
删除根节点后的二叉排序树
Node{value=1}
Node{value=2}
Node{value=3}
Node{value=5}
Node{value=9}
Node{value=10}
Node{value=12}

Process finished with exit code 0