//头文件
//tree.h
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define MaxSons 3
typedef char ElemType;
typedef struct node
{
ElemType data[15]; //结点的值
struct node *sons[MaxSons]; //指向孩子结点
}TSonNode; //孩子链存储结构中的结点类型
typedef struct
{
char N[15];
char n[15];
}array;
//读取文件内容到数组R中
void ReadFile(array R[],FILE *fp,int &n)
{
while((fscanf(fp,"%s",R[n].N))!=EOF&&(fscanf(fp,"%s",R[n].n))!=EOF)
n++;
}
//创建一颗树
TSonNode *CreateTree(char str[],array R[],int n)
{
TSonNode *t;
int k,i=0,j=0;
t=(TSonNode *)malloc(sizeof(TSonNode));
strcpy(t->data,str);
for(k=0;k<MaxSons;k++)
t->sons[k]=NULL;
while(i<n)
{
if(strcmp(R[i].N,str)==0)
{
t->sons[j]=CreateTree(R[i].n,R,n);
j++;
}
i++;
}
return t;
}
//输出树(孩子链存储结构)
void DispTree(TSonNode *t)
{
int i=0;
if(t==NULL)
printf("此树为空树!\n");
else
{
printf("%s",t->data);
if(t->sons[i]!=NULL) //若t结点至少有一个孩子
{
printf("(");
for(i=0;i<MaxSons;i++)
{
DispTree(t->sons[i]);
if(t->sons[i+1]!=NULL)
printf(",");
else
break;
}
printf(")");
}
}
}
//销毁树
void DestroyTree(TSonNode *t)
{
if(t==NULL)
printf("此树为空树!\n");
else
{
for(int i=0;i<MaxSons;i++)
{
if(t->sons[i]!=NULL)
DestroyTree(t->sons[i]);
else
break;
}
free(t);
}
}
//查找某一结点
TSonNode *FindNode(TSonNode *t,char str[])
{
TSonNode *p;
if(t==NULL)
return NULL;
else
{
if(strcmp(t->data,str)==0)
return t;
else
{
for(int i=0;i<MaxSons;i++)
{
if(t->sons[i]!=NULL)
{
p=FindNode(t->sons[i],str);
if(p!=NULL)
return p;
}
}
return NULL;
}
}
}
//求某一结点的孩子个数
int ChildCount(TSonNode *p)
{
int count=0;
for(int i=0;i<MaxSons;i++)
{
if(p->sons[i]!=NULL)
count++;
else
break;
}
return count;
}
//求某棵树中的叶子结点数
//本例中，叶子结点数等于班级数,一个叶子结点对应一个班级
int LeafCount(TSonNode *p)
{
int count=0;
if(p==NULL)
return 0;
else
{
if(p->sons[0]==NULL)
count++;
else
{
for(int i=0;i<MaxSons;i++)
{
if(p->sons[i]!=NULL)
count=count+LeafCount(p->sons[i]);
else
break;
}
}
}
return count;
}
//求某棵树的叶子结点值的和
int LeafSumOfvalue(TSonNode *p)
{
int sum=0;
if(p==NULL)
return 0;
else
{
if(p->sons[0]==NULL)
return atoi(p->data);
else
{
for(int i=0;i<MaxSons;i++)
{
if(p->sons[i]!=NULL)
sum+=LeafSumOfvalue(p->sons[i]);
else
break;
}
}
}
return sum;
}
//源文件
//exp7.cpp
#include<stdio.h>
#include<stdlib.h>
#include"tree.h"
#define MaxSize 66
int main()
{
int n=0;
TSonNode *t;
array R[MaxSize];
FILE *fp;
if((fp=fopen("table.txt","r"))==NULL) //以只读方式打开table.txt文件
{
printf("error!cannot open the file!");
exit(1);
}
printf("读取文件内容存入数组R中\n");
ReadFile(R,fp,n);
printf("输出数组R:\n");
for(int i=0;i<n;i++)
printf("%s %s\n",R[i].N,R[i].n); //输出R数组查看是否读取正确
printf("\n由数组R创建树T,");
t=CreateTree(R[0].N,R,n); //创建一颗树
printf("由括号表示输出树T:\n");
DispTree(t);
char str[10];
printf("\n请输入学院名:");
scanf("%s",str);
printf("\n%s的专业数:%d\n",str,ChildCount(FindNode(t,str)));
printf("%s的班级数:%d\n",str,LeafCount(FindNode(t,str)));
printf("\n请输入学院名:");
scanf("%s",str);
printf("\n%s的学生数:%d\n",str,LeafSumOfvalue(FindNode(t,str)));
printf("销毁树!\n");
DestroyTree(t);
return 0;
}
