2chashu.cpp

二叉排序树

/************************************************************************/
int push(BSTNode *p[],BSTNode *x,int top)
{
	if(top==M-1)printf("overflow");
	else
	{
		top++;
		*(p+top)=x;
	}
	return(top);
}
/************************************************************************/
/*     出栈函数                                                         */
/************************************************************************/
int pop(BSTNode *p[],BSTNode *&x,int top)
{
	if(top<0)printf("overflow");
	else
	{
		x=*(p+top);
		top--;
	}
	
	return(top);
}
/************************************************************************/
/*     中序遍历函数                                                     */
/************************************************************************/
void inorder(BSTNode *root)  
{
	if(!root)return ;
	inorder(root->left);
	PrintStu(root);
	inorder(root->right);
}
/************************************************************************/
/*     层次遍历函数                                                     */
/************************************************************************/
void LevelOrder(BSTNode *root)
{
	BSTNode *p;
	BSTNode *qu[M];      //定义环形队列存放节点指针
	int front,rear;   
	front=rear=-1;
	rear++;
	qu[rear]=root;        //根节点进入队列
	while (front!=rear)
	{
		front=(front+1)%M;
		p=qu[front];			//队头出队列
		PrintStu(p);         //访问节点
		if (p->left!=NULL)      //有左孩子时将其进队
		{
			rear=(rear+1)%M;
			qu[rear]=p->left;
		}
		if (p->right!=NULL)    //有右孩子是将其进队
		{
			rear=(rear+1)%M;
			qu[rear]=p->right;
		}
	}
}
/************************************************************************/
/*     查找节点函数                                                     */
/************************************************************************/
BSTNode *SearchBST(BSTNode *bt,int k)
{
	if(bt==NULL||bt->key==k)
		return bt;
	if(k<bt->key)
		return SearchBST(bt->left,k);
	else
		return SearchBST(bt->right,k);
}
/************************************************************************/
/*     按学号查成绩                                                     */
/************************************************************************/
void IdSearch(BSTNode *root)
{
	BSTNode *stack[20],*p;
	char id[10];
	printf("请输入您要检索的学号:");
	scanf("%s",id);
	int top=0;
	int i;
	stack[top]=root;
	top++;
	while(top>0)
	{											//用栈实现非递归遍历
		top--;
		p=stack[top];
		for(i=0;i<p->count;i++){
			if(strcmp(p->stu[i].id,id)==0){
				printf("学号为的%s成绩为%d",id,p->stu[i].mark);
			}
		}
		if(p->right!=NULL){
			stack[top]=p->right;
			top++;
		}
		if(p->left!=NULL){
			stack[top]=p->left;
			top++;
		}
	}
}
/************************************************************************/
/*     按姓名查成绩                                                     */
/************************************************************************/
void NameSearch(BSTNode *root)
{
	BSTNode *stack[20],*p;
	char name[10];
	printf("请输入您要检索的姓名:");
	scanf("%s",name);
	int top=0;
	int i;
	stack[top]=root;
	top++;
	while(top>0)
	{											//用栈实现非递归遍历
		top--;
		p=stack[top];
		for(i=0;i<p->count;i++){
			if(strcmp(p->stu[i].name,name)==0){
				printf("%s的成绩为%d",name,p->stu[i].mark);
			}
		}
		if(p->right!=NULL){
			stack[top]=p->right;
			top++;
		}
		if(p->left!=NULL){
			stack[top]=p->left;
			top++;
		}
	}

}
/************************************************************************/
/*     按成绩查该分数人数                                               */
/************************************************************************/
void MarkSearch(BSTNode *root)
{
	BSTNode *stack[20],*p;
	int mark;
	int num=0;
	printf("请输入您要检索的成绩:");
	scanf("%d",&mark);
	int top=0;
	int i;
	stack[top]=root;
	top++;
	while(top>0)
	{											//用栈实现非递归遍历
		top--;
		p=stack[top];
		for(i=0;i<p->count;i++){
			if(p->stu[i].mark==mark)num++;
		}
		if(p->right!=NULL){
			stack[top]=p->right;
			top++;
		}
		if(p->left!=NULL){
			stack[top]=p->left;
			top++;
		}
	}
	printf("成绩为%d的学生总共有%d个",mark,num);
}
/************************************************************************/
/*     按分数段查找该段人数                                             */
/************************************************************************/
void KeySearch(BSTNode *root)
{
	BSTNode *p;
	int key;
	key=toKey();
	p=SearchBST(root,key);	
	printf("该成绩段内学生总数为:%d\n",p->count);
}
/************************************************************************/
/*     输出学生信息                                                     */
/************************************************************************/
void PrintStu(BSTNode *p)
{
	int i;
	printf("学号\t");
	printf("姓名\t");
	printf("成绩\t");
	printf("\n");
	for(i=0;i<p->count;i++)
	{
		printf("%s\t",p->stu[i].id);
		printf("%s\t",p->stu[i].name);
		printf("%d\n",p->stu[i].mark);
	}
}
/************************************************************************/
/*     求平均值                                                         */
/************************************************************************/
float AverageStu(BSTNode *root)
{
	BSTNode *stack[20],*p;
	double total=0;
	int top=0;
	int i,n;
	n=AmountStu(root);
	stack[top]=root;
	top++;
	while(top>0)
	{											//用栈实现非递归遍历
		top--;
		p=stack[top];
		for(i=0;i<p->count;i++)total+=p->stu[i].mark;
		if(p->right!=NULL){
			stack[top]=p->right;
			top++;
		}
		if(p->left!=NULL){
			stack[top]=p->left;
			top++;
		}
	}
	return total/n;
}
/************************************************************************/
/*    求最高分                                                          */
/************************************************************************/
int MaxStu(BSTNode *root)
{
	BSTNode *stack[20],*p;
	int max=0;
	int top=0;
	int i;
	stack[top]=root;
	top++;
	while(top>0)
	{											//用栈实现非递归遍历
		top--;
		p=stack[top];
		for(i=0;i<p->count;i++){
			if (p->stu[i].mark>max)max=p->stu[i].mark;
		}
		if(p->right!=NULL){
			stack[top]=p->right;
			top++;
		}
		if(p->left!=NULL){
			stack[top]=p->left;
			top++;
		}
	}
	return max;
}
/************************************************************************/
/*     求最低分                                                         */
/************************************************************************/
int MinStu(BSTNode *root)
{
	BSTNode *stack[20],*p;
	int min=100;
	int top=0;
	int i;
	stack[top]=root;
	top++;
	while(top>0)
	{											//用栈实现非递归遍历
		top--;
		p=stack[top];
		for(i=0;i<p->count;i++){
			if (p->stu[i].mark<min)min=p->stu[i].mark;
		}
		if(p->right!=NULL){
			stack[top]=p->right;
			top++;
		}
		if(p->left!=NULL){
			stack[top]=p->left;
			top++;
		}
	}
	return min;
}
/************************************************************************/
/*     求方差                                                           */
/************************************************************************/
float VarianceStu(BSTNode *root,float average)
{
	BSTNode *stack[20],*p;
	double a;
	double v=0;
	int top=0;
	int i;
	stack[top]=root;
	top++;
	while(top>0)
	{											//用栈实现非递归遍历
		top--;
		p=stack[top];
		for(i=0;i<p->count;i++){
			a=(p->stu[i].mark-average)*(p->stu[i].mark-average);
			v+=a;
		}
		if(p->right!=NULL){
			stack[top]=p->right;
			top++;
		}
		if(p->left!=NULL){
			stack[top]=p->left;
			top++;
		}
	}
	return v/AmountStu(root);
}
/************************************************************************/
/*     求学生总数                                                       */
/************************************************************************/
int AmountStu(BSTNode *root)
{
	BSTNode *stack[20],*p;
	int amount=0;
	int top=0;
	stack[top]=root;
	top++;
	while(top>0)
	{											//用栈实现非递归遍历
		top--;
		p=stack[top];
		amount+=p->count;
		if(p->left!=NULL){
			stack[top]=p->left;
			top++;
		}
		if(p->right!=NULL){
			stack[top]=p->right;
			top++;
		}
	}
	return amount;
}
/************************************************************************/
/*     存盘函数                                                         */
/************************************************************************/
void BSTWrite(BSTNode *root)
{
	FILE *fp1,*fp2;									//fp1存储节点信息，fp2存储节点个数
	char filename[20];
	int i;
	int k=0;
	BSTNode *p;
	BSTNode *qu[M];      //定义环形队列存放节点指针
	int front,rear;   
	printf("\n请输入要写入的文件名:");
	scanf("%s",filename);
	if((fp1=fopen(filename,"wb+"))==NULL)
	{
		printf("can't open\n");
		exit(0);
	}
	fp1=fopen(filename,"w+");
	fp2=fopen("count","w+");
	fwrite(root,sizeof(BSTNode),1,fp1);
	front=rear=-1;
	rear++;
	qu[rear]=root;        //根节点进入队列
	while (front!=rear)
	{
		front=(front+1)%M;
		p=qu[front];					
		for(i=0;i<p->count;i++)	{		 //写入节点
			fwrite(p,sizeof(BSTNode),1,fp1);
			k++;
		}
		if (p->left!=NULL)      
		{
			rear=(rear+1)%M;
			qu[rear]=p->left;
		}
		if (p->right!=NULL)    
		{
			rear=(rear+1)%M;
			qu[rear]=p->right;
		}
	}
	fprintf(fp2,"%d",k);
	fclose(fp1);
	fclose(fp2);
}
/************************************************************************/
/*    恢复函数                                                          */
/************************************************************************/
BSTNode *BSTRead()
{
	FILE *fp1,*fp2;									//fp1存储节点信息，fp2存储节点个数
	char filename[20];
	int i;
	int k;
	BSTNode *root=NULL,*p;   
	printf("\n请输入要读取的文件名:");
	scanf("%s",filename);
	if((fp1=fopen(filename,"r"))==NULL)
	{
		printf("can't open\n");
		exit(0);
	}
	fp1=fopen(filename,"a+");
	fp2=fopen("count","a+");
	fscanf(fp2,"%d",&k);
	for (i=0;i<k;i++)
	{
		p=(BSTNode*)malloc(sizeof(BSTNode));
		fread(p,sizeof(BSTNode),1,fp1);
		root=INsertBST(root,root,p);
	}
	fclose(fp1);
	fclose(fp2);
	return root;
}