二叉树.cpp

二叉排序树

#include<iostream>
#include<fstream>
#include<iomanip>
#include<string>
#include<cstring>
using namespace std;
struct tree
{
	int num;
    char name[20];
	int score;
	char ch[4];
	struct tree *left,*right;
};

struct tree *creat(struct tree *root);      //新建二叉树
void panduan(int score,char ch[4]);       //匹配成绩段
void inorder(struct tree *root);          //中序遍历
void inorder1(struct tree *root);          //层次遍历
void inorder2(struct tree *root);          //线索化后遍历
struct tree *deletemin(struct tree *&root);   //寻找最小节点
struct tree *deletnum(struct tree *&root,int num);          //按学号删除
struct tree *insert(struct tree *root,struct tree *s);       //插入
struct tree *inorder_clew(struct tree *root);       //线索化
void re(struct tree *root);          //反线索化
int push(struct tree **s,struct tree *p,int top);  //入栈
int pop(struct tree **s,struct tree *&p,int top);  //出栈
int ct(struct tree *root);      //节点计数
void save (struct tree *root);   //保存
void back (tree *&root);  //恢复
void search (struct tree *root);  //检索
void searchnum(struct tree *root,int num); //学号检索
void searchscore(struct tree *root,int score); //分数检索
void searchname(struct tree *root,char *name); //姓名检索
void searchch(struct tree *root,char *ch);  //关键码检索
void scoreall(struct tree *root);    //关于成绩
float Aver(struct tree *root);   //平均值
int Max(struct tree *root);        //最大值
int Min(struct tree *root);         //最小值
float fangcha(struct tree *root,float aver); //方差
void main()
{
  int i;
  struct tree *root,*s;
  root=NULL;
  int score,num,count;
  cout<<"输入您的选择："<<endl;
  cout<<"0.退出      1.新建   2.插入         3.删除          4.中序线索化   5.中序遍历 "<<endl;
  cout<<"6.层次遍历  7.检索   8.学生总数统计 9.学生成绩统计  10.存盘        11.从文件恢复"<<endl;
  cin>>i;
  while (i!=0) {
  switch(i) {
  case 0: 
    	break;
  case 1:
 	    root=creat(root);
  	    break;
  case 2:	 
		s=(struct tree *)malloc(sizeof(tree));
		cout<<"请输入学生信息，学号，姓名，成绩"<<endl;
		cin>>s->num>>s->name>>s->score;	
		s->left=NULL;
		s->right=NULL;
		panduan(s->score,s->ch);
		root=insert(root,s);
		cout<<"插入成功"<<endl;
		break;
  case 3:	
		cout<<"输入要删除学生的学号"<<endl;
	    cin>>num;
		s=deletnum(root,num);
		if(!s)
		{
			cout<<"无此学号学生"<<endl;
		}
		else
		{	
		cout<<"删除成功，被删除学生信息如下:"<<endl;
        cout<<setw(10)<<"学号"<<setw(15)<<"姓名"<<setw(15)<<"成绩"<<setw(10)<<"关键码"<<endl;
		cout<<setw(10)<<s->num<<setw(15)<<s->name<<setw(15)<<s->score<<setw(10)<<s->ch<<endl;
		}
		break;
  case 4:
	    root=inorder_clew(root);
		cout<<"线索化成功"<<endl;
		cout<<setw(10)<<"学号"<<setw(15)<<"姓名"<<setw(15)<<"成绩"<<setw(10)<<"关键码"<<endl;
    	inorder2(root);
		re(root);
		break;
  case 5:
	    if(root==NULL) {cout<<"空树"<<endl;break;}
	    cout<<setw(10)<<"学号"<<setw(15)<<"姓名"<<setw(15)<<"成绩"<<setw(10)<<"关键码"<<endl;
	    inorder(root);
	    break;	 
  case 6:
	    if(root==NULL) {cout<<"空树"<<endl;break;}
	    cout<<setw(10)<<"学号"<<setw(15)<<"姓名"<<setw(15)<<"成绩"<<setw(10)<<"关键码"<<endl;
	    inorder1(root);
		break;
  case 7:
	    search(root);
	    break;
  case 8:
	   count=ct(root);
	   cout<<"总节点数为："<<count<<"个"<<endl;
	   break;
  case 9:
	    scoreall(root);
		break;
  case 10:
	   save(root);
	   break;
  case 11:
	   back(root);
	   break;
  default:break;
  
  }
  cout<<"输入您的选择："<<endl;
  cout<<"0.退出      1.新建   2.插入         3.删除          4.中序线索化   5.中序遍历 "<<endl;
  cout<<"6.层次遍历  7.检索   8.学生总数统计 9.学生成绩统计  10.存盘        11.从文件恢复"<<endl;
  cin>>i;
}
}
struct tree *creat(struct tree *root)       //新建二叉树
{
	struct tree *s;
	int num,score,i;
	char name[20];
	cout<<"输入按1，退出按0"<<endl;
	cin>>i;
    while(i!=0) 
	{
	s=(struct tree *)malloc(sizeof(tree));
	cout<<"请输入学生信息，学号，姓名，成绩"<<endl;
    cin>>num>>name>>score;
	s->num=num;
	strcpy(s->name,name);
	s->score=score;
	panduan(score,s->ch);
	s->left=NULL;
	s->right=NULL;
	root=insert(root,s);
	cout<<"输入按1，退出按0"<<endl;
	cin>>i;
	}
	return root;
}

struct tree *insert(struct tree *root,struct tree *s) //插入函数
{
    if(root==NULL) {root=s;root->left=NULL;root->right=NULL;}
	else if(s->score<=root->score) root->left=insert(root->left,s);
	else if(s->score>root->score) root->right=insert(root->right,s);
	return root;
}

void panduan(int score,char ch[4])        //匹配成绩段
{
	if(score<50) strcpy(ch,"E");
	else if(score>=50&&score<=59) strcpy(ch,"D");
	else if(score>=60&&score<=65) strcpy(ch,"C");
	else if(score>=66&&score<=69) strcpy(ch,"C+");
	else if(score>=70&&score<=75) strcpy(ch,"B-");
	else if(score>=76&&score<=79)strcpy(ch,"B");
	else if(score>=80&&score<=85) strcpy(ch,"B+");
	else if(score>=86&&score<=89) strcpy(ch,"A");
	else if(score>=90&&score<=95) strcpy(ch,"AA");
	else  strcpy(ch,"AA+");
}

void inorder(struct tree *root)       //中序遍历
{
	if(root->left) inorder(root->left);
	cout<<setw(10)<<root->num<<setw(15)<<root->name<<setw(15)<<root->score<<setw(10)<<root->ch<<endl;
	if(root->right) inorder(root->right);
}

struct tree *deletemin(struct tree *&root)       //寻找二叉树最小节点
{
	struct tree *temp;
	if(!root) return(0);
	if(root->left) return(deletemin(root->left));
	else
	{
		temp=root;
		root=root->right;
		return (temp);
	}
}


struct tree *deletnum(struct tree *&root,int num)     //按学号删除
{
 	if(!root)return NULL;
	tree *temp;
	if(root->num==num)
	{
		temp=root;
		if(!(root->left)&&!(root->right))  
		{
			root=NULL;
            return temp;
		}
		if(!(root->left))  
		{
			root=root->right;
			return temp;
		}
		if(!(root->right))  
		{
			root=root->left;
			return temp;
		}
		root=deletemin(root->right); 
		root->left=temp->left;
		root->right=temp->right;
		return temp;
	}
	temp=deletnum(root->left,num); 
	if(temp)return temp;
	temp=deletnum(root->right,num);
	return temp;
}

struct tree *inorder_clew(struct tree *root)    //线索化
{
	struct tree *p,*&rp=p,*pr=NULL,*s[100];
	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=(struct tree *)ia;
				}
		    	else if(!p->left)
				{
				ia=-(long)pr;
				p->left=(struct tree *)ia;

				}
			}
			pr=p;
			p=p->right;
		}
	}
		return root;
}

int push(struct tree **s,struct tree *p,int top)  //入栈
{
	top++;
	*(s+top)=p;
	return top;
}

int pop(struct tree **s,struct tree *&p,int top)       //出栈
{
	p=*(s+top);
	top--;
	return top;
}

void inorder2(struct tree *root1)         //线索化后遍历
{
	struct tree *p,*q;
    long ia;
	q=root1;p=q;
	while (q)
	{
      p=q;
	  q=q->left;
	}
	for(;;)
	{
       cout<<setw(10)<<p->num<<setw(15)<<p->name<<setw(15)<<p->score<<setw(10)<<p->ch<<endl;
	   if(!p->right) break;
	   if((long)p->right<0)
	   {
		   ia=-(long)p->right;
		   p=(struct tree *)ia;
	   }
	   else
	   {
		   p=p->right;
		   while((long)p->left>0) p=p->left;
	   }
	}
}

void re(struct tree *root) //反线索化
{
	if(!root)return;
	tree *q,*p;
	long ia;
	q=root;
	p=q;
	while(q)  
	{
		p=q;
		q=q->left;
	}
	while(1)
	{
		if((long)p->left<0)p->left=NULL;   
		if(!p->right)return; 
		if((long)p->right<0)
		{
			ia=-(long)p->right;
			p->right=NULL;    
			p=(tree *)ia;
		}
		else
		{	
			p=p->right;
			while((long)p->left>0)p=p->left;                   
		}
	}
  }
 

int ct(struct tree *root)   //总人数计算
{
	int num1, num2;
	if(root==NULL) return 0;
	else if(root->left==NULL&&root->right==NULL)  return 1;
    else
	{
		num1=ct(root->left);
		num2=ct(root->right);
		return (num1+num2+1);
	}
}

void save (struct tree *root)   //存入文件
{
	ofstream ofile;
	int i;
	ofile.open("tree.txt",ios::out);
	if(!ofile)
	{
		cout<<"打开文件失败"<<endl;
		exit(-1);
	}
	i=ct(root);
	ofile<<i<<endl;
	tree *q[100];
	int front=0,rear=0;
	tree *p;
	if(root!=NULL)
	{
		rear=(rear+1)%100;