application.h

1.编制构建二叉排序树的程序

/****************************************************************/
void InitBST(BSTree *T)//初始化二叉树函数
{
	T->Root=NULL;//将树置为空树
	T->length=0;//数据量为0
}//InitBST
/********************************************************************/
int SearchBST_L(int temp,BSTNode*Root,int*L,BSTNode*p)//查找过程中的搜索函数
{
	(*L)++;//
	if(Root==NULL) return 0;
	if(temp==Root->key)
	{p=Root;return 1;}//找到关键字相同的结点
	else 
	{
		if(temp<Root->key)//转向左孩子搜索
			return(SearchBST_L(temp,Root->lchild,L,p));
		else//转向右孩子搜索
			return(SearchBST_L(temp,Root->rchild,L,p));
	}
}//SearchBST_L
/**********************************************************************************/
int visit(BSTNode * Root)//访问结点
{
	printf("%d\n",Root->key);
	return 1;
}//visit
/**************************************************************************/
int SearchBST_B(int temp,BSTNode **p,BSTNode*Root)//构造二叉平衡树过程中的搜索函数
{
	*p=Root;
	if(!Root)  return 0;//找到适合插入的空结点
	if(Root->key==temp) return 1;//树中存在相同关键字的结点，退回不进行插入
	if(temp<Root->key)//比较关键字大小，决定策略
	{
		if(Root->lchild==NULL)
		{(*p)=Root;return 0;}//左孩子为空，适合插入，返回Root结点用来插入
		else return(SearchBST_B(temp,p,Root->lchild));//转向左孩子搜索
	}
	else
	{
		if(Root->rchild==NULL)
		{(*p)=Root;return 0;}//右孩子为空，适合插入，返回Root结点用来插入
		else return(SearchBST_B(temp,p,Root->rchild));//转向右孩子搜索
	}
}//SearchBST_B
/*************************************************************************/
int BuildBST(BSTree *T)//构造 二叉搜索树
{
	int temp;//做临时存储数据使用
	FILE* fp;
	BSTNode *p,*s;
	char file[12]={'\0'};
	p=NULL;
	printf("请输入需要进行构造 二叉搜索树 的文件名\n");
	gets(file);
	if(!(fp=fopen(file,"r")))
	{printf("open file error\n");return 0;}
	while(!feof(fp))
	{
		fscanf(fp,"%d",&temp);//读取文件数据
		if(!SearchBST_B(temp,&p,T->Root))
		{
			s=(BSTNode*)malloc(sizeof(BSTNode));
			s->key=temp;
			s->lchild=s->rchild=NULL;//为新结点申请空间
			if(!p) 
			{T->Root=s;	T->length++;continue;}//所插结点为树的根结点
			if(temp<p->key)
				p->lchild=s;//插在左孩子位置
			else p->rchild=s;//插在右孩子位置
			T->length++;//树的数据量加1
		}//if
	}//while
	fclose(fp);
	return 1;
}//BuildBSt

/************************************************************************/
int InOrderPrintBST(BSTNode * Root)//中序遍历树
{
	if(Root)//树非空时
	{
		if(InOrderPrintBST(Root->lchild))//递归遍历左孩子
			if(visit(Root))//访问根结点
				if(InOrderPrintBST(Root->rchild)) //递归遍历右孩子
					return 1;
		return 0;
	}
	else return 1;
}//InOrderPrintBST

/*****************************************************************************/
int SearchLen(BSTNode*Root)//查找并计算搜索长度函数
{
	FILE *fp;
	int LEN=0,Len=0,temp,num=0;
	char file[12]={'\0'};
	BSTNode *p;
	getchar();
	printf("请输入需要进行查找的文件名\n");
	gets(file);
	printf("\n************************************\n\n");
	if(!(fp=fopen(file,"r")))
	{printf("open file error\n");return 0;}
	p=NULL;
	fscanf(fp,"%d",&temp);
	while(!(feof(fp)))
	{
		Len=0;
		num++;//统计查找数据的个数，以便计算平均查找长度

		if(SearchBST_L(temp,Root,&Len,p))//查找成功时
			printf("查找成功!\n数据 %d 的成功查找长度为: %d\n\n",temp,Len);
		else//查找失败时
			printf("查找失败!\n数据 %d 的失败查找长度为: %d\n\n",temp,Len);
		LEN=LEN+Len;//总的查找长度
		fscanf(fp,"%d",&temp);
	}//while
	printf("总的查找长度为%.3f\n",((float)LEN));
	printf("总的平均查找长度为%.3f\n",((float)LEN)/num);//打印相关信息
	fclose(fp);
	return 0;
}//SearchLen