else
f—rchild=s;
returnt;
}
bstnode*creatord（）
{bstnode*t,*s;
intkey;
t=Null;
scanf（“%d”,&key）;
while（key!
=0）
{s=malloc（sizeof（bitree））;s—key=key;
s—lchild=Null;s—rchild=Null;
scanf（“%d”,&data）;s—other=data;t=insertbst（t,s）;
scanf（“%d”,&key）;
}
returnt;
五、思考与提高
1.用其它的查找方法完成该算法。
2.比较各种算法的时间及空间复杂度。
六、完整参考程序
1.折半查找
#include
#include
#defineMAX30//定义有序查找表的最大长度
typedefstruct{
charelem[MAX];//有序查找表
intlength;//length指示当前有序查找表的长度
}SSTable;
voidinitial（SSTable&）;//初始化有序查找表
intsearch（SSTable,int）;//在有序查找表中查找元素
voidprint（SSTable）;//显示有序查找表中所有元素
voidmain（）
{SSTableST;//ST为一有序查找表
intch,loc,flag=1;
charj;
initial（ST）;//初始化有序查找表
while（flag）
{printf（"请选择：
\n"）;
printf（"1.显示所有元素\n"）;
printf（"2.查找一个元素\n"）;
printf（"3.退出\n"）;
scanf（"%c",&j）;
switch（j）
{case'1':
print（ST）;break;//显示所有元素
case2:
{printf（"请输入要查找的元素：
"）;
scanf（"%d",&ch）;//输入要查找的元素的关键字
loc=search（ST,ch）;//查找if（loc!
=0）printf（"该元素所在位置是：
%d\n",loc）;//显示该元素位
elseprintf（"%d不存在!
\n",ch）;〃当前元素不存在
break;
}
default:
flag=0;
}
printf（"程序运行结束!
按任意键退出!
\n"）;
}
voidinitial（SSTable&v）
{//初始化有序查找表
inti;
printf（"请输入静态表的元素个数：
"）;//输入有序查找表初始化时的长度scanf（"%d",&v.length）;
printf（"请从小到大输入%d个元素（整形数）：
\n",v.length）;
getchar（）;
for（i=1;i<=v.length;i++）scanf（"%d",&v.elem[i]）;//从小到大输入有序查找表
的各元素
}
intsearch（SSTablev,intch）
{//在有序查找表中查找ch的位置，成功返回其位置，失败返回0intlow,high,mid;
low=1;high=v.length;//置区间初值
while（low<=high）
{mid=（low+high）/2;
if（v.elem[mid]==ch）returnmid;//找到待查元素
elseif（v.elem[mid]>ch）high=mid-1;//继续在前半区间进行查找
elselow=mid+1;
//继续在后半区间进行查找
}
return0;//找不到时，i为0
}
voidprint（SSTablev）//显示当前有序查找表所有元素
{inti;
for（i=1;i<=v.length;i++）printf（"%d",v.elem[i]）;
printf（"\n"）;
}
2.二叉排序树的建立与查找
#include
#include
#include
#include
enumBOOL{False,True};
typedefstructBiTNode//定义二叉树节点结构
{chardata;//为了方便，数据域只有关键字一项
structBiTNode*lchild,*rchild;//左右孩子指针域
}BiTNode,*BiTree;
BOOLSearchBST（BiTree,char,BiTree,BiTree&）;//在二叉排序树中查找元素
BOOLInsertBST（BiTree&,char）;//在二叉排序树中插入元素
//删除二叉排序树的根结点
//中序遍历二叉排序树，即从小到大显示
BOOLDeleteBST（BiTree&,char）;//在二叉排序树中删除元素
voidDelete（BiTree&）;
voidInorderBST（BiTree）;各元素
voidmain（）
{BiTreeT,p;
charch,keyword,j='y';
BOOLtemp;
T=NULL;
while（j!
='n'）
{printf（"1.display\n"）;
printf（"2.search\n"）;
printf（"3.insert\n"）;
printf（"4.delete\n"）;
printf（"5.exit\n"）;
scanf（"%c",&ch）;//输入操作选项
switch（ch）
{case'1':
if（!
T）printf（"TheBSThasnoelem.\n"）;
else{InorderBST（T）;printf（"\n"）;}
break;
case'2':
printf（"Inputthekeywordofelemtobesearched（achar）:
"）;
scanf（"%c",&keyword）;//输入要查找元素的关键字
temp=SearchBST（T,keyword,NULL,p）;
if（!
temp）printf（"%cisn'texisted!
\n",keyword）;//没有找到
elseprintf（"%chasbeenfound!
\n",keyword）;//成功找到
break;
case'3':
printf（"Inputthekeywordofelemtobeinserted（achar）:
"）;
scanf（"%c",&keyword）;//输入要插入元素的关键字
temp=InsertBST（T,keyword）;
if（!
temp）printf（"%chasbeenexisted!
\n",keyword）;//该元素已经存在
elseprintf（"Sucesstoinert%c!
\n",keyword）;//成功插入
break;
case'4':
printf（"Inputthekeywordofelemtobedeleted（achar）:
"）;
scanf（"%c",&keyword）;//输入要删除元素的关键字temp=DeleteBST（T,keyword）;
if（!
temp）printf（"%cisn'texisted!
\n",keyword）;//该元素不存在
elseprintf（"Sucesstodelete%c\n",keyword）;//成功删除
break;
default:
j='n';
}
}
printf（"Theprogramisover!
\nPressanykeytoshutoffthewindow!
\n"）;getchar（）;getchar（）;
}
voidInorderBST（BiTreeT）
{//以中序方式遍历二叉排序树T,即从小到大显示二叉排序树的所有元素
if（T->lchild）InorderBST（T->lchild）;
printf（"%2c",T->data）;
if（T->rchild）InorderBST（T->rchild）;
BOOLSearchBST（BiTreeT,charkey,BiTreef,BiTree&p）
{//在根指针T所指二叉排序树中递归的查找其关键字等于key的元素，若查
找成功
〃则指针p指向该数据元素，并返回True,否则指针指向查找路径上访问的最后一
〃个结点并返回False,指针f指向T的双亲，其初始调用值为NULL
BOOLtmp1,tmp2;
tmp1=tmp2=False;
if（!
T）{p=f;returnFalse;}//查找不成功
elseif（key==T->data）{p=T;returnTrue;}//查找成功
elseif（keydata）tmp1=SearchBST（T->lchild,key,T,p）;/在/左子树中继续查找
elsetmp2=SearchBST（T->rchild,key,T,p）;/在/右子树中继续查找
if（tmp1||tmp2）returnTrue;//若在子树中查找成功，向上级返回True
elsereturnFalse;//否则返回False
}
BOOLInsertBST（BiTree&T,chare）
{//当二叉排序树T中不存在元素e时，插入e并返回True,否则返回False
BiTreep,s;
if（!
SearchBST（T,e,NULL,p））//查找不成功{s=（BiTree）malloc（sizeof（BiTNode））;
s->data=e;
s->lchild=s->rchild=NULL;
if（!
p）T=s;//被插结点*s为新的根结点
elseif（edata）p->lchild=s;//被插结点*s为左孩子
elsep->rchild=s;//被插结点*s为右孩子
returnTrue;//成功插入
}
elsereturnFalse;/树/中已存在关键字为e的数据元素
}
BOOLDeleteBST（BiTree&T,charkey）
{//若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点
〃并返回True否则返回False
BOOLtmp1,tmp2;
tmp1=tmp2=False;
if（!
T）returnFalse;//不存在关键字等于key的数据元素
else
{if（key==T->data）{Delete（T）;returnTrue;}
//找到关键字等于key的数据元素并删除它
elseif（keydata）tmp1=DeleteBST（T->lchild,key）;//继续在左子树中
删除
elsetmp2=DeleteBST（T->rchild,key）;//继续在右子树中删除
if（tmp1||tmp2）returnTrue;//在子树中删除成功，返回True
elsereturnFalse;//不存在该元素
}
}
voidDelete（BiTree&p）
{//在二叉排序树中删除结点P,并重接它的左或右子树
BiTrees,q;
if（!
P->rchild）//右子树空，只需重接它的左子树
{q=P;
P=P->lchild;
free（q）;
elseif（!
p->lchild）//左子树空，只需重接它的右子树
{q=p;
p=p->rchild;
free（q）;
}
else//左右子树均不空
{q=p;
s=p->lchild;
while（s->rchild）
{q=s;s=s->rchild;}//转左，然后向右走到尽头p->data=s->data;//s指向被删结点的“前驱”if（q!
=p）q->rchild=s->rchild;//重接*q的右子树elseq->lchild=s->lchild;//重接*q的左子树
free（s）;
}
升级会员 