二叉排序树

二叉排序树

二叉排序树(Binary Sort Tree)又称二叉查找树

它或是一棵空树,或者是具有下列性质的二叉树。

一些基本性质

  1. 若其左子树不空,则左子树上所有节点的值均小于它的根结构的值
  2. 若其右子树不空,则右子树上所有节点的值均大于它的根节点的值
  3. 它的左、右子树也分别为二叉树

构造二叉排序树的目的主要在于提高查找和插入删除关键字的速度。

然而查找的时间复杂度十分不稳定,最坏的情况是O(n),因此更好的办法是构造平衡二叉树(AVL树)(大概下篇文章就是AVL树?)。

搜索节点

实现的方式有很多种,这里是使用的递归方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//递归查找二叉排序树T中是否存在key
//指针f指向T的双亲,其初始调用值为NULL
//找到了返回NULL,否则返回符合插入条件的地址
node *SearchBST(node *T, int key, node *f)
{
if (!T)
return f;
if (key == T->data)
return NULL;
else if (key < T->data)
return SearchBST(T->lchild, key, T);
else
return SearchBST(T->rchild, key, T);
}

插入节点

先判断一下是不是空树,是空树的话直接插入,否则:

判断一下是不是树中已经存在值为key的节点,

如果已经存在,直接返回,否则进行插入操作。

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
//当二叉排序树中不存在关键字等于key的数据元素时插入
node *InsertBST(node *T, int key)
{
node *p, *t, *c;
if (!T) //空树
{
T = (node *)malloc(sizeof(node));
T->data = key;
T->lchild = T->rchild = NULL;
return T;
}
t = T; //指针t指向当前节点
p = SearchBST(T, key, NULL);
if (p)
{
c = (node *)malloc(sizeof(node));
c->data = key;
c->lchild = c->rchild = NULL;
if (p->data < key)
p->rchild = c;
else
p->lchild = c;
}
return T;
}

删除节点

删除节点需要仔细分析一下:

首先如果是空树,自然直接返回。

接下来应该是在二叉树中寻找键值等于key的节点

如果该节点左右子树至少有一个不为空,那么只需要将该节点的右/左子树接上就好;

反之如果左右孩子都不为空:

要取到中序遍历中该节点的直接前驱(直接后驱也是OK的),然后进行进一步的判断进行删除操作。

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
int DeleteNode(node *T,int key)
{
if(!T)
return 0;
else
{
node *p = T;
node *f = NULL;
node *t;
while((p != NULL) && (p->data != key))
{
f = p;
if(p->data < key)
p = p->rchild;
else
p = p->lchild;
}
//左、右孩子至少有一个为空
if(p->lchild==NULL||p->rchild==NULL)
{
if(f->lchild == p)
{
if(!p->lchild)
f->lchild = p->rchild;
else
f->lchild = p->lchild;
}
else
{
if(!p->lchild)
f->rchild = p->rchild;
else
f->rchild = p->lchild;
}
free(p);
}
//左、右孩子均不为空
else
{
f = p;
t = p->lchild; //转左
while(t->rchild)//一直往右到底,取到中序遍历的直接前驱
{
f = t;
t = t->rchild;
}
p->data = t->data;
if(f!=p)
f->rchild = t->lchild;
else
f->lchild = t->lchild;
free(t);
}
}
return 0;
}

主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
int main(void)
{
node *T = NULL;
int a[11] = {62, 88, 58, 47, 51, 35, 29, 37, 36, 49, 56};
for (int i = 0; i < 11; i++)
{
T = InsertBST(T, a[i]);
}
PreOrderTraverse(T);
printf("\n");
DeleteNode(T,47);
PreOrderTraverse(T);
}

懒得画图了: ( 下面是个极其粗糙的演示:

1
2
3
4
5
6
7
8
9
10
11
12
二叉树原始形态: 删除节点之后:
62 62
/ \ / \
58 88 58 88
/ /
47 37
/ \ / \
35 51 35 51
/ \ / \ / \ / \
29 37 49 56 29 36 49 56
/
36