题目：用二叉树实现家谱的相关运算
/实验14—2 设计一个程序，采用二叉树表示一个家谱关系。要求程序具有如下功能：
（1） 文件操作功能：记录输入、记录输出，清除全部文件记录和将家谱记录存盘。
（2） 家谱操作功能：用括号表示法输出家谱二叉树，查找某人所有的儿子，查找某人所有的祖先。/
#include<iostreamh>
#include<stdlibh>
#include<stdioh>
#include<stringh>
typedef struct Node
{
int degree;//人员所在代数
char data;//人员标志
struct Node lchild;//data的孩子
struct Node rchild;//data的兄弟
}BTNode;
#define max 100
int choose;
char X;
void CreatBTNode(BTNode b,char str);//创建记录
BTNode SearchX(BTNode b,char X);//查找记录
void InputBTNode(BTNode b,char str);//1记录输入
void OutputBTNode(BTNode b,char str);//2记录输出
void Store(BTNode b,char str);//3家谱记录存盘
void DispTree(BTNode b);//4用括号法输出家谱
void SearchXSon(BTNode b,char X);//5查找某人的儿子
void SearchXAncestor(BTNode b,char X);//6查找某人的祖先
void Distory(BTNode b,char str);//7清除全部文件记录
int main()
{BTNode b=NULL;
char str=(char)malloc(maxsizeof(char));
str[0]='\0';
cout<<"--------------------------------------------------------------------"<<endl;
cout<<"0退出"<<endl;
cout<<"1记录输入:\t"<<endl;
cout<<"2记录输出:\t"<<endl;
cout<<"3家谱记录存盘:\t"<<endl;
cout<<"4用括号法输出家谱:\t"<<endl;
cout<<"5查找某人的儿子:\t"<<endl;
cout<<"6查找某人的祖先:\t"<<endl;
cout<<"7清除全部文件记录:\n"<<endl;
cout<<"-------------------------------------------------------------------"<<endl;
cout<<"Please choose the operation you want to do "<<endl;
cout<<"choose=";
cin>>choose;
while(choose)
{switch(choose)
{
case 1:
InputBTNode(&b,str);break;
case 2:
OutputBTNode(&b,str);break;
case 3:
Store(b,str);
printf("文件已经保存!");
break;
case 4:
DispTree(b); break;
case 5:
printf("请输入需要查找儿子的结点:");
cin>>X;
SearchXSon(b,X);
break;
case 6:
printf("请输入需要查找祖先的结点:\n");
cin>>X;
BTNode p;
p=SearchX(b,X);
if(p!=NULL)
SearchXAncestor(b,X);
else
printf("该结点不存在!");
break;
case 7:
Distory(&b,str);
printf("文件记录已经清除!");
break;
default:
cout<<endl<<"Invalid input,input again";
}
cout<<endl<<"please choose again:"<<endl;
cout<<"the choose =";
cin>>choose;
}
return 0;
}
void CreatBTNode(BTNode b,char str) //创建树
{
BTNode S[max],p=NULL;
int top=-1,tag,j=0,d=0;
char ch;
b=NULL;
ch=str[j];
while(ch!='\0')
{
switch(ch)
{
case '(':
d++;
top++;
S[top]=p;
tag=1;break;
case ')':
top--;break;
case ',':
d--;
tag=2;break;
default:
p=(BTNode )malloc(sizeof(BTNode));
p->degree=d;
p->data=ch;
p->lchild=NULL;
p->rchild=NULL;
if((b)==NULL)(b)=p;
else
{
switch(tag)
{
case 1: S[top]->lchild=p;break;
case 2: S[top]->rchild=p;break;
}
}
}
ch=str[++j];
}
}
void InputBTNode(BTNode b,char str)//记录输入
{
do
{
printf("请输入需要输入的记录:\n");
gets(str);
if(str[0]=='\0')
printf("输入的记录为空，请再次输入:\n");
}while(str[0]=='\0');
CreatBTNode(b,str);
printf("记录创建成功!");
}
void OutputBTNode(BTNode b,char str)//从文件中读出记录
{
FILE fp;
if((fp=fopen("wangljtxt","r"))==NULL)
{
printf("不存在记录文件,要建立吗\n建立请输入Y，否则按其他键：");
if(getchar()=='Y')
{
fp=fopen("wangljtxt","w+");
printf("记录文件“wangljtxt”已建立\n");
}
else
exit(1);
}
else
{
if(!feof(fp))
fscanf(fp,"%s",str);
fclose(fp);
CreatBTNode(b,str);
printf("文件中记录已输出\n");
}
}
void Store(BTNode b,char str)//储存全部的结点记录
{
BTNode p;
p=b;
FILE fp;
fp=fopen("wangljtxt","w+");
if(fp==NULL)
{
printf("文件打开失败!");
return;
}
else
{
if(p!=NULL)
{
fprintf(fp,"%s",str);
fclose(fp);
}
}
}
void DispTree(BTNode b)//用括号法输出家谱记录
{
if(b!=NULL)
{printf("%c",b->data);
if(b->lchild!=NULL||b->rchild!=NULL)
{printf("(");
DispTree(b->lchild);
if(b->rchild!=NULL)
{printf(",");
DispTree(b->rchild);
}
printf(")");
}
}
else
printf("\0");
}
BTNode SearchX(BTNode b,char X)//查找结点X
{BTNode p;
if(b==NULL) return NULL;
else if(b->data==X) return b;
else
{
p=SearchX(b->lchild,X);
if(p!=NULL) return p;
else
{
return SearchX(b->rchild,X);
}
}
}
void SearchXSon(BTNode b,char X)//查找结点X的所有儿子
{
BTNode p,q;
p=SearchX(b,X); //找到节点X
if(p!=NULL)
{
p=p->lchild;
if(p==NULL) //X没有孩子
printf("节点%c没有儿子!",X);
else
{
printf("节点%c的所有儿子为:",X);
if(p!=NULL)
printf("%c ",p->data);
q=p->rchild;
while(q)
{
printf("%c ",q->data);
q=q->rchild;
}
}
}
else
printf("该结点不存在!");
}
void TraverseBT(BTNode b,int d)//遍历家谱
{
if(b!=NULL)
if(b->degree<d)
{
printf("%c ",b->data);
if(b->lchild!=NULL)
TraverseBT(b->lchild,d);
if(b->rchild!=NULL)
TraverseBT(b->rchild,d);
}
}
void SearchXAncestor(BTNode b,char X)//查找结点X的所有祖先
{
if(b==NULL)
{
printf("这是一棵空树!");
return ;
}
BTNode p=SearchX(b,X);
if(p->degree==0)
{
printf("X为根节点或其兄弟，没有祖先!");
return;
}
printf("%c结点的祖先有：",X);
TraverseBT(b,p->degree);
}
void Distory(BTNode b,char str)//清除全部的记录
{
(b)=NULL;
FILE fp;
fp=fopen("wangljtxt","w");
if(fp==NULL)
{
printf("打开文件失败!");
exit(1);
}
str="";
fclose(fp);
}
你懂的，同道中人！
父ID、嵌套集和祖先数组。保存家谱用父ID、嵌套集和祖先数组数据结构比较好，数据结构(Datastructures)是由若干数据成分按照一定方式构成的复合数据以及作用于其上的函数或运算。
题目：用二叉树实现家谱的相关运算
本文2023-11-23 19:42:36发表“资讯”栏目。
本文链接：https://www.lezaizhuan.com/article/538993.html
相关文章
