数据结构 四 二叉查找树


二叉查找树

二叉查找树是一个有序的树,使用二叉查找树可以极大的方便查找排好序的元素

二叉查找树保证其中每一个结点的右子树都比他大,左子树都比他小,即左小右大。设x为二叉查找树中的一个结点,x节点包含关键字key,节点x的key值记为key[x]。如果y是x的左子树中的一个结点,则key[y] <= key[x];如果y是x的右子树的一个结点,则key[y] >= key[x]。

前驱

在中序遍历中排在某元素前面的那个元素是该元素的前驱,当然第一个元素是没有前驱的。在数组型的二叉树中,前驱就放在其前面。
寻找前驱的算法如下:
1. 若一个结点有左子树,则左子树的最右侧即为所求前驱。(也就是左边的最大值)
2. 若没有左子树,则从这个结点向上遍历,直到找到某个结点是其父节点的右子树,则这个结点的父节点即为所求。所不存在则说明没有前驱。

后继

在中序遍历中排在某元素后面的那个元素是该元素的后继,当然最后一个元素是没有后继的。在数组型的二叉树中,后继就放在其后面。
寻找后继的算法如下:
1. 若一个结点有右子树,则右子树的最左侧即为所求前驱。(也就是右边的最小值)
2. 若没有右子树,则从这个结点向上遍历,直到找到某个结点是其父节点的左子树,则这个结点的父节点即为所求。所不存在则说明没有后继。

ADT

  1. 构造空树
  2. 销毁一个树
  3. 判断树是否为空
  4. 插入一个结点
  5. 删除一个结点
  6. 打印二叉树
  7. 前序遍历
  8. 中序遍历
  9. 后序遍历
  10. 根据值的大小查找结点。
  11. 查找子树的最小结点
  12. 查找子树的最大结点
  13. 查找某个结点的前驱
  14. 查找某个结点的后继

二叉查找树的实现

接口说明

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
//二叉查找树
// binary search tree

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <time.h>

typedef struct BSTree
{
int key; //可以用Item代替,不过为了方便学习,就不这样了。
struct BSTree *parent;
struct BSTree *left;
struct BSTree *right;
} * BSTree;

//初始化
bool InitBSTree(BSTree *tree);

//销毁
bool DestroyBSTree(BSTree *tree);

//空
bool EmptyBSTree(BSTree *tree);

//插入
bool InsertBSTree(BSTree *tree, int key);

//删除
bool DeleteBSTree(BSTree *tree, int key);

//打印二叉树 0代表根节点 1代表左边 -1代表右
void Print_BSTree(BSTree *tree, int direction);

// 前序遍历
void Preorder_BSTree(BSTree *tree);
// 中序遍历
void Inorder_BSTree(BSTree *tree);
// 后序遍历
void Postorder_BSTree(BSTree *tree);

// (递归实现)查找"二叉树x"中键值为key的节点
bool Search_BSTree(BSTree *tree, int key, BSTree *tree_save);
// (非递归实现)查找"二叉树x"中键值为key的节点
bool iterative_bstree_search(BSTree *tree, int key, BSTree *tree_save);

// 查找最小结点:返回tree为根结点的二叉树的最小结点。
bool Min_BSTree(BSTree *tree, BSTree *tree_save);
// 查找最大结点:返回tree为根结点的二叉树的最大结点。
bool Max_BSTree(BSTree *tree, BSTree *tree_save);

// 找结点(x)的后继结点。即,查找"二叉树中数据值大于该结点"的"最小结点"。
bool Sucessor_BSTree(BSTree *tree, BSTree *x, BSTree *sucessor);
// 找结点(x)的前驱结点。即,查找"二叉树中数据值小于该结点"的"最大结点"。
bool Predecessor_BSTree(BSTree *tree, BSTree *x, BSTree *prede);

void AutoFillBSTree(BSTree *tree, int size);

接口实现

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
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
#include "bstree.h"

//初始化
bool InitBSTree(BSTree *tree)
{
(*tree) = NULL;
printf("初始化成功\n");
}

//销毁
bool DestroyBSTree(BSTree *tree)
{
if ((*tree) != NULL)
{
if ((*tree)->left == NULL && (*tree)->right == NULL)
{
free(tree);
return true;
}
DestroyBSTree(&((*tree)->left));
DestroyBSTree(&((*tree)->right));
if ((*tree) == NULL)
{
printf("销毁成功\n");
return true;
}
else
{
printf("销毁失败\n");
return false;
}
}
if ((*tree) == NULL)
{
printf("销毁成功\n");
return true;
}
}

//空
bool EmptyBSTree(BSTree *tree)
{
if ((*tree) == NULL)
{
printf("空\n");
return true;
}
else
{
printf("不空\n");
return false;
}
}

//插入
bool InsertBSTree(BSTree *tree, int key)
{
BSTree new = (BSTree)malloc(sizeof(struct BSTree));
new->key = key;
new->left = NULL;
new->right = NULL;
new->parent = NULL;
//左低右高
if (EmptyBSTree(tree))
{
(*tree) = new;
printf("插入成功 %d\n", key);
return true;
}
else
{
//寻找位置进行插入;
BSTree p = (*tree);
while (p != NULL)
{
//小 往左走
if (new->key < p->key)
{
if (p->left == NULL)
{
//左边为空,则插入到左边即可
p->left = new;
new->parent = p;
printf("插入成功 %d 到 %d 的左边\n", key, p->key);
return true;
}
else
{
//左边不空,继续寻找
p = p->left;
}
}
//大 往右走
else if (new->key > p->key)
{
if (p->right == NULL)
{
//右边为空,则插入到右边即可
p->right = new;
new->parent = p;
printf("插入成功 %d 到 %d 的右边\n", key, p->key);
return true;
}
else
{
//右边不空,继续寻找
p = p->right;
}
}
else if (new->key == p->key)
{
printf("不允许相等的元素存在,插入失败\n");
return false;
}
}
}
printf("插入失败\n");
return false;
}

//删除
bool DeleteBSTree(BSTree *tree, int key)
{
//删除的是根节点 删除叶子节点 删除的结点没有左子树或者右子树
//空
if (EmptyBSTree(tree))
{
printf("删除失败\n");
return false;
}
BSTree p = (*tree);
//p指向树的每一个结点(其实就是相应内存区域),改变 p->key,就是改变这块内存上key的值。所以才可以实现使用p遍历并更改结点。
//其实,p->key==(*p).key 对(*p).key很自然就修改了其值,这点很容易理解。
//假设这棵树在一个树的左边 解决删除的是根节点的问题
BSTree fakeroot = (BSTree)malloc(sizeof(struct BSTree));
fakeroot->left = p;
fakeroot->right = NULL;
fakeroot->parent = NULL;
p->parent = fakeroot;
if (p->key == (*p).key)
printf("true\n");
while (p != NULL)
{
//printf("1111111111111111111111\n");
if (p->key < key)
{
//向右走
//printf("向右走\n");
p = p->right;
}
else if (p->key > key)
{
p = p->left;
//printf("向左走\n");
}
else if (p->key == key)
{
//找到了,进行删除 p
printf("找到了,进行删除 p %d\n", p->key);
BSTree l = p->left;
BSTree r = p->right;
//p为左子树
if (p->parent->left == p)
{
//p没有左子树
if ((l == NULL) && (r != NULL))
{
p->parent->left = r;
r->parent = p->parent;
free(p);
p = NULL;
(*tree) = fakeroot->left;
printf("删除成功\n");
return true;
}
//p没有右子树
else if ((r == NULL) && (l != NULL))
{
p->parent->left = l;
l->parent = p->parent;
free(p);
p = NULL;
(*tree) = fakeroot->left;
printf("删除成功\n");
return true;
}
//p左右子树都有
else if ((r != NULL) && (l != NULL))
{
//p为左节点,应为右侧的高 继位
p->parent->left = r;
//将l插入到r的最左下
while (r->left != NULL)
{
r = r->left;
}
//找到了右子树的最左边,插入左子树
r->left = l;
l->parent = r;
free(p);
p = NULL;
(*tree) = fakeroot->left;
printf("删除成功\n");
return true;
}
//左右子树都没有
else
{
p->parent->left = NULL;
free(p);
p = NULL;
(*tree) = fakeroot->left;
printf("删除成功\n");
return true;
}
}
//p为右子树
else
{
//将 右子树顶替p的位置,然后将左子树插入到右子树的最左下面即可,因为右边比左边大。
//p为右节点,应为左侧的低 继位
//p没有左子树
if ((l == NULL) && (r != NULL))
{
p->parent->right = r;
r->parent = p->parent;
free(p);
p = NULL;
(*tree) = fakeroot->left;
printf("删除成功\n");
return true;
}
//p没有右子树
else if ((r == NULL) && (l != NULL))
{
p->parent->right = l;
l->parent = p->parent;
free(p);
p = NULL;
(*tree) = fakeroot->left;
printf("删除成功\n");
return true;
}
//p左右子树都有
else if ((r != NULL) && (l != NULL))
{
p->parent->right = l;
while (l->right != NULL)
{
l = l->right;
}
//找到了右子树的最左边,插入左子树
l->right = r;
r->parent = l;
free(p);
p = NULL;
(*tree) = fakeroot->left;
printf("删除成功\n");
return true;
}
//左右子树都没有
else
{
p->parent->right = NULL;
free(p);
p = NULL;
(*tree) = fakeroot->left;
printf("删除成功\n");
return true;
}
}
}
}
printf("没有找到这个元素,删除失败\n");
return true;
}

//打印二叉树 0代表根节点 -1代表左边 1代表右
void Print_BSTree(BSTree *tree, int direction)
{
BSTree p = *tree;
if (p != NULL)
{
//根节点
if (direction == 0)
{
printf("结点 %2d 为根节点\n", p->key);
}
//左
else if (direction == -1)
{
printf("结点 %2d 为结点 %2d 的left\n", p->key, p->parent->key);
}
else
{
printf("结点 %2d 为结点 %2d right\n", p->key, p->parent->key);
}
Print_BSTree(&(p->left), -1);
Print_BSTree(&(p->right), 1);
}
}

// 前序遍历
void Preorder_BSTree(BSTree *tree)
{
BSTree p = (*tree);
if (p == NULL)
{
return;
}
else
{
printf("%d ", p->key);
Preorder_BSTree(&(p->left));
Preorder_BSTree(&(p->right));
}
}
// 中序遍历
void Inorder_BSTree(BSTree *tree)
{
BSTree p = (*tree);
if (p == NULL)
{
return;
}
else
{
Inorder_BSTree(&(p->left));
printf("%d ", p->key);
Inorder_BSTree(&(p->right));
}
}
// 后序遍历
void Postorder_BSTree(BSTree *tree)
{
BSTree p = (*tree);
if (p == NULL)
{
return;
}
else
{
Postorder_BSTree(&(p->left));
Postorder_BSTree(&(p->right));
printf("%d ", p->key);
}
}

// (递归实现)查找"二叉树x"中键值为key的节点
bool Search_BSTree(BSTree *tree, int key, BSTree *tree_save)
{
BSTree p = (*tree);
if (p == NULL)
{
//*tree_save = NULL;
//printf("没找到\n");
return false;
}
if (p->key == key)
{
//找到了
*tree_save = p;
printf("找到了\n");
return true;
}
Search_BSTree(&(p->left), key, tree_save);
Search_BSTree(&(p->right), key, tree_save);
}
// (非递归实现)查找"二叉树x"中键值为key的节点
bool iterative_bstree_search(BSTree *tree, int key, BSTree *tree_save)
{
BSTree p = (*tree);
while (p != NULL)
{
if (p->key == key)
{
//找到了
(*tree_save) = p;
printf("找到了\n");
return true;
}
else if (p->key < key)
{
//往右走
p = p->right;
}
else if (p->key > key)
{
p = p->left;
}
}
//没找到
(*tree_save) = NULL;
printf("没找到\n");
return false;
}

// 查找最小结点:返回tree为根结点的二叉树的最小结点。
bool Min_BSTree(BSTree *tree, BSTree *tree_save)
{
BSTree p = (*tree);
if (p == NULL)
{
*tree_save = NULL;
return false;
}
while (p->left != NULL)
{
p = p->left;
}
*tree_save = p;
return true;
}
// 查找最大结点:返回tree为根结点的二叉树的最大结点。
bool Max_BSTree(BSTree *tree, BSTree *tree_save)
{
BSTree p = (*tree);
if (p == NULL)
{
*tree_save = NULL;
return false;
}
while (p->right != NULL)
{
p = p->right;
}
*tree_save = p;
return true;
}

//前驱节点:对一棵二叉树进行中序遍历,遍历后的顺序,当前节点的前一个节点为该节点的前驱节点;

//后继节点:对一棵二叉树进行中序遍历,遍历后的顺序,当前节点的后一个节点为该节点的后继节点;

// 找结点(x)的后继结点。即,查找"二叉树中数据值大于该结点"的"最小结点"。
bool Sucessor_BSTree(BSTree *tree, BSTree *x, BSTree *sucessor)
{
//即其右子树的最左边
if ((*x) == NULL)
{
printf("空结点,没有后继\n");
(*sucessor) = NULL;
return false;
}
//有右子树
else if ((*x)->right != NULL)
{
Min_BSTree(&((*x)->right), sucessor);
printf("找到了后继,%d 的后继为 %d \n", (*x)->key, (*sucessor)->key);
return true;
}
//没有右子树 则从此开始向上找一个是左结点的结点
else if ((*x)->right == NULL)
{
BSTree p = *x;
//从x往上查,直到有一个结点是左节点 则该左节点的父节点为所求
while (p->parent != NULL)
{
if (p->parent->left == p)
{
*sucessor = p->parent;
printf("找到了后继,%d 的后继为 %d \n", (*x)->key, (*sucessor)->key);
return true;
}
else
{
p = p->parent;
}
}
//p此时已经是root了,还没有找到说明那个结点没有后继。
printf("结点 %d 没有后继\n", (*x)->key);
(*sucessor) = NULL;
return false;
}
}
// 找结点(x)的前驱结点。即,查找"二叉树中数据值小于该结点"的"最大结点"。
bool Predecessor_BSTree(BSTree *tree, BSTree *x, BSTree *prede)
{
if (*x == NULL)
{
printf("空结点,没有前驱\n");
*prede = NULL;
return false;
}
//左子树 则寻找其左子树的最大值
if ((*x)->left != NULL)
{
Max_BSTree(&((*x)->left), prede);
printf("找到了前驱,%d 的前驱为 %d \n", (*x)->key, (*prede)->key);
return true;
}
//没有左子树,则向上寻找一个是其父节点的右子树的结点。
else if ((*x)->left == NULL)
{
BSTree p = *x;
while (p->parent != NULL)
{
if (p->parent->right == p)
{
*prede = p->parent;
printf("找到了前驱,%d 的前驱为 %d \n", (*x)->key, (*prede)->key);
return true;
}
else
{
p = p->parent;
}
}
//p此时已经是root了,还没有找到说明那个结点没有前驱。
printf("结点 %d 没有前驱\n", (*x)->key);
(*prede) = NULL;
return false;
}
}

void AutoFillBSTree(BSTree *tree, int size)
{
InsertBSTree(tree, 5);
InsertBSTree(tree, 4);
InsertBSTree(tree, 6);
InsertBSTree(tree, 2);
InsertBSTree(tree, 3);
InsertBSTree(tree, 1);
InsertBSTree(tree, 8);
InsertBSTree(tree, 7);
InsertBSTree(tree, 9);

for (int i = 1; i <= 10; i++)
{
BSTree sucessor = NULL;
BSTree x = NULL;
Search_BSTree(tree, i, &x);
Sucessor_BSTree(tree, &x, &sucessor);
if (sucessor != NULL)
printf("succor: %d\n", sucessor->key);
}
for (int i = 1; i <= 10; i++)
{
BSTree prede = NULL;
BSTree x = NULL;
Search_BSTree(tree, i, &x);
Predecessor_BSTree(tree, &x, &prede);
if (prede != NULL)
printf("succor: %d\n", prede->key);
}
}

接口使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include "bstree.c"

int main()
{
BSTree tree;
InitBSTree(&tree);
//DestroyBSTree(&tree);
AutoFillBSTree(&tree, 10);
printf("\n前序遍历: ");
Preorder_BSTree(&tree);
printf("\n中序遍历: ");
Inorder_BSTree(&tree);
printf("\n后序遍历: ");
Postorder_BSTree(&tree);
printf("\n");
Print_BSTree(&tree, 0);
}

文章作者: 崔文耀
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 崔文耀 !
  目录