发布时间 : 星期日 文章严蔚敏-数据结构集合习题更新完毕开始阅读4410cb09bb68a98271fefaf5
int count；
struct node * llink，*rlink； }BiTNode，*BSTree；
void Search_InsertX(BSTree t，datatype X） //在二叉排序树t中查找值为X的结点，若查到，则其结点的count域值增1，否则，
//将其插入到二叉排序树中。
{p=t；
while（p!=null && p->data!=X） //查找值为X的结点，f指向当前结点的双亲 {f=p；
if（p->data
{p=（BiTNode *）malloc(sizeof （BiTNode））； p->data=X；p->llink=null；p->rlink=null；
if（f->data>X）f->llink=p；else f->rlink=p； }
else p->count++；// 查询成功，值域为X的结点的count增1。 }// Search_InsertX
17．[题目分析] 因为二叉树各结点已标明了平衡因子b，故从根结点开始记树的层次。根结点的层次为1，每下一层，层次加1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子b为0时，任选左右一分枝向下查找，若b不为0，则沿左（当b=1时）或右（当b=-1时）向下查找。 int Height（BSTree t） // 求平衡二叉树t的高度 {level=0；p=t； while（p）
{level++； // 树的高度增1
if（p->bf<0）p=p->rchild；//bf=-1 沿右分枝向下
//bf是平衡因子，是二叉树t结点的一个域，因篇幅所限，没有写出其存
储定义
else p=p->lchild； //bf>=0 沿左分枝向下
}//while
return （level）；//平衡二叉树的高度
} //算法结束
18．[题目分析]二叉排序树的建立问题请参见上面题3（1）。将二叉排序树上的各整数按降序写入磁盘的问题，要对二叉排序树进行“中序遍历”。这里的“中序遍历”要采取“右根左”。为方便起见，先将整数写入一全局变量数组中，再写入磁盘文件中。
int i=0,a[n];//长度为n的整型数组 void InOrder(BSTree t)
//先右后左的中序遍历二叉排序树t，假定该树t已在本题（1）中生成 {if (t)
{ InOrder(t->rchild) a[i++]=t->key; InOrder(t->lchild) }
}//InOrder
void SaveToDisk()
//将二叉排序树上的各整数按降序写入磁盘 {FILE *fp;
if ((fp=fopen(“file1.dat”, “wb”))==null) {printf(“file can not open!\\n”);exit(0); }
fwrite(a,sizeof (int),n,fp);//将数组a中的n个整数写入磁盘 fclose(fp);//关闭文件 }//SaveToDisk
19．本题的分析同第18题。这里直接写出算法 （1）递归算法
void DecPrint(BSTree t）
//递减序输出二叉排序树t中所有左子树为空右子树非空的结点数据域的值。 {if（t）
{DecPrint(t->rchild)；
if（!t->lchild && t->rchild）printf(t->data：4） 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：4)； t=t->lchild； // 去左分枝
}//if
}//while }//算法结束
20．[题目分析]这是一个在单链表中查找结点，在结点内查找给定值的过程，先定义存储结构：
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 21．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。 22．[题目分析]本题采用中序遍历，将遍历结点与前驱比较，若相同，则不输出并记数。 void BSTPrint(BSTree t,int *count） //递增序输出二叉排序树中结点的值，滤去重复元素 {if（t） {BSTPrint(t->lchild)； //中序遍历左子树 if（pre==null）pre=t; //pre是当前访问结点的前驱,调用本算法时初值为null else if(pre->key==t->key)*count++;//*count记重复元素，调用本算法时初值为0 else {printf（“M”,t->key）；pre=t；} // 前驱后移 BSTPrint(t->rchild)； //中序遍历右子树 }//if }//结束BSTPrint 算法 23．[题目分析]本题算法之一是如上题一样，中序遍历二叉树，在“访问根结点”处判断结点值是否≥x，如是则输出，并记住第一个≥x值结点的指针。这里给出另一个算法，利用二叉排序树的性质，如果根结点的值>=x,则除左分枝中可能有 从根结点开始查找，找到结点值 // 中序输出以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）//沿左分枝向下，找第一个值 {f=p；p=p->lchild ；} //f是p的双亲结点的指针，且指向第一个值≥x的结点 if(p) f->lchild=null; //双亲与找到的第一个值 Print(bst)；//输出以bst为根的子树 }//while }//内层if（p） }//第一层if（p） }//PrintAllx 24．[题目分析] 因为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结点。