二叉排序树

说在前面的话

话说,平时自己也没怎么熬过夜,现在已经凌晨了,不过我还是不想睡,此刻想到最多的词汇就是不够、不够、不够,唉:-(,我也想多学会儿啊,只是总感觉什么都不够,时间不够,精力也不够,都说不要在晚上给自己定任何目标,可毕竟一个人只有在晚上夜深人静的时候,大脑才是最清醒的,更加清楚自己想要什么。期末考试临近,明天英语六级考试,最近又得忙着搞Java课程设计计算机网络课程设计,曾经定下的目标又沦为空话,一次次地拖延,一次次地荒废,到现在依旧是什么都不会,终离目标越来越远。今年暑假不会待在学校培训学习了(一想起去年暑假自信满满地留在学校培训,却被自己荒废掉…),而是有些无奈地要去打暑假工,暑假过后,彼此之间的实力差距会更大,想到这里心里就不是个滋味,机遇摆在你面前,可是你却抓不住。这学期还剩两周时间,而且已经没课了,我近期的目标即是希望自己能够抓紧这段时间,保持一个平稳的心,继续前进,尽自己最大可能去做更多需要做的事情,只希望能够给自己的心灵一丝慰藉,让我看到自己从未放弃挣扎。而在这其中呢,记录技术学习博客就是很大的一方面。

今天呢,就在这里挖个坑,尽快将树表查找知识完善,晚安!

早上起来之后开始补坑…

关于本节树表内容,将涉及到几类特殊的二叉树形式,包括二叉排序树、平衡二叉树、B-树和B+树,线性表的查找更适用于静态查找表,而树表的查找更适用于动态查找表

二叉排序树(二叉查找树)

定义:

二叉排序树或者是空树,或者是满足下列性质的二叉树:

  1. 若其左子树非空,则左子树上所有结点的值均小于根结点的值
  2. 若其右子树非空,则右子树上所有结点的值均大于根结点的值
  3. 其左右子树又各是一棵二叉排序树

中序遍历一棵二叉排序树可以得到一个结点值递增的有序序列。

在对二叉树进行操作的时候,使用二叉链表作为存储结构,下面给出了二叉排序树的二叉链表存储表示

1
2
3
4
5
6
7
8
9
typedef struct	{
Keytype key; // 关键字项
InfoType otherinfo; //其他数据项
}ElemType; //每个结点的数据域的类型

typedef struct BSTNode {
ElemType data; //每个结点的数据域包括关键字项和其他数据项
struct BSTNode *lchild,*rchild; //左右孩子指针
}BSTNode,*BSTree;

查找算法:

1
2
3
4
5
6
7
8
9
10
BSTree SearchBST(BSTree T,KeyType key)	{
//在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素
//若查找成功,则返回指向该数据元素结点的指针,否则返回空指针
if ((!T)||key==T->data.key)
return T; //查找结束
else if (key<T->data.key)
return SearchBST(T->lchild,key); //在左子树中继续查找
else
return SearchBST(T->rchild,key); //在右子树中继续查找
}
  • 在二叉排序树上查找其关键字等于给定值的过程,恰好是走了一条从根结点到该结点的路径的过程,和给定值比较的关键字个数等于路径长度加1(或结点所在层次数)。
  • 对于需要经常进行插入、删除和查找运算的表,采用二叉排序树比较好。

插入算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void InsertBST(BSTree &T,ElemType e)		{
//当二叉排序树T中不存在关键字等于e.key的数据元素时,则插入该元素
if (!T) {
//T为空,找到插入位置,递归结束
BSTree S=new BSTNode; //生成新结点*S
S->data=e; //数据域置为e
S->lchild=S->rchild=NULL; //作为叶子结点
T=S; //把新结点*S链接到已找到的插入位置
}
else if (e.key<T->data.key)
InsertBST(T->lchild,e); //将*S插入左子树
else if (e.key>T->data.key)
InsertBST(T->rchild,e); //将*S插入右子树
}

生成算法:

1
2
3
4
5
6
7
8
9
void CreateBST(BSTree &T)	{
//依次读入一个关键字为key的结点,将此结点插入二叉排序树T中
T=NULL; //将二叉排序树T初始化为空树
cin>>e;
while (e.key!=ENDFLAG) { //ENDFLAG为自定义常量,作为输入结束标志
InsertBST(T,e); //调用插入算法,将此结点插入到二叉排序树T中
cin>>e.key;
}
}

删除操作:

被删除的结点可能是二叉排序树中的任何结点,删除结点后,要根据其位置不同修改其双亲结点及相关结点的指针,以保持二叉排序树的特性。

删除的结点有以下几种情况:

  1. 被删除的结点是叶子,则将其双亲结点中相应指针域的值改为“空”。
  2. 被删除的结点只有左子树或者只有右子树,则将其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。
  3. 被删除的结点既有左子树,也有右子树,则以其前驱替代之,然后再删除该前驱结点。

删除算法:

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
void DeleteBST(BSTree &T,KeyType key)	{
//从二叉排序树T中删除关键字等于key的结点
p=T,f=NULL; //初始化
/*------------下面的while循环从根开始查找关键字等于key的结点*P----------*/
while (p) {
if (p->data.key==key) break; //找到关键字等于key的结点*p,结束循环
f=p; //*f为*p的双亲结点
if (p->data.key>key) p=p->lchild; //在*p的左子树中继续查找
else p=p->rchild; //在*p的右子树上继续查找
}
if (!p) return; //如果找不到被删结点则返回
/*-----------考虑实现p所指子树内部的处理:*P左右子树均不空、无右子树、无左子树-------*/
q=p; //将被删结点p地址保存在q中
//被删结点左右子树都不空
if ((p->lchild)&&(p->rchild)) {
s=p->lchild;
while (s->rchild) {
//在*p的左子树中继续查找其前驱结点,即最右下结点
q=s;
s=s->rchild;
}
p->data=s->data; //s指向被删结点的前驱
if (q!=p) //用于判断程序是否执行了上面的while循环
q->rchild=s->lchild; //程序执行了while循环,需要重接*q的右子树
else
q->lchild=s->lchild; //未执行while循环,需要重接*p的左子树
delete s; //删除前驱结点s
return;
}
//被删结点*p无右子树
else if (!p->rchild)
p=p->lchild; //重接左子树
//被删结点*p无左子树
else if (!p->lchild)
p=p->rchilid; //重接右子树
/*--------------将p所指的子树挂接到期双亲结点*f相应的位置--------------*/
if (!f) T=p; //被删结点为根结点
else if (q==f->lchild) f->lchild=p; //挂接到*f的左子树位置
else f->rchild=p; //挂接到*f的右子树位置
delete q;
}
-------------The End-------------