{while（t）
{S[++top]=t；t=t->rchild ；} //沿右分枝向下 if（top>0） {t=S[top--]；
if（!t->lchild && t->rchild）printf(t->data：4)； t=t->lchild； // 去左分枝
}//if
}//while }//算法结束
19．[题目分析]这是一个在单链表中查找结点，在结点内查找给定值的过程，先定义存储结构：
typedef struct node
{int A[m]； //每个结点内含有m个正整数，本例中m为5 struct node *next；//指向下一结点的指针 }LNode，*LinkList； typedef struct
{int j；// 正整数在结点内的序号 struct node *s；// 结点的指针 }rcd;
rcd *LSearch(LinkList head,int n)
//在链表中查找正整数n，若查找成功，返回该结点指针及n在结点中的序号； //否则返回空指针表示失败。 {rcd *R;
P=head->next；// 假定链表带头结点，P指向链表第一元素结点 found=0；
while（P && !found） {for(i=0;i if(P->A[i]==n) found=1 //查找成功 P=P->next; //下一结点 } if（P==null）return （null）； else {R.j=i; R.s=P; return （R）；} }//LSearch 20．int Search（rectype R[]，int n,K） // 在具有n个元素的有序表R中，顺序查找值为K的结点，查找成功返回其位置， //否则返回-1表示失败 {i=0； while（i {if（R[i]==K） return （i）； else if（R[i]>K） return （-1）； i++; }//while return （-1）； }//结束search 在等概率情况下，则查找成功的平均查找长度为（n+1）/2，查找失败的平均查找长度为（n+2）/2（失败位置除小于每一个，还存在大于最后一个）。若查找成功和不成功的概率也相等，则查找成功时和关键字比较的个数的期望值约为(n+1)/4。 21．[题目分析]中序遍历二叉树，在“访问根结点”处判断结点值是否≥x，如是则输出，并记住第一个≥x值结点的指针。这里给出另一个算法，利用二叉排序树的性质，如果根结点的值>=x,则除左分枝中可能有 void Print（BSTree t） // 中序输出以t为根的二叉排序树的结点 {if（t）{Print（t->lchild）； printf（t->data：4）； Print（t->rchild）； } } void PrintAllx(BSTree bst，datatype x） //在二叉排序树bst中，查找值≥x的结点并输出 {p=bst； if（p） {while（p && p->data {f=p; p=p->lchild ；//找第一个值 while（p && p->data≥x）//沿左分枝向下，找第一个值 if(p) f->lchild=null; //双亲与找到的第一个值 Print(bst)；//输出以bst为根的子树 }//while }//内层if（p） }//第一层if（p） }//PrintAllx 22．[题目分析] 因为T是二叉排序树，则可利用二叉排序树的性质，从根往下查找结点*x。若T的左子树为空，则其中序序号为1，否则为T->lchild->size+1。设T的中序序号为r，其左子女p的中序序号和右子女q的中序序号分别为r-p->rchild->size-1和r+q->lchild->size+1。 int Rank（tree T，node *x） // 在二叉排序树T上，求结点x的中序序号 {if（T->lchild）r=T->lchild->size+1；else r=1；//根结点的中序序号 while（T） if（T->key>x->key）//到左子树去查找 {T=T->lchild； if（T）{if（T->rchild）r=r-T->rchild->size-1；else r=r-1；} } else if（T->key if（T）{if（T->lchild）r=r+T->lchild->size+1；else r=r+1；} } else return （r）；//返回*x结点的中序序号 return （0）； //T树上无x结点。 }//结束算法Rank 算法2：本题的另一种解法是设r是以*x为根的中序序号。同样，若x的左子树为空，r=1;否则，r=x->lchild->size+1。利用结点的双亲域，上溯至根结点，即可求得*x的中序序号。 int Rank（tree T，node *x） // 在二叉排序树T上，求结点x的中序序号 {{if（x->lchild）r=x->lchild->size+1；else r=1；//x的这个序号是暂时的 p=x; //p要上溯至根结点T，求出*x的中序序号 while (p!=T) {if (p==p->parents->rchild) //p是其双亲的右子女 {if (p->parents->lchild==null) r++; else r=r+p->parent->lchild->size+1; } else r-- //p是其双亲的左子女 p=p->parents; }//while return (r); }//Rank 23．[题目分析] 本题未直接给出哈希表表长，但已给出装填因子小于1，且哈希函数H（k）为关键字第一个字母在字母表中的序号，字母‘A’的序号为1，表长可设为n（n≥27），而链地址法中，表长26。查找不成功是指碰到空指针为止（另一种观点是空指针不计算比较次数）。 （1）void Print(rectype h[ ]） //按关键字第一个字母在字母表中的顺序输出各关键字 {int i,j； for（i=0;i≤26；i++） // 哈希地址0到26