|
二叉排序树（BST，Binary Sort Tree）具有这样的性质：对于二叉树中的任意节点，如果它有左子树或右子树，则该节点的数据成员大于左子树所有节点的数据成员，且小于右子树所有节点的数据成员。排序二叉树的中序遍历结果是从小到大排列的。
二叉排序树的查找和插入比较好理解，主要来看一下删除时的情况。
如果需要查找并删除如图8-6-8中的37， 51， 73，93这些在二叉排序树中是叶子的结点，那是很容易的，毕竟删除它们对整棵树来说，其他结点的结构并未受到影响。
对于要删除的结点只有左子树或只有右子树的情况，相对也比较好解决。那就是结点删除后，将它的左子树或右子树整个移动到删除结点的位置即可，可以理解为独子继承父业。比如图8-6-9，就是先删除35和99两结点，再删除58结点的变化图，最终，整个结构还是一个二叉排序树。
但是对于要删除的结点既有左子树又有右子树的情况怎么办呢？比如图8-6-10中的47结点若要删除了，它的两儿子和子孙们怎么办呢？
前人总结的比较好的方法就是，找到需要删除的结点p的直接前驱（或直接后继）s，用s来替换结点p，然后再删除此结点s，如图8-6-12所示。
注意：这里的前驱和后继是指中序遍历时的顺序。
 
Deletion
There are three possible cases to consider:
Deleting a leaf (node with no children): Deleting a leaf is easy, as we can simply remove it from the tree.
Deleting a node with one child: Remove the node and replace it with its child.
Deleting a node with two children: Call the node to be deleted N. Do not delete N. Instead, choose either itsin-order successor node or its in-
order predecessor node, R. Replace the value of N with the value of R, thendelete R.
As with all binary trees, a node's in-order successor is the left-most child of its right subtree, and a node's in-orderpredecessor is the right-most
child of its left subtree. In either case, this node will have zero or one children. Delete itaccording to one of the two simpler cases above.
下面来看代码：（参考《linux c 编程一站式学习》
C++ Code
|
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
|
|
/*************************************************************************
>FileName:binarysearchtree.h
>Author:Simba
>Mail:dameng34@163.com
>CreatedTime:Sat29Dec201206:05:55PMCST
************************************************************************/
#ifndefBST_H
#defineBST_H
typedefstructnode*link;
structnode
{
unsignedcharitem;
linkleft,right;
};
linksearch(linkt,unsignedcharkey);
linkinsert(linkt,unsignedcharkey);
linkdelete(linkt,unsignedcharkey);
voidprint_tree(linkt);
#endif
|
C++ Code
|
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
|
|
/*************************************************************************
>FileName:binarysearchtree.c
>Author:Simba
>Mail:dameng34@163.com
>CreatedTime:Sat29Dec201206:08:08PMCST
************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include"binarysearchtree.h"
staticlinkmake_node(unsignedcharitem)
{
linkp=malloc(sizeof(*p));
p->item=item;
p->left=p->right=NULL;
returnp;
}
staticvoidfree_node(linkp)
{
free(p);
}
linksearch(linkt,unsignedcharkey)
{
if(!t)
returnNULL;
if(t->item>key)
returnsearch(t->left,key);
if(t->item<key)
returnsearch(t->right,key);
/*if(t->item==key)*/
returnt;
}
linkinsert(linkt,unsignedcharkey)
{
if(!t)
returnmake_node(key);
if(t->item>key)/*inserttoleftsubtree*/
t->left=insert(t->left,key);
else/*if(t->item<=key),inserttorightsubtree*/
t->right=insert(t->right,key);
returnt;
}
linkdelete(linkt,unsignedcharkey)
{
linkp;
if(!t)
returnNULL;
if(t->item>key)/*deletefromleftsubtree*/
t->left=delete(t->left,key);
elseif(t->item<key)/*deletefromrightsubtree*/
t->right=delete(t->right,key);
else/*if(t->item==key)*/
{
if(t->left==NULL&&t->right==NULL)
{
/*iftisaleafnode*/
free_node(t);
t=NULL;
}
elseif(t->left)/*ifthasleftsubtree*/
{
/*replacetwiththerightmostnodeinleftsubtree*/
for(p=t->left;p->right;p=p->right);
t->item=p->item;/*将左子树下最靠右的节点值赋予想要删除的节点*/
t->left=delete(t->left,t->item);
}
else/*ifthasrightsubtree*/
{
/*replacetwiththeleftmostnodeinrightsubtree*/
for(p=t->right;p->left;p=p->left);
t->item=p->item;
t->right=delete(t->right,t->item);
}
}
returnt;
}
voidprint_tree(linkt)
{
if(t)
{
printf("(");
printf("%d",t->item);
print_tree(t->left);
print_tree(t->right);
printf(")");
}
else
printf("()");
}
|
C++ Code
|
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
|
|
/*************************************************************************
>FileName:main2.c
>Author:Simba
>Mail:dameng34@163.com
>CreatedTime:Sat29Dec201206:22:57PMCST
************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include"binarysearchtree.h"
#defineRANGE100
#defineN6
voidprint_item(linkp)
{
printf("%d",p->item);
}
intmain(void)
{
inti,key;
linkroot=NULL;
srand(time(NULL));
for(i=0;i<N;i++)
{
root=insert(root,rand()%RANGE);/*第一次循环root从NULL变成根节点值，接下去
的循环虽然迭代root，但在插入节点过程中root的值始终不变*/
printf("root=0x%x\n",(unsignedint)root);
}
printf("\t\\tree");
print_tree(root);
printf("\n\n");
while(root)
{
key=rand()%RANGE;
if(search(root,key))
{
printf("delete%dintree\n",key);
root=delete(root,key);/*root虽然迭代，但返回的仍是先前的值，即根节点的值保持不变
直到全部节点被删除，root变成NULL即0x0*/
printf("root=0x%x\n",(unsignedint)root);
printf("\t\\tree");
print_tree(root);/*传递给函数的一直是根节点的值，直到树清空，root变成NULL*/
printf("\n\n");
}
}
return0;
}
|
输出为：
如果我们使用了The Tree Preprocessor，可以将以括号展示的排序二叉树转换成树形展示，如下图
以前此工具可以在http://www.essex.ac.uk/linguistics/clmt/latex4ling/trees/tree/下载，现已找不到链接，我将其上传到csdn，需要的可以去下载。
http://download.csdn.net/detail/simba888888/5334093
最后提一下，我们希望构建出来的二叉排序树是比较平衡的，即其深度与完全二叉树相同，那么查找的时间复杂度研究度O(logn)，近似于折半查找，
但如果出现构造的树严重不平衡，如完全是左斜树或者右斜树，那么查找时间复杂度为O(n)，近似于顺序查找。那如何让二叉排序树平衡呢？
事实上还有一种平衡二叉树（AVL树），也是一种二叉排序树，其中每个结点的左子树和右子树的高度差至多等于1。
补充：delete() 在《data structure and algorithm analysis in c》 中的实现，个人觉得比较清晰，也挺好理解的，如下：
C++ Code
|
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
|
|
linkFindMin(linkT)
{
if(T!=NULL)
while(T->left!=NULL)
T=T->left;
returnT;
}
linkdelete(unsignedcharX,linkT)
{
linktmp;
if(T==NULL)
{
printf("Treeisempty!\n");
returnNULL;
}
if(X<T->key)//goleft
T->left=delete(X,T->left);
elseif(X>T->key)//goright
T->right=delete(X,T->right);
/*foundelemtobedeleted*/
elseif(T->left&&T->right)//havetwochildren
{
//replacewithsmallestinrightsubtree
tmp=FindMin(T->right);
T->key=tmp->key;
T->right=delete(T->key,T->right);
}
else//oneorzerochildren
{
tmp=T;
if(T->left==NULL)
T=T->right;
elseif(T->right==NULL)
T=T->left;
free(tmp);
}
returnT;
}
|
参考：
《大话数据结构》
《linux c 编程一站式学习》
《Data Structures》
| 
转播
