京东自营 618 + 国补 iPhone 历史最低价
Java 二叉搜索树的一个简单实现（不平衡）。
二叉搜索树的一个简单实现（不平衡）。
实例源码：
源代码：
执行
执行中...
x
1
/**来自 时代Java公众号**/2
3
import java.util.ArrayDeque;4
5
6
7
public class BinaryTree {8
9
10
TreeNode root;11
12
13
public void insert(int value) {14
15
if (root == null) {16
17
root = new TreeNode();18
19
root.data = value;20
21
} else {22
23
insertNode(value, root);24
25
}26
27
}28
29
30
private void insertNode(int value, TreeNode current) {//时 代 J a v a - N o w J a v a . c o m31
32
if (value < current.data) {33
34
if (current.left == null) {35
36
current.left = new TreeNode();37
38
current.left.data = value;39
40
} else {41
42
insertNode(value, current.left);43
44
}45
46
} else {47
48
if (current.right == null) {49
50
current.right = new TreeNode();51
52
current.right.data = value;53
54
} else {55
56
insertNode(value, current.right);57
58
}59
60
}61
62
}63
64
65
public boolean contains(int value) {66
67
if (findNode(value) != null) {68
69
return true;70
71
} else {72
73
return false;74
75
}76
77
}78
79
80
private boolean containsRecursion(int value, TreeNode current) {81
82
if (current == null) {83
84
return false;85
86
} else if (current.data == value) {87
88
return true;89
90
} else {91
92
if (value > current.data) {93
94
return containsRecursion(value, current.right);95
96
} else {97
98
return containsRecursion(value, current.left);99
100
}101
102
}103
104
}105
106
107
108
public TreeNode findNode(int value) {109
110
return findNodeRecursion(value, root);111
112
}113
114
115
private TreeNode findNodeRecursion(int value, TreeNode current) {116
117
if (current == null) {118
119
return null;120
121
} else if (current.data == value) {122
123
return current;124
125
} else {126
127
if (value > current.data) {128
129
return findNodeRecursion(value, current.right);130
131
} else {132
133
return findNodeRecursion(value, current.left);134
135
}136
137
}138
139
140
}141
142
143
public TreeNode findParent(int value) {144
145
return findParentRecursion(value, root);146
147
}148
149
150
151
private TreeNode findParentRecursion(int value, TreeNode current) {152
153
if (root.data == value) {154
155
return null;156
157
}158
159
if (value < current.data) {160
161
if (current.left == null) {162
163
return null;164
165
} else if (current.left.data == value) {166
167
return current;168
169
} else {170
171
return findParentRecursion(value, current.left);172
173
}174
175
} else {176
177
if (current.right == null) {178
179
return null;180
181
} else if (current.right.data == value) {182
183
return current;184
185
} else {186
187
return findParentRecursion(value, current.right);188
189
}190
191
}192
193
}194
195
196
public boolean remove(int value) {197
198
TreeNode nodeToRemove = findNode(value);199
200
if (nodeToRemove == null) {201
202
return false;203
204
}205
206
TreeNode parent = findParent(value);207
208
if (root.left == null && root.right == null) {209
210
root = null;211
212
} else if (nodeToRemove.left == null && nodeToRemove.right == null) {213
214
if (value < parent.data) {215
216
parent.left = null;217
218
} else {219
220
parent.right = null;221
222
}223
224
} else if (nodeToRemove.left == null) {225
226
if (value < parent.data) {227
228
parent.left = nodeToRemove.right;229
230
} else {231
232
parent.right = nodeToRemove.right;233
234
}235
236
} else if (nodeToRemove.right == null) {237
238
if (value < parent.data) {239
240
parent.left = nodeToRemove.left;241
242
} else {243
244
parent.right = nodeToRemove.left;245
246
}247
248
} else {249
250
251
TreeNode largestValue = nodeToRemove.left;252
253
254
while (largestValue.right != null) {255
256
largestValue = largestValue.right;257
258
}259
260
261
TreeNode parentOfLargest = findParent(largestValue.data);262
263
if (parentOfLargest.left == largestValue) {264
265
if (largestValue.left == null) {266
267
parentOfLargest.left = null;268
269
} else {270
271
parentOfLargest.left = largestValue.left;272
273
}274
275
} else {276
277
parentOfLargest.right = null;278
279
}280
281
282
nodeToRemove.data = largestValue.data;283
284
}285
286
287
return true;288
289
}290
291
292
public TreeNode findMin() {293
294
if (root == null) {295
296
return null;297
298
}299
300
return findMinRecursion(root);301
302
303
}304
305
306
307
private TreeNode findMinRecursion(TreeNode current) {308
309
if (current.left == null) {310
311
return current;312
313
} else {314
315
return findMinRecursion(current.left);316
317
}318
319
}320
321
322
public TreeNode findMax() {323
324
if (root == null) {325
326
return null;327
328
}329
330
return findMaxRecursion(root);331
332
333
}334
335
336
private TreeNode findMaxRecursion(TreeNode current) {337
338
if (current.right == null) {339
340
return current;341
342
} else {343
344
return findMaxRecursion(current.right);345
346
}347
348
}349
350
351
352
public void traversePreorder() {353
354
traversePreorderHelper(root);355
356
}357
358
359
private void traversePreorderHelper(TreeNode current) {360
361
if (current != null) {362
363
System.out.println(current.data);364
365
traversePreorderHelper(current.left);366
367
traversePreorderHelper(current.right);368
369
}370
371
}372
373
374
public void traversePostorder() {375
376
traversePostorderHelper(root);377
378
}379
380
381
private void traversePostorderHelper(TreeNode current) {382
383
if (current != null) {384
385
traversePostorderHelper(current.left);386
387
traversePostorderHelper(current.right);388
389
System.out.println(current.data);390
391
}392
393
}394
395
396
public void traverseInorder() {397
398
traverseInorderHelper(root);399
400
}401
402
403
private void traverseInorderHelper(TreeNode current) {404
405
if (current != null) {406
407
traverseInorderHelper(current.left);408
409
System.out.println(current.data);410
411
traverseInorderHelper(current.right);412
413
}414
415
}416
417
418
419
public void traverseBreadth() {420
421
traverseBreadthHelper(root);422
423
}424
425
426
private void traverseBreadthHelper(TreeNode current) {427
428
ArrayDeque<TreeNode> deq = new ArrayDeque<TreeNode>();429
430
while (current != null) {431
432
System.out.println(current.data);433
434
if (current.left != null) {435
436
deq.add(current.left);437
438
}439
440
if (current.right != null) {441
442
deq.add(current.right);443
444
}445
446
if (!deq.isEmpty()) {447
448
current = deq.remove();449
450
} else {451
452
current = null;453
454
}455
456
}457
458
}459
460
461
public static void main(String[] args) {462
463
464
BinaryTree bt = new BinaryTree();465
466
bt.insert(42);467
468
bt.insert(13);469
470
bt.insert(666);471
472
bt.insert(10);473
474
bt.insert(11);475
476
bt.insert(7);477
478
bt.insert(9);479
480
bt.insert(4);481
482
483
System.out.println("1: " + bt.contains(1));484
485
System.out.println("10: " + bt.contains(10));486
487
System.out.println("42: " + bt.contains(42));488
489
System.out.println("13: " + bt.contains(13));490
491
System.out.println("11: " + bt.contains(11));492
493
System.out.println("7: " + bt.contains(7));494
/**代码未完, 请加载全部代码(NowJava.com).**/执行结果：
本文系作者在时代Java发表，未经许可，不得转载。如有侵权，请联系nowjava@qq.com删除。
编辑于
关注时代Java