📄 tree_structure.h
字号:
#include "iostream.h"
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "common.h"
#define M 10
//学生节点
struct student{
int _Mark;
char _Name[10];
char _Number[10];
};
//节点
struct tree {
int key;//关键码
int sum;//学生总数
// <50，50-59，60-65， 66-69，70-75，76-79，80-85，86-89，90-95，96-100
// E， D， C， C+， B-， B， B+， A， AA， AA+
// key=0, 1, 2, 3, 4, 5, 6, 7, 8, 9
struct student stu[20];
struct tree *left,*right;
};
//插入节点函数，节点的关键值是成绩段
//参数：根节点，插入节点，插入位置
//返回：根节点
//调试成功：5-1 17：46
struct tree* _add_tree(struct tree*root,struct tree*r,int mark,int key){
if (r==NULL) {
r=new struct tree;
r->key=key;
r->sum=0;
r->stu->_Mark=mark;
cout<<"请输入姓名"<<endl;
fflush(stdin);
gets(r->stu->_Name);
cout<<"请输入学号"<<endl;
gets(r->stu->_Number);
r->left=NULL;
r->right=NULL;
if(!root){
return r;
}
else if(r->key>root->key){
root->right=r;
// root->left=NULL;
}
else {
root->left=r;
// root->right=NULL;
}
return root;
}
else{
if (key>(r->key))_add_tree(r,r->right,mark,key);
else if(key<(r->key))_add_tree(r,r->left,mark,key);
else{//插入到本节点
int i=0;
while (r->stu[i]._Mark<mark && i<=r->sum) i++;
(r->sum)++;
if(i==r->sum) r->stu[i]._Mark=mark;
else{
int j;
for(j=r->sum;j>i;j--)
r->stu[j]=r->stu[j-1];//全部后移
r->stu[i]._Mark=mark;
}
cout<<"请输入姓名"<<endl;
fflush(stdin);
gets(r->stu[i]._Name);
cout<<"请输入学号"<<endl;
gets(r->stu[i]._Number);
}return r;
}
}
//初始化函数，把二叉树的结构进行搭建
//形成按照成绩段排布的二叉树结构
//参数：无
//返回：根节点
//调试成功：5-1 17：46
struct tree *_init_tree(){
int i=0,mark=0;
struct tree *p=NULL;
struct tree *root=NULL;
for (;i<20;i++){
cout<<"请输入成绩(0就退出)"<<endl;
cin>>mark;
if(!mark)return root;
root=_add_tree(root,root,mark,mark2key(mark));
}
return root;
}
//删除辅助函数
//参数：跟节点
//
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*removehelp(struct tree*root,int key)
{
struct tree*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;
root->sum=temp->sum;
for(int i=0;i<=temp->sum;i++){
root->stu[i]=temp->stu[i];
}
return root;
}
}
}
}
else{
if(root->key<key)root->right=removehelp(root->right,key);
else root->left=removehelp(root->left,key);
return root;
}
}
//学生删除
//参数：指定学号
//
struct tree*remove_stu (struct tree *root,char *num)
{
struct tree **vec,*r=root;
int front=0,rear=0,i,j,flag=0;
vec=(struct tree**)malloc(11*(sizeof(struct tree *)));//把所有节点都装载在这个数组里边
*(vec+rear)=r;
rear++;
while (front<rear) //考虑了可能重名的情况
{
r=*(vec+front);
front++;
if (r->left)
{
*(vec+rear)=r->left;
rear++;
}
if (r->right)
{
*(vec+rear)=r->right;
rear++;
}
i=0;
while (i<=r->sum && flag==0)
{
if (strcmp(num,r->stu[i]._Number)==0)
{
(r->sum)--;
for (j=i;j<=r->sum;j++)
r->stu[j]=r->stu[j+1];
flag=1;//可以跳出循环
}
i++;
}
if (r->sum==-1) //若节点中已无任何学生，则可以删除节点
root=removehelp(root,r->key);
};
//if(!flag)return NULL;//如果没有找到，就返回0；
return(root);
}
//辅助输出函数
//参数：节点地址
//功能：输出所有信息
int _print (struct tree *root)
{
if(!root)return 0;
key2char(root->key);
cout<<": "<<endl;
for (int i=0;i<=root->sum;i++) //输出格式为"学号 姓名 成绩"
cout<<root->stu[i]._Number<<"\t"<<root->stu[i]._Name<<"\t"<<root->stu[i]._Mark<<endl;
return 1;
}
//中序遍历并输出函数
//中序遍历
struct tree*inorder(struct tree*root){
if(!root){
return 0;
}
inorder(root->left);
_print(root);
inorder(root->right);
return 0;
}
//学生总数统计函数
//返回学生总数
//参数：根节点
int _get_sum(struct tree*root){
//这样设计数据是否合适
int sum=0;
if(!root)return 0;
sum=sum+_get_sum(root->left);
sum=sum+_get_sum(root->right);
sum=root->sum+1+sum;
return sum;
}
//求所有分数之和
int total_mark(struct tree*root){
if (root)
{
int temp=0;
int i;
for (i=0;i<=root->sum;i++)
temp=temp+root->stu[i]._Mark;
return(temp+total_mark(root->left)+total_mark(root->right));
}
else return 0;
}
//层次遍历函数
//参数：根节点
//
int inorder_layer(struct tree*root){
if(!root)return 0;
struct tree**vec;
struct tree*r=root;
int front=0,rear=0;
vec=(struct tree**)malloc(11*sizeof(struct tree*));//指向指针的指针
*vec=root;
if(root)_print(root);
rear++;
while(front<rear){
r=*(vec+front);
front++;
if(r->left){
*(vec+rear)=r->left;
rear++;
_print(r->left);
}
if(r->right){
*(vec+rear)=r->right;
rear++;
_print(r->right);
}
//cout<<"这一层已经完毕"<<endl;
}
return 1;
}
//检索函数
//功能：按照关键码检索
int search_key(struct tree*root,int key){
if(!root)return 0;
if(root->key==key){
_print(root);
return 1;
}
if((root->key)>key)search_key(root->left,key);
else search_key(root->right,key);
return 1;
}
//检索函数
//功能：按照姓名检索
int search_name(struct tree*root,char name[10]){
if(!root)return 0;
int flag=0;
if((search_name(root->left,name)||search_name(root->right,name)))flag=1;
for(int i=0;i<=root->sum;i++){
if(!strcmp(name,root->stu[i]._Name)){
cout<<root->stu[i]._Number<<"\t"<<root->stu[i]._Name<<"\t"<<root->stu[i]._Mark<<endl;
flag=1;
}
}
if(flag)return 1;
return 0;//0表示这部分没有检索到
}
//检索函数
//功能：按照分数检索
int search_mark(struct tree*root,int mark){
int key=mark2key(mark),flag=0;
if(!root)return 0;
if(root->key==key){
for(int i=0;i<=root->sum;i++){
if(mark==root->stu[i]._Mark){
cout<<root->stu[i]._Number<<"\t"<<root->stu[i]._Name<<"\t"<<root->stu[i]._Mark<<endl;
flag=1;
}
}
if(!flag){
cout<<"检索失败，没有这个分数"<<endl;
return 0;
}
return 1;
}
if((root->key)>key)search_mark(root->left,mark);
else search_mark(root->right,mark);
return 1;
}
//检索函数
//按照学号检索
//返回有无检索到
int search_num(struct tree*root,char num[10]){
if(!root)return 0;
int flag=0;
if((search_num(root->left,num)||search_num(root->right,num)))flag=1;
for(int i=0;i<=root->sum;i++){
if(!strcmp(num,root->stu[i]._Number)){
cout<<root->stu[i]._Number<<"\t"<<root->stu[i]._Name<<"\t"<<root->stu[i]._Mark<<endl;
flag=1;
}
}
if(flag)return 1;
return 0;//0表示这部分没有检索到
}
//检索入口
//参数：跟节点
//功能：根据选择调用不同的函数
void search_path(struct tree*root){
int _flag=1,choice=0;
do{
cout<<"请选择你要检索的方式"<<endl;
cout<<"1 按照学号检索他的成绩"<<endl;
cout<<"2 按照姓名检索她的成绩"<<endl;
cout<<"3 指定一个分数检索同一成绩有多少学生"<<endl;
cout<<"4 指定一个分数范围（按成绩段整合）"<<endl;
cout<<"其他 退出"<<endl;
cin>>choice;
switch (choice)
{
case 1:
char num[10];
cout<<"请输入学号"<<endl;
cin>>num;
search_num(root,num);
break;
case 2:
char name[10];
cout<<"请输入姓名"<<endl;
cin>>name;
search_name(root,name);
break;
case 3:
int mark;
cout<<"请输入分数"<<endl;
cin>>mark;
search_mark(root,mark);
break;
case 4:
int key;
cout<<"请输入分数范围"<<endl;
cout<<"0 分数<50"<<endl;
cout<<"1 分数50-59"<<endl;
cout<<"2 分数60-65"<<endl;
cout<<"3 分数66-69"<<endl;
cout<<"4 分数70-75"<<endl;
cout<<"5 分数76-79"<<endl;
cout<<"6 分数80-85"<<endl;
cout<<"7 分数86-89"<<endl;
cout<<"8 分数90-95"<<endl;
cout<<"9 分数96-100"<<endl;
cin>>key;
if((key<0)||(key>9)){
cout<<"没有这个分数段"<<endl;
break;
}
search_key(root,key);
break;
default:
fflush(stdin);
_flag=0;
break;
}
}while(_flag);
}
//求平均值函数
//参数：节点
double average(struct tree*root){
double _sum=0,_mark=0;
if(!(_sum=(double)_get_sum(root))){
cout<<"总数为零"<<endl;
return 0;
}
_mark=(double)total_mark(root);
return _mark/_sum;
}
//求方差辅助函数
//返回值：各分数与平均值的平方和
double fch_help(struct tree*root){
if (root)
{
double temp=0;
int i;
double average_root=average(root);
for (i=0;i<=root->sum;i++)
temp+=((double)root->stu[i]._Mark-average_root)*((double)root->stu[i]._Mark-average_root);
return(temp+fch_help(root->left)+fch_help(root->right));
}
else return 0;
}
//求方差函数
//参数：节点
double fch(struct tree*root){
double temp1=fch_help(root);
double temp2=(double)_get_sum(root);
return temp1/temp2;
}
//求最大值最小值
//
void _Max_Min(struct tree*root){
struct tree *p=root,*q=root;
while (p)
{
q=p;
p=p->right;
}
if (q) cout<<"成绩最小值为: "<<q->stu[q->sum]._Mark<<endl;
else cout<<"树为空!"<<endl;
p=q=root;
while (p)
{
q=p;
p=p->left;
};
if (q) cout<<"成绩最大值为: "<<q->stu[0]._Mark<<endl;
else cout<<"树为空!"<<endl;
}
//二叉树存盘辅助韩素
int save_tree_help(struct tree*root,FILE *fp){
if(!root)return 0;
fwrite(root,sizeof(struct tree),1,fp);
save_tree_help(root->left,fp);
save_tree_help(root->right,fp);
return 1;
}
//二叉树存盘
//参数：根节点
int save_tree(struct tree*root){
char location[10];
cout<<"请输入所要保存的文件名"<<endl;
cin>>location;
FILE *fp;
if(!(fp=fopen(location,"wt"))){cout<<"文件无法打开"<<endl;return 0;}
save_tree_help(root,fp);
fclose(fp);
return 1;
}
//二叉树恢复辅助函数
//
struct tree*load_tree_help(FILE*fp){
struct tree*root=(struct tree*)malloc(sizeof(struct tree));
fread(root,sizeof(struct tree),1,fp);
if(!root)return 0;
if(root->left)root->left=load_tree_help(fp);
if(root->right)root->right=load_tree_help(fp);
return root;
}
//二叉树恢复函数
//
struct tree* load_tree(struct tree*root){
char location[10];
cout<<"请输入所要恢复的文件名"<<endl;
cin>>location;
FILE *fp;
if(!(fp=fopen(location,"rt"))){cout<<"文件无法打开"<<endl;return 0;}
root=load_tree_help(fp);
fclose(fp);
return root;//绝对必要的
}
//建堆函数
//push
int push(struct tree*p[M],struct tree*x,int top){
// struct tree*r=p;
if(top==M-1)printf("Overflow");
else{
top++;
// r=p+top;
// *r=*x;
*(p+top)=x;
//*(p+top)=x;
}
return top;
}
//弹出函数
int pop(struct tree*p[M],struct tree*&x,int top){
if(top<0)printf("Overflow");
else{
x=*(p+top);
top--;
}
return top;
}
//中序线索化树之后的节点遍历函数
struct tree*clewprintf(struct tree*root){
struct tree*q,*p;
long ia;
q=root;p=q;
while(q){p=q;q=q->left;}
while(1){
_print(p);
if(!p->right)return 0;
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;
}
}
}
//中序线索化函数
struct tree*inorder_clew(struct tree*root)
{
struct tree*p,*&rp=p,*pr=NULL,*s[M],*temp;
int top=-1;
long ia;
p=root;
temp=(struct tree*)s;//课本上的BUG
for(;;){
while(p){top=push(s,rp,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;
}
}
clewprintf(root);
return 0;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -