参考答案四、简答及应用
1．作为静态查找表存储结构的顺序表的类型定义如下：
#define maxsize 静态查找表的表长 ;
typedef struct
{ keytype key ; /* 关键字 */
…… /* 其他域 */
} rec ;
typedef struct
{ rec item [ maxsize + 1 ] ;
int n ; /* 最后一个数据元素的下标 */
} sqtable ;
静态查找表中的数据元素存放在上述数组的第1到第 n 个单元中，第 n+1 到最后一个单元为备用区，0或 n+1 单元被用于设置“岗哨”，以便简化查找运算的实现。
2．一棵二叉排序树（又称二叉查找树）或者是一棵空树，或者是一棵同时满足下列条件的二叉树：
若它的左子树不空，则左子树上所有结点的键值均小于它根结点键值。;
若它的右子树不空，则右子树上所有结点的键值均大于它根结点键值。;
它的左、右子树也分别为二叉排序树。
3．开散列表的组织方式如下：设选定的散列函数为 H,H的值域（即散列地址的集合）为0．．n – 1。设置一个“地址向量”pointer HP[ n ],其中的每个指针HP[ i ]指向个单链表用于存储所有散列地址为i 的数据元素,即所有散列地址为ii的同义词。每一个样的单链表称为一个同义词子表。由地址向量以及向量中的每个指针所指的同义词子表构成存储结构称为开散列表。这种开散列解决冲突的方法又称“拉链法”。开散列表类型定义如下：
typedef struct tagnode
{ keytype key ;
struct tagnode *next ;
,．．．．,/*其他其他域*/
}*pinter,nod ;
tyedef poiner openhah[n] ;
4．闭散列表是一个一维数组，其元素的类型与动态查找表中数据元素的类型一致：
#define maxsize 闭散列表的容量
typedef struct
{ keytype key ;
,．．．．,/*其他域*/
} element ;
typedef element closehash[ maxsize ] ;
5．闭散列表是一个大小固定的一维数组，解决冲突的基本思想是在需要时为每个键值K生成一个散列地址序列d0，d1，…，di，…，dm-1。其中d0=H(K)是K的散列地址；所有di(0<i<m)是后继散列地址。当插入K时，若位置d0=H(K)上的结点已被别的数据元素占用，则按上述地址序列依次探测，将找到的第一个空闲位置di作为K的存储位置。若所有后继散列地址都不空闲，说明该闭散列表已满（溢出）。相应地，查找或删除K时将按同样的后继地址序列依次查找。查找成功时回送该位置或删除该位置上的数据元素（实际上是对该结点加以标记）；查找不成功时回送一个特殊标志。
6.对地址单元d = H ( K ),如发生冲突，以d为中心在左右两边交替进行探测。按照二次探测法，键值K的散列地址序列为：
d0 = H ( K ),
d1 = (d0 + 12 ) mod m,
d2 = (d0-12 ) mod m,
d3 = (d0 + 22 ) mod m,
d4 = (d0 - 22 ) mod m,
……
7．此法要求设立多个散列函数Hi,i= 1,…,k 。当给定值K与闭散列表中的某个键值是相对于某个散列函数Hi的同义词因而发生冲突时，继续计算该给定值K在下一个散列函数Hi+1下的散列地址，直到不再产生冲突为止。
8．散列表由两个一维数组组成。一个称为基本表，另一个称为溢出表。插入首先在基本表上进行；假如发生冲突，则将同义词存入溢出表。
9．假设长度为20的有序序列为（ a1,a2,…,a20 ）,按二分查找法得到的判定树如图简答题9所示。
成功平均查找长度为：（ 1 + 2 * 2 + 3 * 4 + 4 * 8 + 5 * 5 ）/ 20= 74 /20 = 3.7
10．
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16
①006 087 155 188 220 465 505 508 511 586 656 670 700 766 897 908
↑ ↑ ↑
low mid hig
②006 087 155 188 220 465 505 508 511 586 656 670 700 766 897 908
↑ ↑ ↑
low mid hig
③006 087 155 188 220 465 505 508 511 586 656 670 700 766 897 908
↑ ↑ ↑
low mid hig
（成功）
11．分析：平衡二叉树AVL要求二叉树上任何一个结点的平衡因子为-1，0，1，如有一个元素的平衡因子不是-1，0，1，此二叉树就不是平衡二叉树，必须通过调整把此二叉树变成平衡二叉树。平衡二叉树是二叉树排序树（对结点数结点相同的二叉树）平均查找次数最小的一种二叉树。
答案见图简答题 11（1）（2）所示。成功平均查找长度为：ASL=( 1 +2 * 2 + 3 * 4 + 4 * 4 ) / 11 = 33 /11 = 3,
12．分析：开散列表上查找失败的平均查找次数的计算方法，是对每一种情况（即一个下标）计算查找失败次数的总和除以表的长度，即（3 + 1 + 2 + 2 + 1 + 4 + 3 + 3 + 1 + 2 + 1 +1 + 1 + 1 ）/ 14 ≈2。
闭散列表查找失败的平均查找次数的计算方法，是对每一种情况（即每一个下标）计算查找失败次数的总和除以表的长度，即（5+4+3+2+1+9+8+7+6+5+4+3+2+1）/14 = 60/14≈4。
开散列表见图简答题12-1。
闭散列表见图简答题12-2。
0 1 2 3 4 5 6 7 8 9 10 11 12 13
Apr | Aug | Dec | Feb | | Jan |Mar | May | Jun | Jul | Sep | Oct | Nov |
1 2 1 1 1 1 2 4 5 2 5 6
图简答题12-2闭散列表
开散列表上查找成功的平均查找长度：
ASL =（1+2+1+1+1+2+3+1+2+1+2+1）/12 = 18/12 = 1.5
开散列表上查找不成功的平均查找长度：
ASL =（3+1+2+2+1+4+3+3+1+2+1+1+1+1）/14 = 26/14≈2
闭散列表上查找成功的平均查找长度：
ASL =（1+2+1+1+1+1+2+4+5+2+5+6）/12 = 31/12≈2.6
闭散列表上查找不成功的平均查找长度：
ASL =（5+4+3+2+1+9+8+7+6+5+4+3+2+1）/14 = 60/14≈4
13．开散列表见图简答题13。
查找成功的平均查找长度为：（4*2+8）/ 12 = 4/3。
14．衡量算法的标准有很多，时间复杂度只是其中之一。尽管有些算法时间性能很好，但是其他方面可能就存在着不足。比如散列查找的时间性能很优越，但是需要关注如何合理地构造散列函数问题，而且总存在着冲突等现象，为了解决冲突，还得采用其他方法。
二分查找也是有代价的，因为事先必须对整个查找区间进行排序，而排序也是费时的，所以常应用于频繁查找的场合。对于顺序查找，尽管效率不高，但却比较简单，常用于查找范围较小或偶而进行查找的情况。
五、算法设计
1．分析：将岗哨设置在高下标端，表示从线性表低端查找时，在不成功的情况下，算法自动在岗哨处终止。另外，在等概率前提下，查找成功的平均查找长度等于每一个元素查找次数之和除以结点总数。
Int sqsearch0 (sqtable A,keytype X) /*数组有元素n个*/
{ i=1; A.item[n+1].key=X; /*设置哨兵*/
while (A.item[n+1].key!=X) i++;
return (i% (n+1)); /*找不到返回0，找到返回其下标*/
}
查找成功平均查找长度为：（1+2+3+…+n）/ n =（1+n）/ 2。
查找不成功平均查找长度为：n+1。
2．（1）int sqsearch1 (sqtable A,keytype X) /*数组有元素n个*/
{ i=1; a.item[n+1].key!=X; /*设置哨兵*/
while (A.item[n+1].key!=X) i++;
if ( (i!=1)&&(i<n+1))
{ temp=A.item[i].key;
A.item[i].key=A.item[i-1].key; /*结点i-1和i交换*/
A.item[i-1].key=temp;
i--;
}
return (i% (n+1));
}
（2）lklist lksearch2 (lklist head,dataytpe X)
{ p=head->next;
q=head;
r=NULL; /*r是q的前趋，q是p的前趋*/
while ((p!=NULLl)&&(p->data!=X)) {r=q;q=p;p=p->next;} /*搜索结点X*/
if ((p!=head->next)&&(p!=NULL))
{q->next=p->next;p->next=q;r->next=p;} /*交换q，p结点顺序*/
return (p);
3．分析：在等查区间的上、下界处设两个指针，由此计算出中间元素的序号，当中间元素大于给定值X时，接下来到其低端区间去查找；当中间元素小于给定值X时，接下来到其高端区间去查找；当中间元素等于给定值X时，表示查找成功，输出其序号。
Int binlist (sqtable A,int s,t,keytype X) /*t、s分别为查找区间的上、下界*/
{ if(s<t) return(0); /*查找失败*/
else
{ mid=(s+t)/2;
switch(mid)
{ case x<A.item[mid].key,return(binlist(A,s,mid-1,X)); /*在低端区间上递归*/
case x==A.item[mid].key,return(mid); /*查找成功*/
case x>A.item[mid].key,return(a,mid+1,t,X)); /*在高端区间上递归*/
}
}
}
4．分析：采用递归方法，从根结点开始查找结点p，若查询结点是所要找的结点，返回其深度h0。否则，到左、右子树上去找，查找深度加1。
int find1 ( birtreptr T,p,int h0 )
/*在二叉树排序树T中查找结点p的层次，若不在时返回空值。h0为根结点T的层次*/
{ if ( p == NULL ) return ( 0 ) ; /* 没找到，返回0 */
if( p ==T) return( h0 ) ; /* 找到 */
else if (p -> data < T -> data ) return( find1( T ->lchild,p,h0) +1) ; /* 到左子树去找 */
else return ( find1 ( T -> rchild,p,h0) + 1); /* 到右子树去找 */
}
int find2( birtrptr T,p ) { return ( find1 ( T,p,1 ) ) ; }
5．分析：根据题目要求分下面情况进行讨论：
若A为根结点，则A为公共祖先；
若A->data<T->tata且T->data<B->data,T为公共祖先；
若A->data<T->data且B->data<T->data或A->data>T->data且B->data>T->data,则到T的左右子树去查找。
bitreptr ANS (bitreptr T,A,B) /*T为二叉排序树的根结点*/
{ if (T==NULL) return (NULL); /*不存在*/
else if ((A->data<T-V>data)&&(T->data<B->data)|| /*T为公共祖先*/
(A->data==T->data)) return (T);
else if ((A->data>T->data) return (ANS(T->rchild,A,B)); /*到右子树上查找*/
else return (ANS(T->lchild,A,B)); /*到左子树上查找*/
}
6．分析：对二叉排序树来讲，其中根遍历序列为一个递增有序序列。因此，对给定的二叉树进行中根遍历，如果始终能保证前一个值比后一个值小，则说明该二叉树是二叉排序树。
int bsbtr (bitreptr T) /*predt记录当前结点前趋值，初值为-∞*/
{ if (T==NULL) return(1);
else {b1=bsbtr(T->lchild); /*判断左子树*/
if (!b1 || (predt>=T->data)) return(0); /*当前结点和前趋比较*/
predt=T->data; /*修改当前结点的前趋值*/
return(bsbtr(T->rchild)); /*判断右子树并返回最终结果*/
}
}
7．分析：在二叉排序树上删除指定结点p，首先要找到p的双亲结点Pre。删除结点p又分三种情况（下面仅以p为其双亲左孩子举例）：
若p结点为叶子结点，只要令pre->lchild=null即可。
若p结点只有一棵子树树，令其子树代替结点，即pre->lchild=p->lchild或Pre->lchild=p->rchild。
若结点p的左子树和右子树均不空，做法是p的直接前趋（或直接后继）替代p，然后再从二叉排序树中删除它的直接前趋（或直接后继）。
bitreptr srch_bstree (bitreptr pre,bitreptr bst,keytype k,int found)
/*pre为bst结点的双亲，k为删除结点的关键字，found为查找标志，若找到关键字为k的结点，则置found值为1，找不到found值为0*/
{ if (bst==NULL) {found=0; return(p); }
else if (bst->key==k) {found=1; return(pre); }
else if (k<bst->key) {pre=bst; return(srch_bstre(pre,bst->lchild,k,found)); };
else {pre=bst;return(srch_bstree(pre,bst->rchild,k,found)) };
}
void del_bstree(bitreptr pre,bst,p)
/*bst为二叉树根结点，p为删除结点，pre为p的双亲结点，若p为根结点，则Pre为Null*/
{ k=p->key; found=0;
pre=srch_bstree( pre,bst,k,found)
if (found)
switch{
case (p->lchild==NULL)&&(p->rchild==NULL),/*p为叶结点*/
pre->lchild=NULL; free(p); break;
case (p->lchild==NULL)&&(p->rchild!=NULL),/*p有右孩子*/
pre->lchild=p->rchild; free(p); break;
case (p->lchild!=NULL)&&(p->rchild==NULL),/*p有左孩子*/
pre->lchild=p->lchild; free(p); break;
case (p->lchild!=NULL)&&(p->rchild!=NULL),/*p有左右孩子*/
{ q=p; s=p->lchild;
while (s->rchild!=NULL) {q=s;s=s->rchild;} /*找p的直接前趋*/
p->data=s->data /*p直接前趋的值传给p*/
if (q!=p) q->rchild=s->lchild; /*删除p直接前趋结点*/
else q->lchild=s->lchild; /*q=p时，即为p的左孩子*/
free (s);
}
} /*end switch*/
else {/*p为双亲右孩子，类似p为双亲左孩子，略。*/}
else printf (“没有找到结点P，删除结点有错误。”);
}
8．分析：显然，AVL树的插入算法应在二叉排序树插入算法的基础上扩充以下功能：①判断插入结点之后是否平衡；②若是，寻找最小失衡子树并转③；③判断失衡类型并做相应调整。
失衡的判断可以与寻找最小失衡子树结合起来，最小失衡子树的根结点一定是离插入结点最近，且插入之前平衡因子的绝对值为1的结点。AVL树插入算法的基本步骤如下：
在寻找新结点的插入位置的过程中，记下离该位置最近，且平衡因子不等于零的结点a（此结点即为可能出现的最小失衡树的根）；
修改自该结点至插入位置路径上所有结点的平衡因子（注意：树上其他结点的平衡因子均不受插入的影响）；
判断实施插入操作之后，结a点的平衡因子的绝对值是否大于1（即判断是否失衡）。若是，进一步判断失衡类型并做相应调整；否则插入过程结束。
仍以二叉链表作为AVL树的存储结构。但每个结点需增加一个域用于存储平衡因子。类型定义如下：
typedef struct taganode
{ keytype key; /*键值*/
int bf; /*平衡因子域*/
struct taganode *lchild,*rchild; /*孩子指针域*/
…… /*其他域*/
} anode,*avlpt;
在此存储结构上，AVL树的插入算法如下：
avlpt insert_avltree (keytype K,avlpt T)
{s=malloc(size); s->key=K; s->lchild=NULL; s->rchild=NULL;
/*生成以K为键值的新结点*/
if (T==NULL) return(s); /*查找s的插入位置，并记录a*/
else
{ f=NULL; a=T; q=NULL;
while (p!=NULL)
{ if (p->bf!=0) {a=p; f=q}
/*a记录bf!=0的结点，其终值指向离插入位置最近的bf!=0的结点*/
q=p;
if (s->key<p->key) q->lchild=s;
else p=p->rchild;
} /*与while对应*/
if (s->key<q->key) q->lchild=s;
else q->rchild=s; /*插入s*/
if(s->key<a->key){p=a->lchild; b=p; d=1;}/*s插入在a的左子树上，增量d为1*/
else {p=a->rchild; b=p; d=-1;} /*s插入在a的右子树上，增量d为-1*/
while (p!=s) /*修改自a的孩子到s路径上结点的平衡因子*/
if (s->key<p->key) /*若s在p的左子树上*/
{p->bf=1; p=p->lchild;}/*p的平衡因子加1。原来为0，因为p是a的子孙*/
else {p->bf=-1; P=P->rchild;} /*p的平衡因子减1，原来为0*/
switch /*判断是否失衡并分类调整*/
{ case a->bf==0,a->bf=d; break;
/*找插入位置过程中未遇到bf!=0的结点，a指树根*/
case a->bf+d==0,a->bf=0; break; /*插入不导致以a为根的子树失衡*/
default,/*其他情况均失衡，判别失衡类型并调整*/
{ if(d==-1) switch
{ case b->bf==1,LL_rotation; break; /*LL调整*/
case b->bf==-1,LR_rotation; break;
/*LR调整，结束时令b指向新子树的根*/
}
else switch
{ case b->bf==-1,RR_rotation; break;
case b->bf==1,RL_rotation; break; /*结束时令B指向新子树的根*/
}
switch /*将新子树链接到原a双亲f上*/
{ case f==NULL,return(b); /*原a为树根*/
case f->lchild==a,f->lchild=b; return(T);
case f->rchild==a,f->rchild=b; return(T);
}
}
}
}
1．作为静态查找表存储结构的顺序表的类型定义如下：
#define maxsize 静态查找表的表长 ;
typedef struct
{ keytype key ; /* 关键字 */
…… /* 其他域 */
} rec ;
typedef struct
{ rec item [ maxsize + 1 ] ;
int n ; /* 最后一个数据元素的下标 */
} sqtable ;
静态查找表中的数据元素存放在上述数组的第1到第 n 个单元中，第 n+1 到最后一个单元为备用区，0或 n+1 单元被用于设置“岗哨”，以便简化查找运算的实现。
2．一棵二叉排序树（又称二叉查找树）或者是一棵空树，或者是一棵同时满足下列条件的二叉树：
若它的左子树不空，则左子树上所有结点的键值均小于它根结点键值。;
若它的右子树不空，则右子树上所有结点的键值均大于它根结点键值。;
它的左、右子树也分别为二叉排序树。
3．开散列表的组织方式如下：设选定的散列函数为 H,H的值域（即散列地址的集合）为0．．n – 1。设置一个“地址向量”pointer HP[ n ],其中的每个指针HP[ i ]指向个单链表用于存储所有散列地址为i 的数据元素,即所有散列地址为ii的同义词。每一个样的单链表称为一个同义词子表。由地址向量以及向量中的每个指针所指的同义词子表构成存储结构称为开散列表。这种开散列解决冲突的方法又称“拉链法”。开散列表类型定义如下：
typedef struct tagnode
{ keytype key ;
struct tagnode *next ;
,．．．．,/*其他其他域*/
}*pinter,nod ;
tyedef poiner openhah[n] ;
4．闭散列表是一个一维数组，其元素的类型与动态查找表中数据元素的类型一致：
#define maxsize 闭散列表的容量
typedef struct
{ keytype key ;
,．．．．,/*其他域*/
} element ;
typedef element closehash[ maxsize ] ;
5．闭散列表是一个大小固定的一维数组，解决冲突的基本思想是在需要时为每个键值K生成一个散列地址序列d0，d1，…，di，…，dm-1。其中d0=H(K)是K的散列地址；所有di(0<i<m)是后继散列地址。当插入K时，若位置d0=H(K)上的结点已被别的数据元素占用，则按上述地址序列依次探测，将找到的第一个空闲位置di作为K的存储位置。若所有后继散列地址都不空闲，说明该闭散列表已满（溢出）。相应地，查找或删除K时将按同样的后继地址序列依次查找。查找成功时回送该位置或删除该位置上的数据元素（实际上是对该结点加以标记）；查找不成功时回送一个特殊标志。
6.对地址单元d = H ( K ),如发生冲突，以d为中心在左右两边交替进行探测。按照二次探测法，键值K的散列地址序列为：
d0 = H ( K ),
d1 = (d0 + 12 ) mod m,
d2 = (d0-12 ) mod m,
d3 = (d0 + 22 ) mod m,
d4 = (d0 - 22 ) mod m,
……
7．此法要求设立多个散列函数Hi,i= 1,…,k 。当给定值K与闭散列表中的某个键值是相对于某个散列函数Hi的同义词因而发生冲突时，继续计算该给定值K在下一个散列函数Hi+1下的散列地址，直到不再产生冲突为止。
8．散列表由两个一维数组组成。一个称为基本表，另一个称为溢出表。插入首先在基本表上进行；假如发生冲突，则将同义词存入溢出表。
9．假设长度为20的有序序列为（ a1,a2,…,a20 ）,按二分查找法得到的判定树如图简答题9所示。
成功平均查找长度为：（ 1 + 2 * 2 + 3 * 4 + 4 * 8 + 5 * 5 ）/ 20= 74 /20 = 3.7
10．
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16
①006 087 155 188 220 465 505 508 511 586 656 670 700 766 897 908
↑ ↑ ↑
low mid hig
②006 087 155 188 220 465 505 508 511 586 656 670 700 766 897 908
↑ ↑ ↑
low mid hig
③006 087 155 188 220 465 505 508 511 586 656 670 700 766 897 908
↑ ↑ ↑
low mid hig
（成功）
11．分析：平衡二叉树AVL要求二叉树上任何一个结点的平衡因子为-1，0，1，如有一个元素的平衡因子不是-1，0，1，此二叉树就不是平衡二叉树，必须通过调整把此二叉树变成平衡二叉树。平衡二叉树是二叉树排序树（对结点数结点相同的二叉树）平均查找次数最小的一种二叉树。
答案见图简答题 11（1）（2）所示。成功平均查找长度为：ASL=( 1 +2 * 2 + 3 * 4 + 4 * 4 ) / 11 = 33 /11 = 3,
12．分析：开散列表上查找失败的平均查找次数的计算方法，是对每一种情况（即一个下标）计算查找失败次数的总和除以表的长度，即（3 + 1 + 2 + 2 + 1 + 4 + 3 + 3 + 1 + 2 + 1 +1 + 1 + 1 ）/ 14 ≈2。
闭散列表查找失败的平均查找次数的计算方法，是对每一种情况（即每一个下标）计算查找失败次数的总和除以表的长度，即（5+4+3+2+1+9+8+7+6+5+4+3+2+1）/14 = 60/14≈4。
开散列表见图简答题12-1。
闭散列表见图简答题12-2。
0 1 2 3 4 5 6 7 8 9 10 11 12 13
Apr | Aug | Dec | Feb | | Jan |Mar | May | Jun | Jul | Sep | Oct | Nov |
1 2 1 1 1 1 2 4 5 2 5 6
图简答题12-2闭散列表
开散列表上查找成功的平均查找长度：
ASL =（1+2+1+1+1+2+3+1+2+1+2+1）/12 = 18/12 = 1.5
开散列表上查找不成功的平均查找长度：
ASL =（3+1+2+2+1+4+3+3+1+2+1+1+1+1）/14 = 26/14≈2
闭散列表上查找成功的平均查找长度：
ASL =（1+2+1+1+1+1+2+4+5+2+5+6）/12 = 31/12≈2.6
闭散列表上查找不成功的平均查找长度：
ASL =（5+4+3+2+1+9+8+7+6+5+4+3+2+1）/14 = 60/14≈4
13．开散列表见图简答题13。
查找成功的平均查找长度为：（4*2+8）/ 12 = 4/3。
14．衡量算法的标准有很多，时间复杂度只是其中之一。尽管有些算法时间性能很好，但是其他方面可能就存在着不足。比如散列查找的时间性能很优越，但是需要关注如何合理地构造散列函数问题，而且总存在着冲突等现象，为了解决冲突，还得采用其他方法。
二分查找也是有代价的，因为事先必须对整个查找区间进行排序，而排序也是费时的，所以常应用于频繁查找的场合。对于顺序查找，尽管效率不高，但却比较简单，常用于查找范围较小或偶而进行查找的情况。
五、算法设计
1．分析：将岗哨设置在高下标端，表示从线性表低端查找时，在不成功的情况下，算法自动在岗哨处终止。另外，在等概率前提下，查找成功的平均查找长度等于每一个元素查找次数之和除以结点总数。
Int sqsearch0 (sqtable A,keytype X) /*数组有元素n个*/
{ i=1; A.item[n+1].key=X; /*设置哨兵*/
while (A.item[n+1].key!=X) i++;
return (i% (n+1)); /*找不到返回0，找到返回其下标*/
}
查找成功平均查找长度为：（1+2+3+…+n）/ n =（1+n）/ 2。
查找不成功平均查找长度为：n+1。
2．（1）int sqsearch1 (sqtable A,keytype X) /*数组有元素n个*/
{ i=1; a.item[n+1].key!=X; /*设置哨兵*/
while (A.item[n+1].key!=X) i++;
if ( (i!=1)&&(i<n+1))
{ temp=A.item[i].key;
A.item[i].key=A.item[i-1].key; /*结点i-1和i交换*/
A.item[i-1].key=temp;
i--;
}
return (i% (n+1));
}
（2）lklist lksearch2 (lklist head,dataytpe X)
{ p=head->next;
q=head;
r=NULL; /*r是q的前趋，q是p的前趋*/
while ((p!=NULLl)&&(p->data!=X)) {r=q;q=p;p=p->next;} /*搜索结点X*/
if ((p!=head->next)&&(p!=NULL))
{q->next=p->next;p->next=q;r->next=p;} /*交换q，p结点顺序*/
return (p);
3．分析：在等查区间的上、下界处设两个指针，由此计算出中间元素的序号，当中间元素大于给定值X时，接下来到其低端区间去查找；当中间元素小于给定值X时，接下来到其高端区间去查找；当中间元素等于给定值X时，表示查找成功，输出其序号。
Int binlist (sqtable A,int s,t,keytype X) /*t、s分别为查找区间的上、下界*/
{ if(s<t) return(0); /*查找失败*/
else
{ mid=(s+t)/2;
switch(mid)
{ case x<A.item[mid].key,return(binlist(A,s,mid-1,X)); /*在低端区间上递归*/
case x==A.item[mid].key,return(mid); /*查找成功*/
case x>A.item[mid].key,return(a,mid+1,t,X)); /*在高端区间上递归*/
}
}
}
4．分析：采用递归方法，从根结点开始查找结点p，若查询结点是所要找的结点，返回其深度h0。否则，到左、右子树上去找，查找深度加1。
int find1 ( birtreptr T,p,int h0 )
/*在二叉树排序树T中查找结点p的层次，若不在时返回空值。h0为根结点T的层次*/
{ if ( p == NULL ) return ( 0 ) ; /* 没找到，返回0 */
if( p ==T) return( h0 ) ; /* 找到 */
else if (p -> data < T -> data ) return( find1( T ->lchild,p,h0) +1) ; /* 到左子树去找 */
else return ( find1 ( T -> rchild,p,h0) + 1); /* 到右子树去找 */
}
int find2( birtrptr T,p ) { return ( find1 ( T,p,1 ) ) ; }
5．分析：根据题目要求分下面情况进行讨论：
若A为根结点，则A为公共祖先；
若A->data<T->tata且T->data<B->data,T为公共祖先；
若A->data<T->data且B->data<T->data或A->data>T->data且B->data>T->data,则到T的左右子树去查找。
bitreptr ANS (bitreptr T,A,B) /*T为二叉排序树的根结点*/
{ if (T==NULL) return (NULL); /*不存在*/
else if ((A->data<T-V>data)&&(T->data<B->data)|| /*T为公共祖先*/
(A->data==T->data)) return (T);
else if ((A->data>T->data) return (ANS(T->rchild,A,B)); /*到右子树上查找*/
else return (ANS(T->lchild,A,B)); /*到左子树上查找*/
}
6．分析：对二叉排序树来讲，其中根遍历序列为一个递增有序序列。因此，对给定的二叉树进行中根遍历，如果始终能保证前一个值比后一个值小，则说明该二叉树是二叉排序树。
int bsbtr (bitreptr T) /*predt记录当前结点前趋值，初值为-∞*/
{ if (T==NULL) return(1);
else {b1=bsbtr(T->lchild); /*判断左子树*/
if (!b1 || (predt>=T->data)) return(0); /*当前结点和前趋比较*/
predt=T->data; /*修改当前结点的前趋值*/
return(bsbtr(T->rchild)); /*判断右子树并返回最终结果*/
}
}
7．分析：在二叉排序树上删除指定结点p，首先要找到p的双亲结点Pre。删除结点p又分三种情况（下面仅以p为其双亲左孩子举例）：
若p结点为叶子结点，只要令pre->lchild=null即可。
若p结点只有一棵子树树，令其子树代替结点，即pre->lchild=p->lchild或Pre->lchild=p->rchild。
若结点p的左子树和右子树均不空，做法是p的直接前趋（或直接后继）替代p，然后再从二叉排序树中删除它的直接前趋（或直接后继）。
bitreptr srch_bstree (bitreptr pre,bitreptr bst,keytype k,int found)
/*pre为bst结点的双亲，k为删除结点的关键字，found为查找标志，若找到关键字为k的结点，则置found值为1，找不到found值为0*/
{ if (bst==NULL) {found=0; return(p); }
else if (bst->key==k) {found=1; return(pre); }
else if (k<bst->key) {pre=bst; return(srch_bstre(pre,bst->lchild,k,found)); };
else {pre=bst;return(srch_bstree(pre,bst->rchild,k,found)) };
}
void del_bstree(bitreptr pre,bst,p)
/*bst为二叉树根结点，p为删除结点，pre为p的双亲结点，若p为根结点，则Pre为Null*/
{ k=p->key; found=0;
pre=srch_bstree( pre,bst,k,found)
if (found)
switch{
case (p->lchild==NULL)&&(p->rchild==NULL),/*p为叶结点*/
pre->lchild=NULL; free(p); break;
case (p->lchild==NULL)&&(p->rchild!=NULL),/*p有右孩子*/
pre->lchild=p->rchild; free(p); break;
case (p->lchild!=NULL)&&(p->rchild==NULL),/*p有左孩子*/
pre->lchild=p->lchild; free(p); break;
case (p->lchild!=NULL)&&(p->rchild!=NULL),/*p有左右孩子*/
{ q=p; s=p->lchild;
while (s->rchild!=NULL) {q=s;s=s->rchild;} /*找p的直接前趋*/
p->data=s->data /*p直接前趋的值传给p*/
if (q!=p) q->rchild=s->lchild; /*删除p直接前趋结点*/
else q->lchild=s->lchild; /*q=p时，即为p的左孩子*/
free (s);
}
} /*end switch*/
else {/*p为双亲右孩子，类似p为双亲左孩子，略。*/}
else printf (“没有找到结点P，删除结点有错误。”);
}
8．分析：显然，AVL树的插入算法应在二叉排序树插入算法的基础上扩充以下功能：①判断插入结点之后是否平衡；②若是，寻找最小失衡子树并转③；③判断失衡类型并做相应调整。
失衡的判断可以与寻找最小失衡子树结合起来，最小失衡子树的根结点一定是离插入结点最近，且插入之前平衡因子的绝对值为1的结点。AVL树插入算法的基本步骤如下：
在寻找新结点的插入位置的过程中，记下离该位置最近，且平衡因子不等于零的结点a（此结点即为可能出现的最小失衡树的根）；
修改自该结点至插入位置路径上所有结点的平衡因子（注意：树上其他结点的平衡因子均不受插入的影响）；
判断实施插入操作之后，结a点的平衡因子的绝对值是否大于1（即判断是否失衡）。若是，进一步判断失衡类型并做相应调整；否则插入过程结束。
仍以二叉链表作为AVL树的存储结构。但每个结点需增加一个域用于存储平衡因子。类型定义如下：
typedef struct taganode
{ keytype key; /*键值*/
int bf; /*平衡因子域*/
struct taganode *lchild,*rchild; /*孩子指针域*/
…… /*其他域*/
} anode,*avlpt;
在此存储结构上，AVL树的插入算法如下：
avlpt insert_avltree (keytype K,avlpt T)
{s=malloc(size); s->key=K; s->lchild=NULL; s->rchild=NULL;
/*生成以K为键值的新结点*/
if (T==NULL) return(s); /*查找s的插入位置，并记录a*/
else
{ f=NULL; a=T; q=NULL;
while (p!=NULL)
{ if (p->bf!=0) {a=p; f=q}
/*a记录bf!=0的结点，其终值指向离插入位置最近的bf!=0的结点*/
q=p;
if (s->key<p->key) q->lchild=s;
else p=p->rchild;
} /*与while对应*/
if (s->key<q->key) q->lchild=s;
else q->rchild=s; /*插入s*/
if(s->key<a->key){p=a->lchild; b=p; d=1;}/*s插入在a的左子树上，增量d为1*/
else {p=a->rchild; b=p; d=-1;} /*s插入在a的右子树上，增量d为-1*/
while (p!=s) /*修改自a的孩子到s路径上结点的平衡因子*/
if (s->key<p->key) /*若s在p的左子树上*/
{p->bf=1; p=p->lchild;}/*p的平衡因子加1。原来为0，因为p是a的子孙*/
else {p->bf=-1; P=P->rchild;} /*p的平衡因子减1，原来为0*/
switch /*判断是否失衡并分类调整*/
{ case a->bf==0,a->bf=d; break;
/*找插入位置过程中未遇到bf!=0的结点，a指树根*/
case a->bf+d==0,a->bf=0; break; /*插入不导致以a为根的子树失衡*/
default,/*其他情况均失衡，判别失衡类型并调整*/
{ if(d==-1) switch
{ case b->bf==1,LL_rotation; break; /*LL调整*/
case b->bf==-1,LR_rotation; break;
/*LR调整，结束时令b指向新子树的根*/
}
else switch
{ case b->bf==-1,RR_rotation; break;
case b->bf==1,RL_rotation; break; /*结束时令B指向新子树的根*/
}
switch /*将新子树链接到原a双亲f上*/
{ case f==NULL,return(b); /*原a为树根*/
case f->lchild==a,f->lchild=b; return(T);
case f->rchild==a,f->rchild=b; return(T);
}
}
}
}
