这是我的课程设计题目，下周就要结果．麻烦知道的朋友指教．谢谢！我在后边附了已经编好的程序，可是和题目要求有一定距离，现在进行不下去了．我是一个新手，Ｃ语言学的不够好．请知道的朋友帮我完善一下程序！先谢谢大家！
二叉排序树的相关问题，具体要求如下：
（1）使用二叉链表存储二叉排序树，主要功能有：生成一棵二叉排序树T；计算二叉排序树T的平均查找长度，输出结果；插入元素x，重新计算二叉排序树T的平均查找长度以及统计各结点所在的层次；输入元素x，查找二叉排序树T：若存在含x的结点，则删除该结点；否则输出信息“无x”；判断二叉排序树T是否为平衡二叉树；遍历二叉排序树等；
（2）二叉排序树至少含有10个测试数据，算法对于这些合法的输入数据都能产生满足规格说明要求的结果；
（3）算法对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；对算法实现过程中的异常情况能给出有效信息；
（4）假设二叉排序树中的数据元素为整数，输入时以回车符作为结束标志等；
#include <stdio.h>
#include <stdlib.h>
#define NULL 0
typedef int keytype;
typedef int elemtype;
typedef struct node
{
keytype key; /*关键字域*/
elemtype other; /*其他域*/
struct node *lchild, *rchild; /*左 右孩子指针*/
}*bistree; /*二叉排序树的结点结构*/
int BSTSearch (bistree t,keytype key) /*二叉排序树查找的非递归算法*/
{
bistree p;
p=t;
while(p!=NULL && p->key!=key)
{
if(key<p->key)
p=p->lchild; /*沿左子树查找*/
else
p=p->rchild; /*沿右子树查找*/
}
if(p!=NULL)
return(1);
else
return(0);
}
bistree BSTInsert(bistree t,bistree s) /*二叉排序树的插入的非递归算法*/
{
bistree p,q;
if(t==NULL) /*二叉排序树为空的情况*/
{
t=s;
return(t);
}
p=t; /*从根结点开始*/
while(p!=NULL)
{
q=p;
if(s->key==p->key) /*查找到返回*/
return(t);
else /*继续搜索*/
{
if(s->key<p->key) /*搜索左子树*/
p=p->lchild;
else /*搜索右子树*/
p=p->rchild;
}
}
if(s->key>q->key)
q->rchild=s;
else
q->lchild=s;
return(t);
}
void BSTCreat(bistree t) /*建立一个有n个节点的二叉排序树算法*/
{
bistree s;
keytype key; /*关键字*/
int i,n;
t=NULL;
printf("Please input the number of the nodes:\n");
scanf("%d",&n);
printf("Please input the data:\n");
for(i=1;i<=n;i++)
{
scanf("%d",&key); /*假定关键字为整型*/
s=(bistree)malloc(sizeof(bistree)); /*生成一个新结点*/
s->lchild=NULL;
s->rchild=NULL;
s->key=key; /*调用插入算法将s所指结点插入二叉排序树t中*/
t=BSTInsert(t,s);
}
}
void BSTDelete(bistree t,int key) /*二叉排序树中删除一个结点的算法*/
{
bistree p,q,s;
p=t;
q=NULL; /*p指向待比较的结点，q指向p的前驱结点*/
while(p!=NULL && p->key!=key) /*查找值域为key的结点*/
if(key<p->key)
{
q=p;
p=p->lchild;
}
else
{
q=p;
p=p->rchild;
}
if(p==NULL)
printf("Can not find node %d \n",key);
else if(p->lchild==NULL) /*被删结点无左子树*/
{
if(q==NULL) t=p->rchild; /*考虑p为根结点的情况*/
else if(q->lchild==p)
q->lchild=p->rchild; /*p为双亲的左子树*/
else
q->rchild=p->rchild; /*p为双亲的右子树*/
free(p); /*释放p结点*/
}
else if(p->rchild==NULL) /*被删除结点无右子树*/
{
if(q==NULL)
t=p->rchild; /*考虑p为根结点的情况*/
else if(q->lchild==p)
q->lchild=p->rchild; /*p为双亲的左子树*/
else
q->rchild=p->rchild; /*p为双亲的右子树*/
free(p); /*释放P结点*/
}
else /*被删除结点同时有左子树和右子树*/
{ /*查找被删除结点的左子树中的最右结点，即刚好小于key的结点，也即是p的直接前驱*/
s=p->lchild;
while(s->rchild!=NULL) /*寻找p的直接前驱s*/
s=s->rchild;
s->rchild=p->rchild; /*被删除结点的右子树作为直接前驱s的右子树*/
/*被删除结点的左子树根代替被删结点*/
if(q==NULL) /*被删结点是根结点*/
t=p->lchild;
else if(q->lchild==p) /*p为其双亲结点左子树*/
q->lchild=p->lchild;
else /*p为双亲的右子树*/
q->rchild=p->lchild;
free(p);
}
}
void BSTPrint(bistree t)
{
if(t!=NULL)
{
BSTPrint(t->lchild);
printf("%d\t",t->key);
BSTPrint(t->rchild);
}
}
void main()
{
int k;
bistree p,s1;
keytype key1;
print5f("建立二叉排序树:\n");
p=NULL;
s1=NULL;
BSTCreat(p);
printf("请输入需要查找关键字:\n");
scanf("%d",&key1);
k=BSTSearch(p,key1);
if(!k)
printf("There is no such a node.\n");
else
printf("There id such a node.\n ");
printf("请输入要插入的结点关键字的值:\n");
scanf("%d",&s1->key);
p=BSTInsert(p,s1);
printf("请输入要删除的结点关键字的值:\n");
scanf("%d",&key1);
BSTDelete(p,key1);
printf("打印输出该二叉树:\n");
BSTPrint(p);
}
