二分搜索树的底层实现

二分搜索树的底层实现

  1. 二分搜索树是一个二叉树,二分搜索树的每个节点都大于其左子树的所有节点,并且小于其右子树的所有节点。因此二分搜索树中的元素必须具有可比较性。另外二分搜索树的每一颗之树也是二分搜索树。
  2. 二分搜索树的具体实现,包括前中后序遍历与利用队列实现层序遍历,以及用栈实现前序遍历等操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
package BinarySearchTree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
* @ Description: 二分搜索树的实现
* @ Date: Created in 08:59 20/07/2018
* @ Author: Anthony_Duan
*/
public class BST<E extends Comparable<E>> {
private class Node {
private E e;
public Node left, right;

public Node(E e) {
this.e = e;
left = null;
right = null;
}
}

private Node root;
private int size;


public BST() {
root = null;
size = 0;
}


public int size() {
return size;
}

public boolean isEmpty() {
return size == 0;
}


/**
* 向以node为根的二分搜索树中插入元素e 递归算法
*
* @param node 当前要插入二分搜索树的根
* @param e 元素e
* @return 当前调用过程中的二分搜索树的根
*/
private Node add(Node node, E e) {

//递归的终止条件,如果当前要插入树为空则该节点就是要如节点的地方
if (node == null) {
size++;
return new Node(e);
}

//如果小于当前节点则把左子树传入递归方法
if (e.compareTo(node.e) < 0) {
//需要注意的是这里返回的node.left 每次add方法返回的都会有一个节点
//如果是终止条件返回的是插入元素的节点,如果是中间的递归程序返回的是 当前节点node 并不会改变当前节点node的地址
node.left = add(node.left, e);
} else if (e.compareTo(node.e) > 0) {
node.right = add(node.right, e);
}
//这里很重要
return node;
}

/**
* 用户调用这个方法
*
* @param e
*/
public void add(E e) {
root = add(root, e);
}

private boolean contains(Node node, E e) {
if (node == null) {
return false;
}
if (e.compareTo(node.e) == 0) {
return true;
} else if (e.compareTo(e) < 0) {
return contains(node.left, e);
} else {
return contains(node.right, e);
}
}

/**
* 用户调用这个方法
* 看二分搜索树中是否包含元素e
*
* @param e
* @return
*/
public boolean contains(E e) {
return contains(root, e);
}

/**
* 二分搜索树的前序遍历
*
* @param node
*/
private void preOrder(Node node) {
if (node == null) {
return;
}
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}


/**
* 用栈完成二分搜索树的非递归前序遍历
*/
private void preOrderNR() {
if (root == null) {
return;
}
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node cur = stack.pop();
System.out.println(cur.e);

if (cur.right != null) {
stack.push(cur.right);
}
if (cur.left != null) {
stack.push(cur.left);
}
}
}

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


/**
* 后序遍历
*
* @param node
*/
private void postOrder(Node node) {
if (node == null) {
return;
}
postOrder(node.left);
postOrder(node.right);
System.out.println(node.e);
}

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

/**
* 中序遍历
*
* @param node
*/
private void inOrder(Node node) {
if (node == null) {
return;
}
inOrder(node.left);
System.out.println(node.e);
inOrder(node.right);
}

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


//二分搜索树的层序遍历
public void levelOrder() {
if (root == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node cur = queue.remove();
System.out.println(cur.e);
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
}
}

/**
* 寻找二分搜索树的最小元素
*
* @return
*/
public E minimum() {
if (size == 0) {
throw new IllegalArgumentException("BST is empty!");
}
return minimum(root).e;
}

/**
* 返回二分搜索树中最小值所在的节点
*
* @param node
* @return
*/
private Node minimum(Node node) {
if (node.left == null) {
return node;
}
return minimum(node.left);
}

/**
* 寻找二分搜索树中的最大元素
*
* @return
*/
public E maximum() {
if (size == 0) {
throw new IllegalArgumentException("BST is empty!");
}
return maximum(root).e;
}

/**
* 返回以node为根的二分搜索树的最大值所在的节点
*
* @param node
* @return
*/
private Node maximum(Node node) {
if (node.right == null) {
return node;
}
return maximum(node.right);
}

/**
* 从二分搜索树中删除最小值所在的节点,返回最小值
*
* @return
*/
public E removeMin() {
E ret = minimum();
root = removeMin(root);
return ret;
}

/**
* 删除掉以node为根的二分搜索树中的最小节点
* 返回删除节点后新的二分搜索树的根
*
* @param node
* @return
*/
private Node removeMin(Node node) {
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}

/**
* 删除二分搜索树中最大值所在的节点
*
* @return
*/
public E removeMax() {
E ret = maximum();
root = removeMax(root);
return ret;
}

/**
* 删除掉以node为根的二分搜索树中的最大节点
* 返回删除后的新二分搜索树的根
*
* @param node
* @return
*/
private Node removeMax(Node node) {
if (node.right == null) {
Node leftNode = node.left;
node.right = null;
size--;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}


/**
* 从二分搜索树中删除元素为e 的节点
*
* @param e
*/
public void remove(E e) {
root = remove(root, e);
}

/**
* 删除掉以node为根的二分搜索树中值为e 的节点 递归算法
* 返回删除节点后新的二分搜索树的根
*
* @param node
* @param e
* @return
*/
private Node remove(Node node, E e) {
if (node == null) {
return null;
}
if (e.compareTo(node.e) < 0) {
node.left = remove(node.left, e);
return node;
} else if (e.compareTo(node.e) > 0) {
node.right = remove(node.right, e);
return node;
} else {//e.compareTo(node.e)==0

//如果左子树为空
if (node.left == null) {
Node righNode = node.right;
node.right = null;
size--;
return righNode;
}
//如果右子树为空
if (node.right == null) {
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}

/**
* 左右子树都不为空的情况下
* 首先找到比待删除节点大的最小的节点 即待删除节点右子树中的最小节点
* 用这个节点替代删除节点的位置
*/
Node successor = minimum(node.right);
successor.left = node.left;
//这里removeMax方法中已经有了size--,所以这里不需要再对size进行维护
successor.right = removeMax(node.right);

node.left = node.right = null;
return successor;
}
}


private void generateString(Node node, int depth, StringBuilder res) {

if (node == null) {
res.append(generateDepthString(depth) + "null\n");
return;
}


res.append(generateDepthString(depth) + node.e + "\n");
generateString(node.left, depth + 1, res);
generateString(node.right, depth + 1, res);
}

private String generateDepthString(int depth) {
StringBuilder res = new StringBuilder();
for (int i = 0; i < depth; i++) {
res.append("--");
}
return res.toString();
}

@Override
public String toString() {
StringBuilder res = new StringBuilder();
generateString(root, 0, res);
return res.toString();
}
}
-------------End Of This ArticleThank You For Reading-------------