二叉查找树
二叉查找树（Binery Search Tree），要么是一颗空树，要么是具有以下性质的二叉树：
（1） 要是结点的左子树不为空，则左子树的所有结点的值小于该结点的值
（2） 要是结点的右子树不为空，则右子树的所有结点的值大于该结点的值
（3） 该结点的左右子树也是二叉查找树
二叉查找树通常用二叉链表存储结点。中序遍历二叉查找树可以得到关键字有序的序列，一个无序的序列可以通过构造一棵二叉查找树，再中序遍历得到一棵有序的链表。每次插入的位置都是叶子结点，插入时不用移动其他结点。搜索、插入、删除结点的复杂度为树高，即O(logn)(数列有序，退化成线性表，此时的复杂度为O(n))。
查找
二叉查找树T查找关键字val的过程为：
- 若T为空树，查找失败，否则：
- 若val 等于T的关键字，查找成功，返回。否则
- 若val 小于T的关键字，继续查找T的左子树。否则
- 查找T的右子树。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
bool SearchBST(BiTree T, int val, BiTree f, BiTree &p)
{ if(!T)
{
p = f;
return false;
}
else if(val == T->data)
{
p = T;
return true;
}
else if(val < T->data)
SearchBST(T->left, val, T, p);
else
SearchBST(T->right, val, T, p);
} |
插入
二叉查找树T插入关键字为val的结点s过程为：
如果在二叉查找树T中没有找到关键字为val的结点（查找过程返回的结点为p）：
- 如果p为空，则s直接赋给p
- 如果val小于p的关键字，插入到p的左子树上
- 如果val大于p的关键字，插入到p的右子树上
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
bool InsertBST(BiTree &T, int val)
{ BiTree p = NULL;
if(!SearchBST(T, val, NULL, p))
{
BiTree node = new BiTNode;
node->data = val;
node->left = node->right = NULL;
if(!p)
T = node;
else if(val < p->data)
p->left = node;
else
p->right = node;
return true;
}
return false;
} |
删除
删除结点为p
- 若p为叶子结点，直接删掉
- 若p只有左子树，则把自己替换成左子树
- 若p只有右子树，则把自己替换成右子树
- 若左右子树都有，则把自己的关键字替换成左子树中最靠右的关键字，同时干掉最右边的关键字
|
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
|
bool Delete(BiTree &T)
{ if(!T->left && !T->right)
{
delete T;
T = NULL;
}
else if(!T->left)
{
BiTree p = T;
T = T->right;
delete p;
p = NULL;
}
else if(!T->right)
{
BiTree p = T;
T = T->left;
delete p;
p = NULL;
}
else
{
BiTree p = T, q = T->left;
while(q->right)
{
p = q;
q = q->right;
}
if(T == p)
{
T->data = q->data;
T->left = q->left;
delete q;
q = NULL;
}
else
{
T->data = q->data;
p->right = NULL;
delete q;
q = NULL;
}
}
return true;
}bool DeleteBST(BiTree &T, int val)
{ if(!T)
return false;
else
{
if(val == T->data)
return Delete(T);
else if(val < T->data)
return DeleteBST(T->left, val);
else
return DeleteBST(T->right, val);
}
} |
完整参考代码
本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/p/3428307.html，如需转载请自行联系原作者