9.2动态查找表一、二叉排序树（二叉查找树）1．定义2．查找算法3．插入算法4．删除算法5．查找性能的分析（1）
若它的左子树不空，则左子树上所有结点的值均小于根结点的值；1．定义：二叉排序树或者是一棵空树；或者是具
有如下特性的二叉树：（3）它的左、右子树也都分别是二叉排序树。（2）若它的右子树不空，则右子树上所有结点的值均大于
根结点的值；例如:是二叉排序树。50308020901085403525238866不通
常，取二叉链表作为二叉排序树的存储结构typedefstructBiTNode{structBiT
Nodelchild,rchild;}BiTNode,BiTree;TElemTypedata
;typedefstruct{keyTypekey;……}
ElemType;2．二叉排序树的查找算法：（1）若给定值等于根结点的关键字，则查找成功；（2）若给定值小于
根结点的关键字，则继续在左子树上进行查找；（3）若给定值大于根结点的关键字，则继续在右子树上进行查找。
若二叉排序树为空，则查找不成功；否则，50308020908540358832例如:二叉排序树查找关键字
==50,505035,503040355090,50809095,算法描述如下：BiT
reeSearchBST(BiTreeT,KeyTypekey)if((!T)||(EQ(key,T-
>data.key))returnT;elseif(LT(key,T->data.key))
returnSearchBST(T->lchild,key);elsereturnSearchBST(T->
rchild,key);}二叉排序树是一种动态树表，其特点是，树的结构通常不是一次生成的，而是在查找过程中，当树
中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最
后一个结点的左孩子或右孩子。为了便于在查找不成功时返回插入位置，可将查找算法进行修改。算法描述如下：StatusS
earchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p)
{if(!T){p=f;returnFALSE;}//查找不成功elsei
f(EQ(key,T->data.key)){p=T;returnTRUE;}/
/查找成功elseif(LT(key,T->data.key))returnSearchBS
T(T->lchild,key,T,p);elsereturnSearchBST(T->rchild,ke
y,T,p);}30201040352523fT设key=48fTfT22pf
TfTTTTfffp根据动态查找表的定义，“插入”操作在查找不成功时才进行；3．二叉排序树的插入算法若二叉
排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。StatusIns
ertBST(BiTree&T,ElemTyp
ee){if(!SearchBST(T,e.key,NULL,p)){
}elsereturnFALSE;}//InsertBST…
…s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->l
child=s->rchild=NULL;if(!p)T=s;//插入s为新的根结点
elseif(LT(e.key,p->data.key))p->lchild=s;
//插入s为p的左孩子elsep->rchild=s;//插入s为p的右孩子
returnTRUE;//插入成功（1）被删除的结点是叶子；（2）被删除的结点只有左子树或者只有右
子树；（3）被删除的结点既有左子树，也有右子树。4．二叉排序树的删除算法可分三种情况讨论：删除在查找成
功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。50308020908540358
832（1）被删除的结点是叶子结点例如:被删关键字=2088其双亲结点中相应指针域的值改为“空”503080
20908540358832（2）被删除的结点只有左子树或者只有右子树其双亲结点的相应指针域的值改
为“指向被删除结点的左子树或右子树”。被删关键字=408050308020908540358832
（3）被删除的结点既有左子树，也有右子树4040以其前驱替代之，然后再删除该前驱结点被删结点前驱结点被删关键字=50
StatusDeleteBST(BiTree&T,KeyTypekey){if(!T)returnF
ALSE;else{}}//DeleteBST算法描述如下：
……if(EQ(key,T->data.key)) //找到关键字等于key的数据元素elseif
(LT(key,T->data.key))else{Delete(T);returnTRUE;
}returnDeleteBST(T->lchild,key);//继续在左子树
中进行查找returnDeleteBST(T->rchild,key);//继续在右子树中进行查找void
Delete(BiTree&p){//从二叉排序树中删除结点p，//并重接它的左子树或右子树
if(!p->rchild){}elseif(!p->lchild){
}else{}}//Delete其中删除操作过程如下所描
述：………………//右子树为空树则只需重接它的左子树q=p;p=p->lchild;free(
q);pp//左子树为空树只需重接它的右子树q=p;p=p->rchild;free(q);ppq
=p;s=p->lchild;while(!s->rchild){q=s;s=s->rchild;
}//s指向被删结点的前驱//左右子树均不空p->data=s->
data;if(q!=p)q->rchild=s->lchild;elseq->
lchild=s->lchild;//重接q的左子树free(s);
pqs5．查找性能的分析对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的ASL值，显然，由值相
同的n个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大。由关键字序列3，1，2，5，4
构造而得的二叉排序树，由关键字序列1，2，3，4，5构造而得的二叉排序树，例如：2134535412A
SL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.2含有n个结点的二叉排序
树的平均查找长度与树形态有关。最坏的情况：树的深度为n，构成单支树，其平均查找长度为（n+1)/2。最好的情况：二叉排序树的形态与折半查找的判定树相同，其平均查找长度和log2n成正比。作业：将关键字序列25，73，191，325，198中各关键字依次插入到下面的二叉排序树中，以构成一棵新的二叉排序树，请画出二叉排序树的最后结果。按哪种顺序遍历二叉排序树可得到一个关键字非递减的有序序列？这个有序序列是什么？8070200预习：9.3节 |
|
