2chashu.cpp

二叉排序树

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include<stdlib.h>
#define M 10											//总节点数的最大值
struct student											//学生定义
{
	char name[10];
	char id[10];
	int mark;
};

typedef struct node										//二叉排序树节点定义
{
	int key;       //关键码
	int count;     //记录数组中成员个数
	struct student stu[20];
	struct  node *left,*right;
}BSTNode;
/************************************************************************/
/*    函数声明                                                          */
/************************************************************************/
int toKey();											//由成绩段获得关键码 
int BSTKey(int mark);									//由分数获得关键码 
int push(BSTNode *p[],BSTNode *  x,int top);			//进栈函数
int pop(BSTNode *p[],BSTNode *&x,int top);				//出栈函数 
BSTNode *INsertBST(BSTNode *root,BSTNode *r,BSTNode *s);//插入辅助函数
BSTNode *AddBST(BSTNode *root);							//插入函数
BSTNode *CreateBST();									//创建函数
BSTNode *deletemin(BSTNode *&root);						//删除二叉排序树中最小节点函数
BSTNode *removeNode(BSTNode *root,int key);				//删除节点函数
BSTNode *removeStu(BSTNode *root);						//删除学生记录函数
BSTNode *inorder_clew(BSTNode *root);					//中序线索化函数
void inorder(BSTNode *root);							//中序遍历函数
void LevelOrder(BSTNode *root);							//层次遍历函数 
BSTNode *SearchBST(BSTNode *bt,int k);					//节点检索函数				
void IdSearch(BSTNode *bt);								//按学号检索成绩
void NameSearch(BSTNode *bt);							//按姓名检索成绩
void MarkSearch(BSTNode *bt);							//按成绩检索该分数人数
void KeySearch(BSTNode *bt);							//按成绩段检索该段人数
void PrintStu(BSTNode *root);							//输出学生数据函数
float AverageStu(BSTNode *root);						//求平均值
int MaxStu(BSTNode *root);								//求最高分
int MinStu(BSTNode *root);								//求最低分
float VarianceStu(BSTNode *root,float average );		//求方差
int AmountStu(BSTNode *root);							//求学生总数
void BSTWrite(BSTNode *root);							//二叉树存盘
BSTNode *BSTRead();										//恢复二叉树
/*************************************************************************/
/*     主函数															 */
/*************************************************************************/
int main()
{
	BSTNode *root;
	BSTNode *p;
	int key;
	int n;
	while(1){
		printf("****************************************************************\n");
		printf("*  请选择操作序号(若当前无树，请从文件中恢复或新建)            *\n");
		printf("*  1创建二叉树  2插入  3删除   4中序遍历   5层次遍历           *\n");
		printf("*  6中序线索化  7存盘  8恢复   9检索       10学生总数统计      *\n");
		printf("*  11总体信息   12退出                                         *\n");
		printf("****************************************************************\n");
		printf("选择:");
		scanf("%d",&n);
		if(n!=12){
			switch(n) {
			case 1:
				root=CreateBST();
				break;
			case 2:
				while (1)
				{
					printf("\n请选择操作序号:\n1、插入节点;2、退出;\n");
					scanf("%d",&n);
					if (n!=2)
					{
						switch(n)
						{
						case 1:		root=AddBST(root);
							break;
						case 2:		break;
						}
					}
					else break;
				}
				
				break;
			case 3:

			while(1){
					printf("\n请选择操作序号:\n1、按成绩段删除节点;2、按学号删除数据;3、退出;\n");
					scanf("%d",&n);
					if(n!=3)
					{
						switch(n)
						{
						case 1:
						key=toKey();
						p=SearchBST(root,key);	
						if (p!=NULL)
							{	
								root=removeNode(root,key);
								printf("节点已删除，当前中序遍历结果如下:\n");
								inorder(root);
							}
							else printf("没有这个节点.\n");
							break;
						case 2:		
								root=removeStu(root);
								break;
						}
					}
					else break;
					} 
					break;
			case 4:
				printf("中序遍历如下:\n");
				inorder(root);
				break;
			case 5:	
				printf("层次遍历如下:\n");
				LevelOrder(root);
				break;
			case 6:	
				inorder_clew(root);
				printf("中序线索化成功！\n");
				break;
			case 7:	
				BSTWrite(root);
				break;
			case 8:
				root=BSTRead();
				break;
			case 9:
				while(1){
					printf("\n请选择操作序号:\n");
					printf("\t\t 1、按学号检索学生成绩\n");
					printf("\t\t 2、按姓名检索学生成绩\n");
					printf("\t\t 3、按成绩检索学生人数\n");
					printf("\t\t 4、按成绩段检索学生信息\n");
					printf("\t\t 5、退出;\n");
					scanf("%d",&n);
					if(n!=5){
						switch(n){
						case 1:
							IdSearch(root);
							break;
						case 2:
							NameSearch(root);
							break;
						case 3:
							MarkSearch(root);
							break;
						case 4:
							KeySearch(root);
							break;
						}
					}
					else break;
				} 
				break;
			case 10:
			printf("年级总学生数为：%d\n",	AmountStu(root));
				break;
			case 11:
				printf("年级学生成绩的平均值为：%f\n",AverageStu(root));
				printf("年级学生成绩的最高分为：%d\n",MaxStu(root));
				printf("年级学生成绩的最低分为：%d\n",MinStu(root));
				printf("年级学生成绩的方差为：%f\n",VarianceStu(root,AverageStu(root)));
				break;
			}
		}
		else break;
	}
	return 0;
}
/************************************************************************/
/*     由分数获得关键码                                                 */
/************************************************************************/
int BSTKey(int k)
{
	int key;
	if(k<50)key=0;
	if(k>=50&&k<=59)key=1;
    if(k>=60&&k<=65)key=2;
	if(k>=66&&k<=69)key=3;
	if(k>=70&&k<=75)key=4;
	if(k>=76&&k<=79)key=5;
	if(k>=80&&k<=85)key=6;
	if(k>=86&&k<=89)key=7;
	if(k>=90&&k<=95)key=8;
	if(k>=96&&k<=100)key=9;
	return key;
}
/************************************************************************/
/*     由分数段获得关键码                                               */
/************************************************************************/
int toKey()
{
	char s[5];
	printf("请输入成绩段:");
	while (1){
		scanf("%s",s);
		if (strcmp(s,"AA+")==0)	return 9;
		if (strcmp(s,"AA")==0)	return 8;
		if (strcmp(s,"A")==0)	return 7;
		if (strcmp(s,"B+")==0)	return 6;
		if (strcmp(s,"B")==0)	return 5;
		if (strcmp(s,"B-")==0)	return 4;
		if (strcmp(s,"C+")==0)	return 3;
		if (strcmp(s,"C")==0)	return 2;
		if (strcmp(s,"D")==0)	return 1;
		if (strcmp(s,"E")==0)	return 0;
		else printf("该成绩段不存在，请重新输入:");
	}
}
/************************************************************************/
/*     插入子函数（当节点不存在的时候插入节点）					    */
/************************************************************************/
BSTNode *INsertBST(BSTNode *root,BSTNode *r,BSTNode *s) 
{
	if (!r)
	{
		r=s;
		r->left=NULL;
		r->right=NULL;
		if(!root)return(r);
		if(r->key<root->key)root->left=r;
		else root->right=r;
		return(root);
	}
	else{
		if(s->key<r->key)INsertBST(r,r->left,s);
		else if(s->key>r->key)INsertBST(r,r->right,s);
		return root;
	}
}
/************************************************************************/
/* 插入函数 （当节点不存在的时候调用插入子函数，否则直接插入学生数组 ） */
/************************************************************************/
BSTNode *AddBST(BSTNode *root)  
{
	int k;																																																																									
	int key;
	BSTNode *p;
    printf("成绩:");
    scanf("%d",&k);
    key=BSTKey(k);
	p=SearchBST(root,key);	
	if(p==NULL)
	{
		p=(BSTNode*)malloc(sizeof(BSTNode));
		printf("学号:");
	    scanf("%s",p->stu[0].id);
     	printf("姓名:");
	    scanf("%s",p->stu[0].name);
		p->stu[0].mark=k;
		p->key=key;
		p->count=0;
		root=INsertBST(root,root,p);	
		p->count++;
		return(root);
	}
	else 
	{
		printf("学号:");
	    scanf("%s",p->stu[p->count].id);
     	printf("姓名:");
	    scanf("%s",p->stu[p->count].name);
		p->stu[p->count].mark=k;
		p->count++;
		return(root);
	}
}
/************************************************************************/
/*     创建函数			                                                */
/************************************************************************/
BSTNode *CreateBST()  //创建二叉树函数
{
	BSTNode *bt=NULL;
	int cmd;
	while(1)
	{
	    printf("1输入数据 2退出:");
        scanf("%d",&cmd);
		if (cmd==1)bt=AddBST(bt);
		if (cmd==2)break;
	}
	printf("创建成功！\n");
    return bt;
}
/************************************************************************/
/*     删除二叉排序树最小节点                                           */
/************************************************************************/
BSTNode *deletemin(BSTNode *&root)  
{
	BSTNode *temp;
	if(!root)return(0);
	if(root->left)return(deletemin(root->left));
	else{
		temp=root;
		root=root->right;
		return(temp);
	}
}
/************************************************************************/
/*       删除节点函数                                                     */
/************************************************************************/
BSTNode *removeNode(BSTNode *root,int key)					
{ 
	BSTNode *p,*temp;
	if(!root)return(NULL);
	if(root->key==key)
	{
		if(root->left==root->right)
		{
			free(root);
			return(NULL);
		}
		else
		{
			if(root->left==NULL)
			{
				p=root->right;
				free(root);
				return(p);
			}
			else
			{
				if (root->right==NULL)
				{
					p=root->left;
					free(root);
					return(p);
				}
				else
				{
					temp=deletemin(root->right);
					root->key=temp->key;
					return(root);
				}
			}
		}
	}
		else
		{
		if(root->key<key)root->right=removeNode(root->right,key);
		else root->left=removeNode(root->left,key);
		return(root);
		}
}
/************************************************************************/
/*     按学号删除学生函数（若删除后该节点无学生数据，删除该节点）       */
/************************************************************************/
BSTNode *removeStu(BSTNode *root)			
{
	BSTNode *stack[20],*p;
	int tt=0;
	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)
			{
			    tt=1;
				if (p->count==1){
					removeNode(root,p->key);
					printf("该学号已删除，当前中序遍历结果如下:\n");
					inorder(root);
					return root;
				}
				else
				{
					p->stu[i]=p->stu[p->count-1];
					p->count--;
				}
			}
		}
		if(p->right!=NULL){
			stack[top]=p->right;
			top++;
		}
		if(p->left!=NULL){
			stack[top]=p->left;
			top++;
		}
	}
	if (tt==1)
	{
		printf("该学号已删除，当前中序遍历结果如下:\n");
		inorder(root);
	}
	else printf("不存在该学号的学生\n");
	return root;

}
/************************************************************************/
/*     中序线索化函数                                                   */
/************************************************************************/
BSTNode *inorder_clew(BSTNode *root)
{
	BSTNode *p,*&rp=p,*pr=NULL,*s[M];
	int top=-1;
	long ia;
	p=root;
	for (;;)
	{
		while(p){top=push(s,p,top);p=p->left;}//在子树内寻找中序序列第一个元素
		if(top==-1)break;
		else
		{
			top=pop(s,rp,top);
			if(pr){                 //仅在整个树中序序列起点是为空
				if(!pr->right){
					ia=-(long)p;    //以补码为线索标记
					pr->right=(BSTNode *)ia;
				}
				else if (!p->left)
				{
					ia=-(long)pr;
					p->left=(BSTNode *)ia;
				}
			}
			pr=p;
			p=p->right;
		}
	}
	return 0;
}
/************************************************************************/
/*     进栈函数                                                         */