树 - 二叉搜索树 BST

10 Algorithm 评论

1. BST的定义

在二叉查找树中：

  • 若任意结点的左子树不空，则左子树上所有的结点的值均小于根结点的值；

  • 若任意结点的右子树不空，则右子树上所有的结点的值均小于根结点的值；

  • 任意结点的左、右子树也分别为二叉查找树

  • 没有键值相等的结点

动画效果请参考【BST】

2. BST的实现

2.1 结点

BSTree是二叉树，它保存了二叉树的根节点mRoot;mRoot是BSTNode类型，而BSTNode是二叉查找树的节点，它是BSTree的内部类。BSTNode包含二叉查找树的几个基本信息：

  • key：关键字，用来对二叉查找树的节点进行排序

  • left：指向当前节点的左子树

  • right：指向当前节点的右子树

  • parent：指向当前节点的父节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @author xiaoyuge
 */
public class BSTree<T extends Comparable<T>>{

    private BSTNode<T> mRoot; //根节点

    //内部类 --节点
    class BSTNode<T extends Comparable<T>>{

        T key;  //关键字
        BSTNode<T> left;    //左子树
        BSTNode<T> right;    //右子树
        BSTNode<T> parent;    //父节点

        public BSTNode(T key, BSTNode<T> left, BSTNode<T> right, BSTNode<T> parent) {
            this.key = key;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }
    }
}

2.2 遍历

2.2.1 前序遍历

若二叉树非空，则执行以下操作：

  • 访问根节点

  • 先序遍历左子树

  • 先序遍历右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 先序遍历
 * @param tree 树
 */
private void preOrder(BSTNode<T> tree){
    if (tree !=null){
        System.out.print(tree.key+" ");
        preOrder(tree.left);
        preOrder(tree.right);
    }
}
public void preOrder(){
    preOrder(mRoot);
}

2.2.2 中序遍历

若二叉树非空，则执行以下操作：

  • 中序遍历左子树

  • 访问根节点

  • 中序遍历右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 中序遍历
 * @param tree 树
 */
private void inOrder(BSTNode<T> tree){
    if (tree != null){
        inOrder(tree.left);
        System.out.print(tree.key);
        inOrder(tree.right);
    }
}
public void inOrder(){
    inOrder(mRoot);
}

2.2.3 后序遍历

若二叉树非空，则执行以下操作：

  • 后序遍历左子树

  • 后序遍历右子树

  • 访问根节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 后序遍历
 * @param tree 树
 */
private void postOrder(BSTNode<T> tree){
    if (tree != null){
        postOrder(tree.left);
        postOrder(tree.right);
        System.out.print(tree.key);
    }
}
public void postOrder(){
    postOrder(mRoot);
}

2.2.4 测试

对于上面的二叉树而言：

  • 前序遍历：8，3，1，6，3，7，10，14，13

  • 中序遍历：1，3，6，4，7，8，10，13，14

  • 后序遍历：1，4，7，6，3，13，14，10，8

2.3 查找

  • 递归版本代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    /**
     * 递归实现查找"二叉树 X"中键值为 key 的节点
     */
    private BSTNode<T> search(BSTNode<T> x, T key){
        if (x == null){
            return x;
        }
        int cmp = key.compareTo(x.key);
        if (cmp < 0){
            //key在左子树上
            return search(x.left, key);
        }else if(cmp > 0){
            //key 在右子树上
            return search(x.right, key);
        }else{
            return x;
        }
    }

    public BSTNode<T> search(T key){
        return search(mRoot, key);
    }

  • 非递归版本的代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    /**
     * 非递归实现查找"二叉树 X"中键值为 key 的节点
     */
    private BSTNode<T> iterativeSearch(BSTNode<T> x, T key){
        while (!(null == x)){
            int cmp = key.compareTo(x.key);
            if (cmp < 0){
                x = x.left;
            }else if(cmp > 0){
                x = x.right;
            }else{
                return x;
            }
        }
        return x;
    }
    public BSTNode<T> iterativeSearch(T key){
        return iterativeSearch(mRoot, key);
    }

2.4 最大值和最小值

  • 查找最大值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
     /**
     * 查找最大结点：返回tree为根节点的二叉树的最大结点
     * 最大结点永远在右子树上
     */
    private BSTNode<T> maximum(BSTNode<T> tree){
        if (tree == null){
            return null;
        }       
        while (tree.right != null){
            tree = tree.right;
        }
        return tree;
    }

    public T maximum(){
        BSTNode<T> p = maximum(mRoot);
        if (p != null){
            return p.key;
        }
        return null;
    }

  • 查找最小值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    /**
     * 查找最小结点：返回tree为根节点的二叉树的最小结点
     * 最小结点永远在左子树上
     */
    private BSTNode<T> minimum(BSTNode<T> tree) {
        if (tree == null) {
            return null;
        }
        while (tree.left != null){
            tree = tree.left;
        }
        return tree;
    }
    public T minimum(){
        BSTNode<T> p = minimum(mRoot);
        if (p != null){
            return p.key;
        }
        return null;
    }

2.5 前驱后继

  • 结点的前驱：是该结点左子树中最大结点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    /**
     * 找结点(x)的前驱结点。即，查找"二叉树中数据值小于该结点"的"最大结点"。
     */
    public BSTNode<T> predecessor(BSTNode<T> x) {
        //如果x存在左子树，则"x的前驱结点"为：以其左子树根的子树的最大结点
        if (x.left != null) {
            return maximum(x.left);
        }
        // 如果x没有左孩子。则x有以下两种可能:
        //1. x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
        //2. x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
        BSTNode<T> y = x.parent;
        while ((y != null) && (x == y.left)) {
            x = y;
            y = y.parent;
        }
        return y;
    }

  • 结点的后继：是该结点的右子树上最小的结点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    /**
     * 找结点(x)的后继结点。即，查找"二叉树中数据值大于该结点"的"最小结点"。
     */
    public BSTNode<T> successor(BSTNode<T> x) {
        // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
        if (x.right != null) {
            return minimum(x.right);
        }
        // 如果x没有右孩子。则x有以下两种可能:
        // 1. x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
        // 2. x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
        BSTNode<T> y = x.parent;
        while ((y != null) && (x == y.right)) {
            x = y;
            y = y.parent;
        }
        return y;
    }

2.6 插入

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
/**
 * 将结点插入到二叉树中
 *
 * @param bst 二叉树
 * @param z   插入的结点
 */
private void insert(BSTree<T> bst, BSTNode<T> z) {
    int cmp;
    BSTNode<T> y = null;
    BSTNode<T> x = bst.mRoot;

    //查找z的插入位置
    while (x != null) {
        y = x;
        cmp = z.key.compareTo(x.key);
        if (cmp < 0) {
            x = x.left;
        } else {
            x = x.right;
        }
    }

    z.parent = y;
    if (y == null) {
        bst.mRoot = z;
    } else {
        cmp = z.key.compareTo(y.key);
        if (cmp < 0) {
            y.left = z;
        } else {
            y.right = z;
        }
    }
}

/**
 * 新建结点(key)，并将其插入到二叉树中
 * @param key  插入结点的键值
 */
public void insert(T key) {
    BSTNode<T> z = new BSTNode<T>(key, null, null, null);
    insert(this, z);
}

2.7 删除

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
/**
 * 删除结点，并返回被删除的结点
 *
 * @param bst 二叉树
 * @param z   删除的结点
 */
private BSTNode<T> remove(BSTree<T> bst, BSTNode<T> z) {
    BSTNode<T> x = null;
    BSTNode<T> y = null;
    if ((z.left == null) || (z.right == null)) {
        //情况二：如果被删除结点只有左子树或右子树，孩子顶替
        y = z;
    } else {
        //二叉树中数据值大于该结点"的"最小结点"
        y = successor(z);
    }
    if (y.left != null) {
        x = y.left;
    } else {
        x = y.right;
    }
    if (x != null) {
        x.parent = y.parent;
    }
    if (y.parent == null) {
        bst.mRoot = x;
    } else if (y == y.parent.left) {
        y.parent.left = x;
    } else {
        y.parent.right = x;
    }
    if (y != z) {
        z.key = y.key;
    }
    return y;
}

public void remove(T key) {
    BSTNode<T> z, node;
    if ((z = search(mRoot, key)) != null) {
        node = null;
    }
}

2.8 打印树

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
/**
 * 打印二叉树
 *
 * @param tree      二叉树
 * @param key       结点的键值
 * @param direction 0：表示根节点
 *                  1：该结点是左子树
 *                  2：该结点是右子树
 */
private void print(BSTNode<T> tree, T key, int direction) {
    if (tree != null) {
        if (direction == 0) {
            //根节点
            System.out.printf("%2d is root \n", tree.key);
        } else {
            System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction == 1 ? "right" : "left");
        }
        print(tree.left, tree.key, -1);
        print(tree.right, tree.key, 1);
    }
}

public void print() {
    if (mRoot != null) {
        print(mRoot, mRoot.key, 0);
    }
}

2.9 销毁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 销毁二叉树
 */
private void destroy(BSTNode<T> tree) {
    if (tree==null) {
        return ;
    }
    if (tree.left != null) {
        destroy(tree.left);
    }
    if (tree.right != null) {
        destroy(tree.right);
    }

    tree=null;
}

public void clear() {
    destroy(mRoot);
    mRoot = null;
}

3. 完整代码示例

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
/**
 * @author xiaoyuge
 */
public class BSTree<T extends Comparable<T>> {

    private BSTNode<T> mRoot; //根节点

    //内部类 --节点
    public class BSTNode<T extends Comparable<T>> {

        T key;  //关键字
        BSTNode<T> left;    //左子树
        BSTNode<T> right;    //右子树
        BSTNode<T> parent;    //父节点

        public BSTNode(T key, BSTNode<T> left, BSTNode<T> right, BSTNode<T> parent) {
            this.key = key;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }
        public T getKey(){
          return key;
        }

        @Override
        public String toString() {
          return "BSTNode{" +
                  "key=" + key +
                  '}';
        }
    }

    /**
     * 先序遍历
     *
     * @param tree 树
     */
    private void preOrder(BSTNode<T> tree) {
        if (tree != null) {
            System.out.print(tree.key + "");
            preOrder(tree.left);
            preOrder(tree.right);
        }
    }

    public void preOrder() {
        preOrder(mRoot);
    }

    /**
     * 中序遍历
     *
     * @param tree 树
     */
    private void inOrder(BSTNode<T> tree) {
        if (tree != null) {
            inOrder(tree.left);
            System.out.print(tree.key);
            inOrder(tree.right);
        }
    }

    public void inOrder() {
        inOrder(mRoot);
    }

    /**
     * 后序遍历
     *
     * @param tree 树
     */
    private void postOrder(BSTNode<T> tree) {
        if (tree != null) {
            postOrder(tree.left);
            postOrder(tree.right);
            System.out.print(tree.key);
        }
    }

    public void postOrder() {
        postOrder(mRoot);
    }

    /**
     * 递归实现查找"二叉树 X"中键值为 key 的节点
     */
    private BSTNode<T> search(BSTNode<T> x, T key) {
        if (x == null) {
            return x;
        }
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            //key在左子树上
            return search(x.left, key);
        } else if (cmp > 0) {
            //key 在右子树上
            return search(x.right, key);
        } else {
            return x;
        }
    }

    public BSTNode<T> search(T key) {
        return search(mRoot, key);
    }

    /**
     * 非递归实现查找"二叉树 X"中键值为 key 的节点
     */
    private BSTNode<T> iterativeSearch(BSTNode<T> x, T key) {
        while (!(null == x)) {
            int cmp = key.compareTo(x.key);
            if (cmp < 0) {
                x = x.left;
            } else if (cmp > 0) {
                x = x.right;
            } else {
                return x;
            }
        }
        return x;
    }

    public BSTNode<T> iterativeSearch(T key) {
        return iterativeSearch(mRoot, key);
    }

    /**
     * 查找最大结点：返回tree为根节点的二叉树的最大结点
     * 最大结点永远在右子树上
     */
    private BSTNode<T> maximum(BSTNode<T> tree) {
        if (tree == null) {
            return null;
        }
        while (tree.right != null) {
            tree = tree.right;
        }
        return tree;
    }

    public T maximum() {
        BSTNode<T> p = maximum(mRoot);
        if (p != null) {
            return p.key;
        }
        return null;
    }

    /**
     * 查找最小结点：返回tree为根节点的二叉树的最小结点
     * 最小结点永远在左子树上
     */
    private BSTNode<T> minimum(BSTNode<T> tree) {
        if (tree == null) {
            return null;
        }
        while (tree.left != null) {
            tree = tree.left;
        }
        return tree;
    }

    public T minimum() {
        BSTNode<T> p = minimum(mRoot);
        if (p != null) {
            return p.key;
        }
        return null;
    }

    /**
     * 找结点(x)的前驱结点。即，查找"二叉树中数据值小于该结点"的"最大结点"。
     */
    public BSTNode<T> predecessor(BSTNode<T> x) {
        //如果x存在左子树，则"x的前驱结点"为：以其左子树根的子树的最大结点
        if (x.left != null) {
            return maximum(x.left);
        }
        // 如果x没有左孩子。则x有以下两种可能:
        //1. x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
        //2. x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
        BSTNode<T> y = x.parent;
        while ((y != null) && (x == y.left)) {
            x = y;
            y = y.parent;
        }
        return y;
    }

    /**
     * 找结点(x)的后继结点。即，查找"二叉树中数据值大于该结点"的"最小结点"。
     */
    public BSTNode<T> successor(BSTNode<T> x) {
        // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
        if (x.right != null) {
            return minimum(x.right);
        }
        // 如果x没有右孩子。则x有以下两种可能:
        // 1. x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
        // 2. x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
        BSTNode<T> y = x.parent;
        while ((y != null) && (x == y.right)) {
            x = y;
            y = y.parent;
        }
        return y;
    }

    /**
     * 将结点插入到二叉树中
     *
     * @param bst 二叉树
     * @param z   插入的结点
     */
    private void insert(BSTree<T> bst, BSTNode<T> z) {
        int cmp;
        BSTNode<T> y = null;
        BSTNode<T> x = bst.mRoot;

        //查找z的插入位置
        while (x != null) {
            y = x;
            cmp = z.key.compareTo(x.key);
            if (cmp < 0) {
                x = x.left;
            } else {
                x = x.right;
            }
        }

        z.parent = y;
        if (y == null) {
            bst.mRoot = z;
        } else {
            cmp = z.key.compareTo(y.key);
            if (cmp < 0) {
                y.left = z;
            } else {
                y.right = z;
            }
        }
    }

    /**
     * 新建结点(key)，并将其插入到二叉树中
     *
     * @param key 插入结点的键值
     */
    public void insert(T key) {
        BSTNode<T> z = new BSTNode<T>(key, null, null, null);
        insert(this, z);
    }

    /**
     * 删除结点，并返回被删除的结点
     *
     * @param bst 二叉树
     * @param z   删除的结点
     */
    private BSTNode<T> remove(BSTree<T> bst, BSTNode<T> z) {
        BSTNode<T> x = null;
        BSTNode<T> y = null;
        if ((z.left == null) || (z.right == null)) {
            //情况二：如果被删除结点只有左子树或右子树，孩子顶替
            y = z;
        } else {
            //二叉树中数据值大于该结点"的"最小结点"
            y = successor(z);
        }
        if (y.left != null) {
            x = y.left;
        } else {
            x = y.right;
        }
        if (x != null) {
            x.parent = y.parent;
        }
        if (y.parent == null) {
            bst.mRoot = x;
        } else if (y == y.parent.left) {
            y.parent.left = x;
        } else {
            y.parent.right = x;
        }
        if (y != z) {
            z.key = y.key;
        }
        return y;
    }

    public void remove(T key) {
        BSTNode<T> z, node;
        if ((z = search(mRoot, key)) != null) {
            node = null;
        }
    }

    /**
     * 打印二叉树
     *
     * @param tree      二叉树
     * @param key       结点的键值
     * @param direction 0：表示根节点
     *                  1：该结点是左子树
     *                  2：该结点是右子树
     */
    private void print(BSTNode<T> tree, T key, int direction) {
        if (tree != null) {
            if (direction == 0) {
                //根节点
                System.out.printf("%2d is root \n", tree.key);
            } else {
                System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction == 1 ? "right" : "left");
            }
            print(tree.left, tree.key, -1);
            print(tree.right, tree.key, 1);
        }
    }

    public void print() {
        if (mRoot != null) {
            print(mRoot, mRoot.key, 0);
        }
    }
    /**
     * 销毁二叉树
     */
    private void destroy(BSTNode<T> tree) {
        if (tree==null) {
            return ;
        }
        if (tree.left != null) {
            destroy(tree.left);
        }
        if (tree.right != null) {
            destroy(tree.right);
        }
        tree=null;
    }

    public void clear() {
        destroy(mRoot);
        mRoot = null;
    }
}

4. 测试程序

下面对测试程序的流程进行分析：

  • 新建二叉树root

  • 向二叉树中依次加入1，5，4，3，2，6。如图所示：

BST测试

Java代码测试：

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
/**
 * 二叉树
 *
 * @author xiaoyuge
 */
public class BstTreeTest {

  private static final int[] arr = {1, 5, 4, 3, 2, 6};

  public static void main(String[] args) {
    BSTree<Integer> tree = new BSTree<>();
    System.out.print("\n ---- 依次添加：");
    for (int i : arr) {
      System.out.print(i + "");
      tree.insert(i);
    }
    System.out.print("\n ----前序遍历：");
    tree.preOrder();
    System.out.print("\n ----中序遍历：");
    tree.inOrder();
    System.out.print("\n ----后序遍历：");
    tree.postOrder();

    System.out.println("\n---最小值：" + tree.minimum());
    System.out.println("---最大值：" + tree.maximum());
    System.out.println("---打印树的详细信息");
    tree.print();

    System.out.println("---删除根节点" + arr[3]);
    tree.remove(arr[3]);
    System.out.print("\n ----中序遍历：");
    tree.inOrder();

    System.out.print("\n ---销毁二叉树");
    tree.clear();
  }
}

运行后输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
---- 依次添加：154326
----前序遍历：154326
----中序遍历：123456
----后序遍历：234651
---最小值：1
---最大值：6
---打印树的详细信息
 1 is root 
 5 is  1's  right child
 4 is  5's   left child
 3 is  4's   left child
 2 is  3's   left child
 6 is  5's  right child
---删除根节点3
----中序遍历：123456
---销毁二叉树

5. 参考文章

本文主要来源于@pdai的https://pdai.tech/md/algorithm/alg-basic-tree-search.html，在此基础上重新组织和增加了内容。

小余哥xiaoyouge

分享一些技术教程与实践，以及日常踩坑记录。