typedef struct Bitnode /*定义二叉排序树的结点类型*/
{ keytype key;/*存放记录关键值的数据域key*/ elemtype other; /*存储记录中的其它数据项的域*/
struct Bitnode *lchild, *rchild; /*左、右孩子指针域*/ }Bitnode,*Bitree;
【核心算法提示】
（1）二叉排序树查找操作的基本步骤：对于给定的待查找记录的关键字值key，在二叉排序树非空的情况下，先将给定的值key与二叉排序树的根结点的关键字值进行比较，如果相等，则查找成功，函数返回指向根结点的指针，否则，如果给定的值key小于根结点的关键字值，则在二叉排序树的左子树上继续查找；如果给定的值key大于根结点的关键字值，则在二叉排序树的右子树上继续查找，直到查找成功，或子树为空即查找失败函数返回空指针为止。
（2）二叉排序树的插入操作的基本步骤（用递归的方法）：如果已知二叉排序树是空树，则插入的结点成为二叉排序树的根结点；如果待插入结点的关键字值小于根结点的关键字值，则插入到左子树中；如果待插入结点的关键字值大于根结点的关键字值，则插入到右子树中。
【核心算法描述】
Bitree Bstsearch1(Bitree T,keytype key) /*二叉排序树查找的递归算法*/
{ if (T==NULL||key==T->key)
return T; /*当T为非空时，查找成功，否则表示查找失败*/ else if (key< T->key)
return(searchbst(T->key, key)); /*递归查找二叉排序树的左子树*/ else return(searchbst(T->key, key)); /*递归查找二叉排序树的右子树*/ }
Bitree Bstsearch2(Bitree T,keytype key) /*二叉排序树查找的非递归算法*/ { Bitree p; p=T;
while (p&& key!= p->key) { if (key
p=p->lchild; /*沿左子树继续查找*/ else
p=p->rchild; /*沿右子树继续查找*/ }
return p; }
Bitree Bstinsert(Bitree T,Bitree s)
/*将结点s插入到二叉排序树T中，使其仍然构成一棵二叉排序树*/
{ if(T==NULL) T=s; /*如果已知二叉排序树是空树，则新插入的结点成为根结点*/ else if(s->key>T->key)
T->rchild=Bstinsert(T->rchild,s); /*递归调用*/ else if(s->key
46
T->lchild=Bstinsert(T->lchild,s);/*递归调用*/ return T;}
3．源程序代码参考
#include
typedef struct Bitnode /*定义二叉排序树的结点类型*/ { keytype key; elemtype other;
struct Bitnode *lchild, *rchild; }Bitnode,*Bitree;
Bitree Bstinsert(Bitree T,Bitree s)
/*将结点s插入到二叉排序树T中，使其仍然构成一棵二叉排序树*/ { if(T==NULL) T=s; else if(s->key>T->key)
T->rchild=Bstinsert(T->rchild,s); /*递归调用*/ else if(s->key
T->lchild=Bstinsert(T->lchild,s);/*递归调用*/ return T;}
Bitree creat(Bitree T)
/*根据输入的n个关键字序列，建立一棵二叉排序树*/ { Bitree s; keytype key; int i,n;
printf(\ scanf(\
printf(\ for (i=0; i s=(Bitree)malloc(sizeof(Bitnode)); /*生成一个待插入的新结点*/ s->key=key; s->lchild=NULL; s->rchild=NULL; T=Bstinsert(T,s);/*调用二叉排序树插入函数*/ } return T; 47 } Bitree Bstsearch(Bitree T,keytype key) /*二叉排序树查找的非递归算法*/ { Bitree p; p=T; while (p&& key!= p->key) { if (key p=p->lchild; /*沿左子树继续查找*/ else p=p->rchild; /*沿右子树继续查找*/ } return p; } main()/*主函数*/ { Bitree T=NULL,p; keytype key; T=creat(T); /*调用二叉排序树建立函数*/ printf(\请求输入需要查找的记录的关键字值*/ scanf(\ p=Bstsearch(T,key);/*调用二叉排序树查找函数*/ if(p==NULL) printf(\输出“找不到”信息*/ else printf(\输出“找到”信息*/ } 5． 运行结果参考如图7-1所示： 图7-1 验证性实验运行结果 七、设计性实验(以下两个设计题目学生可根据自己的掌握程度或兴趣自行选择完成) 1．在二叉排序树上实现插入、删除一个指定结点。 48 ⑴ 实验要求 （1）按照输入的n个关键字序列顺序建立二叉排序树，二叉排序树采用二叉链表的存储结构。 （2）输入待插入记录的关键字值key,然后在二叉排序树上查找该记录，如果查找失败，则在二叉排序树中插入该记录对应的结点，并输出插入操作后的二叉排序树（以某种遍历序列表示）。 （3）输入待删除记录的关键字值key,然后在二叉排序树上查找该记录，如果查找成功，则在二叉排序树中删除该记录对应的结点，并输出删除操作后的二叉排序树（以某种遍历序列表示）。 ⑵ 核心算法分析 要实现以上功能，主要要完成查找、插入和删除操作算法的编写。插入操作是在查找失败时才进行，其算法内容验证性实验中的内容相同。为了删除操作的需要，查找算法只要在验证性实验的查找算法内容中，当搜索指针p移动之前，增加一个记载其双亲结点的指针f的操作语句。与插入相反，删除操作是在查找成功时才进行，下面对删除操作的算法详细分析如下：由二叉排序树的性质决定，中序遍历二叉排序树可得到一个关键字的有序序列，则在二叉排序树中删除一个结点就相当于删除有序序列中的一个记录，只要保证删除某个结点后仍然保持二叉排序树的特性即可。假设用p指针指向被待删除的结点，f指针指向二叉排序树中p的双亲结点，删除操作的关键是找到p结点在中序遍历序列中的前驱结点s，再用s替代掉p，如图7-2所示： 图7-2 前驱结点 被删结点 则删除操作需要分三种情况分别处理： （1） 若待删除的结点是叶子结点，则只要将其双亲结点中相应指针域的值改为“空”； （2） 若待删除的结点只有左子树或者只有右子树，则只要将其双亲结点的相应指针域的值改为 “指向待删除结点的左子树或右子树”； （3） 若待删除的结点既有左子树又有右子树，则以其中序遍历序列下的前驱结点替代掉待删结点p，然后再删除该前驱结点s。 ⑶ 核心算法描述 Bitree f=NULL; /*全局变量*/ Bitree Bstsearch(Bitree T, keytype key) /*在二叉排序树中查找关键字为key的记录，如果找到则返回该记录结点的地址,全局变量f指向该结点的双亲结点，否则返回空指针,全局变量f指向搜索路径上最后一个访问的结点*/ { Bitree p; 49 p=T; while (p&& key!= p->key) { if (key { f=p; /* 在p移动之前，用f 记下p, 使f永远指向p的双亲结点*/ p=p->lchild; /*沿左子树继续查找*/ } else { f=p; p=p->rchild; /*沿右子树继续查找*/ } } return p; } Bitree Bstinsert(Bitree T,Bitree s) /*将结点s插入到二叉排序树T中，使其仍然构成一棵二叉排序树*/ { if(T==NULL) T=s; else if(s->key>T->key) T->rchild=Bstinsert(T->rchild,s); /*递归调用*/ else if(s->key T->lchild=Bstinsert(T->lchild,s);/*递归调用*/ return T;} Bitree Bstdelete(Bitree T,Bitree p) /*二叉排序树上的删除算法*/ { Bitree q,t; if (p->lchild==NULL) /*待删结点无左子树*/ { if (f==NULL) /*如果p为根结点*/ T=p->rchild; else if (f->lchild==p) /*如果p是其双亲的左孩子*/ f->lchild=p->rchild; else /*如果p是其双亲的右孩子*/ f->rchild=p->rchild; free(p); } else if (p->rchild==NULL) /*待删结点无右子树*/ { if (f==NULL) /*如果p为根结点*/ T=p->lchild; else if (f->lchild==p) /*如果p是其双亲的左孩子*/ f->lchild=p->lchild; else /*如果p是其双亲的右孩子*/ 50