else{p->data=q->data；s->rchild=q->lchild；free（q）；} }
}//Delete
39．给出折半查找的递归算法，并给出算法时间复杂度性分析。 int BinSrch（rectype r[ ]，int k，low，high）
//在长为n的有序表中查找关键字k，若查找成功，返回k所在位置，查找失败返回0。
{if（low≤high） //low和high分别是有序表的下界和上界 {mid=（low+high）/2；
if（r[mid].key==k）return （mid）；
else if（r[mid].key>k）return （BinSrch（r,k，mid+1，high））; else return （BinSrch（r,k，low，mid-1））; }
else return （0）；//查找失败。 }//算法结束
算法时间复杂度为O（logn）。
40．写出从哈希表中删除关键字为K的一个记录的算法，设哈希函数为H，解决冲突的方法为链地址法。
[题目分析] 用链地址法解决冲突的哈希表是一个指针数组，数组分量均是指向单链表的指针，（第i个）单链表结点有两个域，一个是哈希地址为i的关键字，另一个是指向同义词结点的指针。删除算法与单链表上删除算法类似。
typedef struct node {keytype key；
struct node *next； }HSNode；*HSList
typedef struct node *HLK；
void Delete（HLK HT[]，keytype K）
//用链地址法解决冲突，从哈希表中删去关键字为K的记录 {i=H（K）；//用哈希函数确定关键字K的哈希地址
if（HT[i]==null）{printf（“无被删除记录\\n”）；exit（0）；}
HLK p,q; p=H[i]；q=p； //p指向当前记录（关键字），q是p的前驱 while（p && p->key！=k）{q=p；p=p->next；}
if（p==null）{printf（“无被删除记录”）；exit(0); } if（q==H[i]） //被删除关键字是链表中第一个结点 { HT[i]=HT[i].next；free（p）；} else{ q->next=p->next；free（p）；} }//结束Delete
41．设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。
（1）递归算法
void DecPrint(BSTree t）
//递减序输出二叉排序树t中所有左子树为空右子树非空的结点数据域的值。
{if（t）
{DecPrint(t->rchild)；
if（!t->lchild && t->rchild）printf(t->data)； DecPrint(t->lchild）； }
}//DecPrint （2）非递归算法
void DecPrint(BSTree t）
// 递减序输出二叉排序树t中所有左子女为空右子女非空的结点的值 {BSTree S[]；//S是二叉排序树结点指针的栈，容量足够大 int top=0；
while（t || top>0） {while（t）
{S[++top]=t；t=t->rchild ；} //沿右分枝向下 if（top>0） {t=S[top--]；
if（!t->lchild && t->rchild）printf(t->data)； t=t->lchild； // 去左分枝
}//if
}//while }//算法结束
42．已知二叉排序树采用二叉链表存储结构，根结点的指针为T，链结点的结构为（lchild,data,rchild），其中lchild、rchild分别指向该结点左、右孩子的指针（当孩子结点不存在时，相应指针域为null）,data域存放结点的数据信息。请写出递归算法，从小到大输出二叉排序树中所有数据值>=x的结点的数据。要求先找到第一个满足条件的结点后再依次输出其他满足条件的结点。
[题目分析]利用二叉排序树的性质，如果根结点的值>=x,则除左分枝中可能有 // 中序输出以t为根的二叉排序树的结点 {if（t）{Print（t->lchild）； printf（t->data）； Print（t->rchild）； } } void PrintAllx(BSTree bst，datatype x） //在二叉排序树bst中，查找值≥x的结点并输出 {p=bst； if（p） {while（p && p->data bst=p; //bst所指结点是值≥x的结点的树的根 if（p） {f=p; p=p->lchild ；//找第一个值 while（p && p->data≥x）//沿左分枝向下，找第一个值 if(p) f->lchild=null; //双亲与找到的第一个值 Print(bst)；//输出以bst为根的子树 }//while }//内层if（p） }//第一层if（p） }//PrintAllx