//循环，知道栈S和N都为空，说明按辈分遍历完成
leveling(S,N,n++);
leveling(N,S,n++);
}
printf("\n");
}
void leveling(SqStack S1,SqStack S2,int n){
gets(name);
Preorder(home,name,p);
if(!p)printf("家谱中无此人");
else{
printf("辈分：%d\n",p->level);
printf("孩子信息");
findchildren(p);
else return(Preorder(T->nextsibling,name,p));
}
}
else return ERROR;
}
void findchildren(BiNode *p){
//查找所得名字的孩子信息，输出他们的名字，若无孩子，则输出无孩子
strcpy(root->man,man1); //将男女的名字赋给该结点的数据域
strcpy(root->woman,woman1);
printf("father:"); //输入该结点的双亲名字
gets(father);
}
void putoutchildren(BiNode *q,int n){
//输出其孩子的结点的信息，并把孩子数加一
printf("第%d个孩子,男方名字%s,女方名字%s\n",n++,q->man,q->woman);
}
void findparents(BiNode *s){
if(!S.base) return ERROR;
S.top=S.base;
S.stacksize =STACK_INIT_SIZE;
return OK;
}
Status Push (SqStack &S,BiNode e){
//将e结点推入栈，作为栈顶元素
gets(man1);
if(strcmp(man1,"#")==0&&strcmp(woman1,"#")==0)//若该结点男女都不存在，则说明该结点为空，即该子树的根结点不存在
{
root=NULL;
}
else{
root=(BiNode *)malloc(sizeof(BiNode));
int level;
struct BiNode *firstchild,*nextsibling;
};
struct SqStack{
//对栈类型进行定义
BiNode *base;
BiNode *top;
int stacksize; }; Nhomakorabea}
}
void levelhome(BiNode *T){
//按层输出该家谱
SqStack S,N; //定义两个栈并初始化
InitStack(S);
InitStack(N);
BiNode *p;
p=T;
int n=1;
q=p->firstchild;
if(q){
print(q);
q->level=n;
Push(S2,*q);
while(q=q->nextsibling){
print(q);
Status Preorder(BiNode *T,char name[10],BiNode *p);
//Status CreateParent(BiNode *s);
void findchildren(BiNode *p);
void putoutchildren(BiNode *q,int n);
int n=1;
BiNode *q;
if(p->firstchild){//该结点的firstchild指针指向的为他的第一个孩子
q=p->firstchild;
putoutchildren(q,n);//输出
}
while(q->nextsibling){
//创建家谱二叉树
char man1[10],woman1[10],father[10],mother[10];
printf("man:");//男方名字，不存在则输入“#”
gets(man1);
printf("woman:");//女方名字，不存在则输入“#”
printf("mother:");
gets(mother);
CreateBiTree(root->firstchild); //递归创建该结点的左、右子树
CreateBiTree(root->nextsibling);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,BiNode e){
//取出栈顶元素
//查询该结点的双亲名字
if(s->father=="#"&&s->mother=="#")
printf("没有父母信息");
else{
if((s->father)!="#")printf("father:%s\n",s->father);
if((s->mother)!="#")printf("mother:%s\n",s->mother);
typedef int Status;
struct BiNode{
//用结构体定义结点类型。
//数据域信息包含家谱中该对的男、女名字，其双亲名字，以及这对夫妇位于家谱中的辈分
//指针域指向他们的第一个孩子以及其他兄弟
char man[10],woman[10],father[10],mother[10];
//将S1栈保存的信息一一取出，查找他孩子的结点，输出其名字，并推入栈S2.
//即S2栈保存的结点是S1的下一辈
BiNode *p,*q;
printf("第%d层的信息为：\n");
while(!EmptyStack(S1)){
Pop(S1,*p);
printf("第%d层的信息为:\n");
if(p){
print(p);
p->level=n;//修改p所指向的结点的辈分信息
Push(S,*p);//将该结点推进栈S
}
while(p=p->nextsibling){
printf("父母信息：");
findparents(p);
}
}
//函数定义
Status InitStack (SqStack &S){
//初始化函数
S.base=(BiNode*)malloc(STACK_INIT_SIZE * sizeof(BiNode));
//第一个孩子的nextsibling指针指向的为孩子的兄弟，即第二个孩子
//如此继续，知道结点的右指针为空
q=q->nextsibling;
putoutchildren(q,n);//输出
}
if(n==1)printf("无孩子");
//用循环来查找该层的所有信息，只要其nextsibling指向的结点不空，均为同一层
print(p);
p->level=n;
Push(S,*p);
}
while(!EmptyStack(S)||!EmptyStack(N)){
if(T){
if(strcmp(T->man,name)==0||strcmp(T->woman,name)==0){
p=T;
return OK;
}
else{
if(Preorder(T->firstchild,name,p))return OK;
if(S.top-S.base >=S.stacksize ){
S.base=(BiNode *)realloc(S.base ,(S.stacksize +STACKINCREMENT)*sizeof(BiNode));
if(!S.base ) return ERROR;
//函数声明
Status InitStack (SqStack &S);
Status Push (SqStack &S,BiNode e);
Status CreateBiTree(BiNode *s);
Status Pop(SqStack &S,BiNode e);
Status EmptyStack(SqStack &S);
char name[10];
printf("请按先序遍历的顺序根据提示输入家谱信息，不存在则输入“#”\n");
leveling(S,N,n++);
leveling(N,S,n++);
}
printf("\n");
}
void leveling(SqStack S1,SqStack S2,int n){
gets(name);
Preorder(home,name,p);
if(!p)printf("家谱中无此人");
else{
printf("辈分：%d\n",p->level);
printf("孩子信息");
findchildren(p);
else return(Preorder(T->nextsibling,name,p));
}
}
else return ERROR;
}
void findchildren(BiNode *p){
//查找所得名字的孩子信息，输出他们的名字，若无孩子，则输出无孩子
strcpy(root->man,man1); //将男女的名字赋给该结点的数据域
strcpy(root->woman,woman1);
printf("father:"); //输入该结点的双亲名字
gets(father);
}
void putoutchildren(BiNode *q,int n){
//输出其孩子的结点的信息，并把孩子数加一
printf("第%d个孩子,男方名字%s,女方名字%s\n",n++,q->man,q->woman);
}
void findparents(BiNode *s){
if(!S.base) return ERROR;
S.top=S.base;
S.stacksize =STACK_INIT_SIZE;
return OK;
}
Status Push (SqStack &S,BiNode e){
//将e结点推入栈，作为栈顶元素
gets(man1);
if(strcmp(man1,"#")==0&&strcmp(woman1,"#")==0)//若该结点男女都不存在，则说明该结点为空，即该子树的根结点不存在
{
root=NULL;
}
else{
root=(BiNode *)malloc(sizeof(BiNode));
int level;
struct BiNode *firstchild,*nextsibling;
};
struct SqStack{
//对栈类型进行定义
BiNode *base;
BiNode *top;
int stacksize; }; Nhomakorabea}
}
void levelhome(BiNode *T){
//按层输出该家谱
SqStack S,N; //定义两个栈并初始化
InitStack(S);
InitStack(N);
BiNode *p;
p=T;
int n=1;
q=p->firstchild;
if(q){
print(q);
q->level=n;
Push(S2,*q);
while(q=q->nextsibling){
print(q);
Status Preorder(BiNode *T,char name[10],BiNode *p);
//Status CreateParent(BiNode *s);
void findchildren(BiNode *p);
void putoutchildren(BiNode *q,int n);
int n=1;
BiNode *q;
if(p->firstchild){//该结点的firstchild指针指向的为他的第一个孩子
q=p->firstchild;
putoutchildren(q,n);//输出
}
while(q->nextsibling){
//创建家谱二叉树
char man1[10],woman1[10],father[10],mother[10];
printf("man:");//男方名字，不存在则输入“#”
gets(man1);
printf("woman:");//女方名字，不存在则输入“#”
printf("mother:");
gets(mother);
CreateBiTree(root->firstchild); //递归创建该结点的左、右子树
CreateBiTree(root->nextsibling);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,BiNode e){
//取出栈顶元素
//查询该结点的双亲名字
if(s->father=="#"&&s->mother=="#")
printf("没有父母信息");
else{
if((s->father)!="#")printf("father:%s\n",s->father);
if((s->mother)!="#")printf("mother:%s\n",s->mother);
typedef int Status;
struct BiNode{
//用结构体定义结点类型。
//数据域信息包含家谱中该对的男、女名字，其双亲名字，以及这对夫妇位于家谱中的辈分
//指针域指向他们的第一个孩子以及其他兄弟
char man[10],woman[10],father[10],mother[10];
//将S1栈保存的信息一一取出，查找他孩子的结点，输出其名字，并推入栈S2.
//即S2栈保存的结点是S1的下一辈
BiNode *p,*q;
printf("第%d层的信息为：\n");
while(!EmptyStack(S1)){
Pop(S1,*p);
printf("第%d层的信息为:\n");
if(p){
print(p);
p->level=n;//修改p所指向的结点的辈分信息
Push(S,*p);//将该结点推进栈S
}
while(p=p->nextsibling){
printf("父母信息：");
findparents(p);
}
}
//函数定义
Status InitStack (SqStack &S){
//初始化函数
S.base=(BiNode*)malloc(STACK_INIT_SIZE * sizeof(BiNode));
//第一个孩子的nextsibling指针指向的为孩子的兄弟，即第二个孩子
//如此继续，知道结点的右指针为空
q=q->nextsibling;
putoutchildren(q,n);//输出
}
if(n==1)printf("无孩子");
//用循环来查找该层的所有信息，只要其nextsibling指向的结点不空，均为同一层
print(p);
p->level=n;
Push(S,*p);
}
while(!EmptyStack(S)||!EmptyStack(N)){
if(T){
if(strcmp(T->man,name)==0||strcmp(T->woman,name)==0){
p=T;
return OK;
}
else{
if(Preorder(T->firstchild,name,p))return OK;
if(S.top-S.base >=S.stacksize ){
S.base=(BiNode *)realloc(S.base ,(S.stacksize +STACKINCREMENT)*sizeof(BiNode));
if(!S.base ) return ERROR;
//函数声明
Status InitStack (SqStack &S);
Status Push (SqStack &S,BiNode e);
Status CreateBiTree(BiNode *s);
Status Pop(SqStack &S,BiNode e);
Status EmptyStack(SqStack &S);
char name[10];
printf("请按先序遍历的顺序根据提示输入家谱信息，不存在则输入“#”\n");
