BinarySearchTree(二叉搜索树的实现)

二叉搜索树的实现(Java)

  • 若它的左子树不为空,左子树上所有节点的值都小于它的根节点。
  • 若它的右子树不为空,右子树上所有的节点的值都大于它的根节点。

img

接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @author weijie.zeng
* @date 2022-03-26-14:25
*/
public interface Tree<E> {
//是否为空
boolean isEmpty();
//清空所有结点
void clear();
//结点个数
int size();
//是否包含某个元素
boolean contains(E element);
//树的添加
void add(E element);
//删除树的某个结点
E remove(E element);
}

代码实现

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
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
/**
* @author weijie.zeng
* @create 2022-03-26-14:28
*/
public class BinarySearchTree<E> implements Tree<E>, BinaryTreeInfo {
protected int size;
protected Node<E> root;
protected Comparator<E> comparator;

public BinarySearchTree() {
this(null);
}

public BinarySearchTree(Comparator<E> comparator) {
this.comparator = comparator;
}

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

@Override
public void clear() {
root = null;
size = 0;
}

@Override
public int size() {
return size;
}

@Override
public boolean contains(E element) {
return getNode(element) != null;
}

public Node<E> subsequent(Node<E> node) {
if (node == null) return null;
Node<E> p = node.right;
//右子树不为空的时候,后继结点一定在右子树的左孩子里
if (p != null) {
while (p.left != null) {
p = p.left;
}
return p;
}
//否则右子树为空
//那么后继结点一定在父节点中
//往上寻找
while (node.parent != null && node == node.parent.right) {
node = node.parent;
}
//node.parent==null
//node==node.parent.right
return node.parent;
}

/**
* 寻找前驱结点
*
* @param node
* @return
*/
public Node<E> precursor(Node<E> node) {
if (node == null) return null;
Node<E> p = node.left;
//左子树不为空的时候,前驱结点一定在左子树的右孩子里
if (p != null) {
while (p.right != null) {
p = p.right;
}
return p;
}
//否则左子树为空
//那么前驱结点一定在父节点中
//往上寻找
while (node.parent != null && node == node.parent.left) {
node = node.parent;
}
//node.parent==null
//node==node.parent.right
return node.parent;
}

/**
* 层序遍历实现计算树的高度
*/
public int height() {
if (root == null) {
return 0;
}
int height = 0;
//存储每一层元素的数量
int levelSize = 1;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
levelSize--;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
if (levelSize == 0) {
//意味着即将要访问下一层
levelSize = queue.size();
height++;
}
}
return height;
}

public boolean isComplete() {
if (root == null) {
return false;
}
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
boolean leaf = false;
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
//判断叶子结点
if (leaf && !(node.left == null && node.right == null)) {
leaf = false;
}
if (node.left != null && node.right != null) {
queue.offer(node.left);
queue.offer(node.right);
} else if (node.left == null && node.right != null) {
return false;
} else {
//后面遍历的结点都必须是叶子结点
leaf = true;
if (node.left != null) {
queue.offer(node.left);
}

}

}
return true;
}

/**
* 递归获取树的高度
*
* @return
*/
public int height1() {
return height1(root);
}

private int height1(Node<E> node) {
if (node == null) {
return 0;
}
return 1 + Math.max(height1(node.left), height1(node.right));
}

public void preorderTraversal(Visitor<E> visitor) {
preorderTraversal(root, visitor);
}

private void preorderTraversal(Node<E> node, Visitor<E> visitor) {
if (node == null || visitor == null) {
return;
}
visitor.visit(node.element);
preorderTraversal(node.left, visitor);
preorderTraversal(node.right, visitor);
}

public void inorderTraversal(Visitor<E> visitor) {
inorderTraversal(root, visitor);
}

private void inorderTraversal(Node<E> node, Visitor<E> visitor) {
if (node == null || visitor == null) {
return;
}
inorderTraversal(node.left, visitor);
visitor.visit(node.element);
inorderTraversal(node.right, visitor);
}

public void postorderTraversal(Visitor<E> visitor) {
postorderTraversal(root, visitor);
}

private void postorderTraversal(Node<E> node, Visitor<E> visitor) {
if (node == null || visitor == null) {
return;
}
//递归遍历左结点
postorderTraversal(node.left, visitor);
//递归遍历右结点
postorderTraversal(node.right, visitor);
visitor.visit(node.element);
}

/**
* 层序遍历
*/
public void levelOrderTraversal(Visitor<E> visitor) {
//如果根节点为空
//则不进行遍历
if (root == null || visitor == null) {
return;
}
//创建辅助队列
Queue<Node<E>> queue = new LinkedList<>();
//将根节点入队
queue.offer(root);
//只要队列不为空
//则进行层序遍历
while (!queue.isEmpty()) {
//将根节点出队
Node<E> node = queue.poll();
visitor.visit(node.element);
//如果有左儿子节点
if (node.left != null) {
//则右儿子入队
queue.offer(node.left);
}
//如果有左儿子节点
if (node.right != null) {
//则右儿子入队
queue.offer(node.right);
}
}
}

protected Node<E> createNode(E element, Node<E> parent) {
return new Node<>(element, parent);
}

protected void afterAdd(Node<E> node) {

}

@Override
public void add(E element) {
elementNotNullCheck(element);
//添加第一个结点
if (root == null) {
root = createNode(element, null);
size++;
afterAdd(root);
return;
}
//添加的不是第一个结点
//找到根节点
Node<E> node = root;
//找到父节点
Node<E> parentNode = null;
//比较当前待插入的结点与结点本身打的大小
int cmp = 0;
while (node != null) {
cmp = compare(element, node.element);
parentNode = node;
if (cmp > 0) {
node = node.right;
} else if (cmp < 0) {
node = node.left;
} else {
//相等
node.element = element;
}
}
//看看插入到父节点的哪个位置
Node<E> newNode = createNode(element, parentNode);
if (cmp > 0) {
//说明要插入的结点比较大
parentNode.right = newNode;
} else {
//说明要插入的结点比较小
parentNode.left = newNode;
}
size++;
//新添加节点之后的处理
afterAdd(newNode);
}

/**
* @param e1 第一个结点的值
* @param e2 第二个结点的值
* @return 返回值0代表e1==e2,大于0代表e1>e2,反之
*/
private int compare(E e1, E e2) {

if (comparator != null) {
comparator.compare(e1, e2);
}
//如果没传比较器,就默认比较规则
return ((Comparable<E>) e1).compareTo(e2);
}

private void elementNotNullCheck(E element) {
if (element == null) {
throw new IllegalArgumentException("结点元素不能为空");
}
}
private void checkelementnotnull(E element){
if(element == null){
throw new IllegalArgumentException("element must be not null");
}
}
@Override
public E remove(E element) {
remove(getNode(element));
return null;
}
private boolean hasTwoChildren(Node<E> node){
if(node.right != null && node.left != null){
return true;
}
return false;
}

protected void afterRemove(Node<E> node) { }

private void remove(Node<E> node) {
if (node == null) return;

size--;

if (hasTwoChildren(node)) { // 度为2的节点
// 找到后继节点
Node<E> s = subsequent(node);
// 用后继节点的值覆盖度为2的节点的值
node.element = s.element;
// 删除后继节点
node = s;
}

// 删除node节点(node的度必然是1或者0)
Node<E> replacement = node.left != null ? node.left : node.right;

if (replacement != null) { // node是度为1的节点
// 更改parent
replacement.parent = node.parent;
// 更改parent的left、right的指向
if (node.parent == null) { // node是度为1的节点并且是根节点
root = replacement;
} else if (node == node.parent.left) {
node.parent.left = replacement;
} else { // node == node.parent.right
node.parent.right = replacement;
}

// 删除节点之后的处理
afterRemove(node);
} else if (node.parent == null) { // node是叶子节点并且是根节点
root = null;

// 删除节点之后的处理
afterRemove(node);
} else { // node是叶子节点,但不是根节点
if (node == node.parent.left) {
node.parent.left = null;
} else { // node == node.parent.right
node.parent.right = null;
}

// 删除节点之后的处理
afterRemove(node);
}
}

private Node<E> getNode(E element) {
Node<E> node = this.root;
while (node != null) {
int cmp = compare(element, node.element);
if (cmp == 0) {
return node;
}
if (cmp > 0) {
node = node.right;
} else {
node = node.left;
}
}
return null;
}

@Override
public Object root() {
return root;
}

@Override
public Object left(Object node) {
return ((Node<E>) node).left;
}

@Override
public Object right(Object node) {
return ((Node<E>) node).right;
}

@Override
public Object string(Object node) {
return ((Node<E>) node).element;
}

public interface Visitor<E> {
/**
* 对结点的操作
*
* @param element 结点元素
*/
void visit(E element);
}

protected static class Node<E> {
E element;
Node<E> left;
Node<E> right;
Node<E> parent;

public Node(E element, Node<E> parent) {
this.element = element;
this.parent = parent;
}
public boolean isLeftChild() {
return parent != null && this == parent.left;
}

public boolean isRightChild() {
return parent != null && this == parent.right;
}
}
}