#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#define MAXSIZE 20
typedef struct TreeNode
{
int Num;//记录这个人的子女数
char name[20];//姓名
struct TreeNode *NextNode[MAXSIZE+1];//记录儿女结点
struct TreeNode *parent;//记录父亲结点
}TreeNode;
TreeNode *tree;
void CreateTree(TreeNode *T);//创建一个家谱
void PrintTree(TreeNode *T);//输出一个家谱
void AddMember(TreeNode *T);//添加一个成员
void DeleteMember(TreeNode *T);//删除一个成员
void DeleteNode(TreeNode *p);//删除一个结点，以及它的所有子结点
int Childth(TreeNode *T,char *names);//查找names是他父母的第几个孩子
TreeNode *FindMember(TreeNode *T,char *names);//查找某人信息
void PrintMember(TreeNode *T,char *names);//输出查找的人的信息
void FindChild(TreeNode *T,char *names);//查找某人孩子
TreeNode *FindParent(TreeNode *T,char *names);//查找父母
void FindBrother(TreeNode *T,char *names);//查找兄弟
void LevelOrder(TreeNode *T);//层次遍历
int Generation(TreeNode *T);//求该家谱发展了多少代
int max(int A[],int n);
int AllNo(TreeNode *T);//求该家族的总成员数目
void main()
{
TreeNode *parent;
char findname1[20],findname2[20],findname3[20],findname4[20];
tree=(TreeNode *)malloc(sizeof(TreeNode));
int k,g,x;char ch;
do{
printf("请输入你要进行的操作:\n");
printf("\t\t=============================================\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");//完成
printf("\t\t==6、查找孩子 ==7、查找兄弟 ==8、查找父母 ==\n");//完成
printf("\t\t==9、求该家族发展多少代以及总人口 ==\n");
printf("\t\t==10、退出 ==\n");
printf("\t\t=============================================\n");
scanf("%d",&k);
switch(k)
{
case 1:
printf("请输入姓名:");
scanf("%s",tree->name);
tree->parent=NULL;
CreateTree(tree);
printf("\n\t\t=====家谱树建立完成=========\n\n");
break;
case 2:
PrintTree(tree);
break;
case 3:
AddMember(tree);
break;
case 4:
DeleteMember(tree);
break;
case 5:
printf("输入你要查找人的名字:");
scanf("%s",findname4);
PrintMember(tree,findname4);
break;
case 6:
printf("输入你要查找人的名字:");
scanf("%s",findname1);
FindChild(tree,findname1);
printf("\n\n");
break;
case 7:
printf("输入你要查找人的名字:");
scanf("%s",findname3);
FindBrother(tree,findname3);
printf("\n\n");
break;
case 8:
printf("输入你要查找人的名字:");
scanf("%s",findname2);
parent=(TreeNode *)malloc(sizeof(TreeNode));
parent=FindParent(tree,findname2);
if(parent==NULL) printf("\n\t===你查找的人没有父母，他是家族第一代!===\n");
else
printf("\n\t====你要查找的人的父母已找到:===\n\t===%s父母是:%s===\n",findname2,parent->name);
break;
case 9:
if(tree==NULL) printf("\n\t===该家族已经发展了0代===\n");
else
{
g=Generation(tree);x=AllNo(tree);
printf("\n\t===该家族已经发展了%d代===\n",g);
//printf("\t===该家族总人数有%d====\n",x);x=1;//ERROR
printf("\t===该家族的人分别是====\n");
LevelOrder(tree);
}
break;
default:
break;
}
printf("\n\n\t\t==按任意键返回主菜单==\n\t\t");
fflush(stdin);
scanf("%c",&ch);
}while(k!=10);
}
/***********************1.创建***********************/
/***********************检测完毕***********************/
void CreateTree(TreeNode *T)
{
int i;
TreeNode *p;
printf("请输入%s子女的数目:",T->name);
scanf("%d",&(T->Num));
if(T->Num!=0)
{
for(i=1;i<=T->Num;i++)
{
p=(TreeNode *)malloc(sizeof(TreeNode));
printf("\n请输入%s的第%d个子女的名字:",T->name,i);
scanf("%s",p->name);
p->Num=0;
p->parent=T;
T->NextNode[i]=p;
CreateTree(T->NextNode[i]);//递归创建孩子树
}
}
}
/***********************2.输出***********************/
/***********************检测完毕***********************/
void PrintTree(TreeNode *T)
{
int i;
printf("\n姓名:%s",T->name);
printf("\n孩子:");
for(i=1;i<=T->Num;i++)
{
if(T->Num!=0)
{
printf("%-10s",T->NextNode[i]->name);
}
else
printf("NULL");
}
printf("\n===================================\n");
for(i=1;i<=T->Num;i++)
{
PrintTree(T->NextNode[i]);//递归输出孩子树
}
}
/***********************3.添加***********************/
/***********************检测完毕***********************/
void AddMember(TreeNode *T)
{
char hisparents[20];
TreeNode *p,*newp;
newp=(TreeNode *)malloc(sizeof(TreeNode));
printf("请输入添加人的姓名:");
scanf("%s",newp->name);
newp->Num=0;
if(FindMember(T,newp->name)!=NULL)
printf("\t===你要添加的人已经存在===");
else
{
int i;
printf("输入%s的父母姓名:",newp->name);
scanf("%s",hisparents);
p=(TreeNode *)malloc(sizeof(TreeNode));
p=FindMember(T,hisparents);
i=p->Num+1;
p->NextNode[i]=newp;
p->Num=i;
newp->parent=p;
}
printf("\t\t===添加人员完成===\n");
}
/***********************4.删除***********************/
/***********************检测完毕***********************/
void DeleteMember(TreeNode *T)
{
int k;
TreeNode *p1,*p2;
p1=(TreeNode *)malloc(sizeof(TreeNode));
p2=(TreeNode *)malloc(sizeof(TreeNode));
char hisname[20];
printf("请输入你要删除人的姓名:");
scanf("%s",hisname);
k=Childth(T,hisname);
if(FindMember(T,hisname)==NULL)
printf("\t===你要删除的人不存在!===\n");
else
{
p1=FindMember(T,hisname);
p2=p1->parent;
DeleteNode(p2->NextNode[k]);//删除第k个孩子的所有结点
p2->NextNode[k]=(TreeNode *)malloc(sizeof(TreeNode));
for(int i=k;i<p2->Num;i++)
{
//从第k个孩子开始，往前移一位
p2->NextNode[i]=p2->NextNode[i+1];
}
p2->Num--;
}
printf("\t===删除人员操作完成!===\n");
}
/***********************检测完毕***********************/
TreeNode *FindMember(TreeNode *T,char *names)
{
TreeNode *p;
p=(TreeNode *)malloc(sizeof(TreeNode));
if(strcmp(T->name,names)==0)
return T;
else
{
for(int i=1;i<=T->Num;i++)
{
p=FindMember(T->NextNode[i],names);
if(p!=NULL)
return p;
}
}
return NULL;
}
/***********************检测完毕***********************/
void DeleteNode(TreeNode *p)
{
if(p->Num==0)
{
free(p);
}
else if(p->Num!=0)
{
for(int i=1;i<=p->Num;i++)
{
p->Num--;
DeleteNode(p->NextNode[i]);
}
}
}
/***********************检测完毕 ***********************/
int Childth(TreeNode *T,char *names)
{
int i,n;
TreeNode *p1,*p2;
p1=(TreeNode *)malloc(sizeof(TreeNode));
p2=(TreeNode *)malloc(sizeof(TreeNode));
p1=FindMember(T,names);
p2=p1->parent;
for(i=1;i<=p2->Num;i++)
{
if(p2->NextNode[i]==p1)
{n=i;break;}
}
return n;
}
/***********************5.查找某人信息***********************/
/***********************检测完毕************************/
void PrintMember(TreeNode *T,char *names)
{
int i=0;
TreeNode *p,*p1;
p=(TreeNode *)malloc(sizeof(TreeNode));
p1=(TreeNode *)malloc(sizeof(TreeNode));
p=FindMember(T,names);
p1=FindParent(T,names);
if(p1==NULL && p!=NULL) printf("\n\t===他是家族的第一代成员，没有父母和兄弟!===\n");
else{
printf("\n\t====他有%d个兄弟,%d个孩子====\n",p1->Num-1,p->Num);
while(p!=NULL)
{
p=p->parent;i++;
}
printf("\t\t===他是家族的第%d代成员!===\n\n",i);
}
}
/***********************6.查找孩子***********************/
/***********************检测完毕************************/
void FindChild(TreeNode *T,char *names)//6
{
TreeNode *p;
p=(TreeNode *)malloc(sizeof(TreeNode));
p=FindMember(T,names);
if(p==NULL) printf("\n\t===你要查找的人不存在!===");
else{
if(p->Num==0) printf("\n\t===你查找的人还没有孩子===\n");
else{
printf("\n\t===你要查找的人有%d个孩子.===\n\t===孩子分别是:",p->Num);
for(int i=1;i<=p->Num;i++)
{
printf("%-10s",p->NextNode[i]->name);
}
}
}
}
/***********************8.查找父母***********************/
/***********************检测完毕***********************/
TreeNode *FindParent(TreeNode *T,char *names)
{
TreeNode *p1,*p2;
p1=(TreeNode *)malloc(sizeof(TreeNode));
p2=(TreeNode *)malloc(sizeof(TreeNode));
p1=FindMember(T,names);
if(p1==NULL)
{printf("\n\t===你要查找的人不存在!==="); return NULL;}
else
{
p2=p1->parent;
return p2;
}
}
/***********************7.查找兄弟***********************/
/************************检测完毕***********************/
void FindBrother(TreeNode *T,char *names)
{
TreeNode *p;
int k;int i;
p=(TreeNode *)malloc(sizeof(TreeNode));
if(FindMember(T,names)==NULL)printf("\n\t\t你要查找的人不存在\n");
p=FindParent(T,names); //p为names的父母
if(p==NULL)
printf("\n\t===你查找的人没有父母，也没有兄弟!===");
else
{
k=Childth(T,names); //第k个孩子
if(p->Num==1)printf("\n\t===%s没有兄弟===\n",names);
else
{
printf("%s的兄弟是:",names);
for(i=1;i<k;i++)
printf("%-10s",p->NextNode[i]->name);
if(k<p->Num)
{
for(i=k+1;i<=p->Num;i++)
printf("%-10s",p->NextNode[i]->name);
}
}
}
}
/***********************9.代数***********************/
/***********************/
//int a[20]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
int i=0,j,n;
int Generation(TreeNode *T)
{
int a[20]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
//if(T==NULL) {n=0;}
//printf("%d",T->Num);
//if(T->Num==0) {a[i]=a[i]+0;n=a[i];}
//else
if(T->Num!=0)
{
//a[i]++;
//printf(" ~a[%d]=%d~",i,a[i]);
for(j=1;j<=T->Num;j++,i++)
{
a[i]=Generation(T->NextNode[j]);
//i++;
}
//a[i]++;
//printf(" !a[%d]=%d!",i,a[i]);
}
n=max(a,20)+1;
return n;
}
int max(int A[],int n)
{
int m;
m=A[0];
for(int j=1;j<n;j++)
{
if(m<A[j])
m=A[j];
}
return m;
}
/*******************/
int m=1;
int AllNo(TreeNode *T)
{
if(T->Num!=0 &&T->Num>0) m=m+T->Num;
for(int i=1;i<=T->Num;i++)
{
m=AllNo(T->NextNode[i]);
}
return m;
}
/****************层次遍历********************/
void LevelOrder(TreeNode *T)
{
int m=0;
TreeNode *p;
TreeNode *qu[MAXSIZE];
int rear,front;
p=(TreeNode *)malloc(sizeof(TreeNode));
//qu=(TreeNode)malloc(sizeof(TreeNode));
front=rear=-1;
rear++;
qu[rear]=T;
printf("\t");
while(front!=rear)
{
front=(front+1)%MAXSIZE;
p=qu[front];
printf("%-4s",p->name);m++;
for(int i=1;i<=p->Num;i++)
{
rear=(rear+1)%MAXSIZE;
qu[rear]=p->NextNode[i];
}
}
printf("\n\t===该家族总人口数是:%d===\n",m);
}