《数据结构与算法》实验报告专业班级姓名学号实验项目实验一二叉树的应用实验目的1、进一步掌握指针变量的含义及应用。

2、掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。

3、掌握用指针类型描述、访问和处理二叉树的运算。

实验内容题目1:编写一个程序，采用一棵二叉树表示一个家谱关系。

要求程序具有如下功能：（1）用括号表示法输出家谱二叉树，（2）查找某人的所有儿子，（3）查找某人的所有祖先。

算法设计分析（一）数据结构的定义为了能够用二叉树表示配偶、子女、兄弟三种关系，特采用以下存储关系，则能在二叉树上实现家谱的各项运算。

二叉树型存储结构定义为：typedef struct SNODE{char name[MAX]; //人名struct SNODE *left; //指向配偶结点struct SNODE *right; //指向兄弟或子女结点}FNODE;（二）总体设计实验由主函数、家谱建立函数、家谱输出函数、儿子查找函数、祖先查找函数、结点定位函数、选择界面函数七个函数共同组成。

其功能描述如下：（1）主函数：统筹调用各个函数以实现相应功能void main()（2）家谱建立函数：与用户交互建立家族成员对应关系void InitialFamily(FNODE *&head) //家谱建立函数（3）家谱输出函数：用括号表示法输出家谱输出形式为：父和母（子1和子妻1（孙1），子2和子妻2（孙2））void PrintFamily(FNODE *head) //家谱输出函数（4）儿子查找函数：在家谱中查找到某人所有的子女并输出，同时也能辨别出其是否为家族成员与是否有子女void FindSon(FNODE *b,char p[]) //儿子查找函数（5）祖先查找函数：在家谱中查找到某人所有的祖先并输出，同时也能辨别出其是否为家族中成员。

int FindAncestor(FNODE *head,char son[ ]) //祖先查找函数（6）结点定位函数：在家谱中找到用户输入人名所对应的结点。

FNODE *findnode(FNODE *b,char p[]) //结点定位函数（7）选择界面函数：为便于编写程序，将用户选择部分独立为此函数。

void PRINT(int &n)（三）各函数的详细设计：void InitialFamily(FNODE *&head) //家谱建立函数1：首先建立当前人的信息，将其左右结点置为空，2：然后让用户确定其是否有配偶，如果没有配偶，则当前程序结束，3：如果有则建立其配偶信息，并将配偶结点赋给当前人的左结点；4：再让用户确定其是否有子女，如果有则递归调用家谱建立函数建立子女结点，并将其赋给配偶结点的下一个右结点。

5：如无，则程序结束void PrintFamily(FNODE *head) //家谱输出函数1：首先判断当前结点是否为空，如果为空则结束程序；2：如果不为空，则输出当前结点信息，3：然后判断其左结点（配偶结点）是否为空，如不为空则输出“和配偶信息。

4：再判断配偶结点的右结点是否为空，如不为空则递归调用输出其子女信息，最后输出“）”；5：当配偶结点为空时，则判断其右结点（兄弟结点）是否为空6：如果不为空，则输出“，”，并递归调用输出兄弟信息7程序结束FNODE *findnode(FNODE *b,char p[]) //结点定位函数1：当前结点是否为空，为空则返回空；2：如果和查找信息相同，则返回当前结点；3：如不然，则先后递归访问其左结点，再不是则递归访问右结点void FindSon(FNODE *b,char p[]) //儿子查找函数1：在家谱中定位到要查找的结点，如无则输出“查找不到此人”2：判断其配偶结点与子女结点是否为空，为空则输出“无子女”3：不为空则输出其配偶结点的所有右结点（子女结点）。

int FindAncestor(FNODE *head,char son[ ]) //祖先查找函数1：先在家谱中定位到要查找的结点，如为空输出“不存在此人”，程序结束2：先将父母结点入栈，当栈为空时程序结束，3：栈不为空时，判断栈顶元素是否已访问过，4：访问过，再判断是否为查找结点，如是则输出栈中保存的其祖先结点，并滤过其兄弟结点不输出；不是查找结点，则退栈一个元素5：未访问过，则取当前栈顶元素，置访问标志——1，同时取其右结点6：栈不为空或当前所取结点不为空时，转到2；实验测试结果及结果分析（一）测试结果（二）结果分析（略）实验总结（略）附录实验程序代码(该部分请加注释)/*程序定义部分：*/#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX 20typedef struct SNODE{char name[MAX]; //人名struct SNODE *left; //指向配偶结点struct SNODE *right; //指向兄弟或子女结点}FNODE;/*家谱建立函数*/void InitialFamily(FNODE *&head){FNODE *s,*r,*q;int tag;q=(FNODE *)malloc(sizeof(FNODE));q=NULL;s=(FNODE *)malloc(sizeof(FNODE));printf("输入姓名:\n");scanf("%s"，,s->name);s->left=s->right=NULL;head=r=s;printf("%s是否有配偶?有1,无0\n",head->name); //建立配偶结点scanf("%d",&tag);if(tag){s=(FNODE *)malloc(sizeof(FNODE));printf("输入其配偶姓名:\n");scanf("%s",s->name);s->left=s->right=NULL;r->left=s;r=s;do{ //递归调用建立孩子结点printf("%s是否还有子女?有1,无0\n",head->name);scanf("%d",&tag);if(tag){InitialFamily(q);r->right=q;r=q;}}while(tag);}}/*家谱输出部分*/void PrintFamily(FNODE *head){FNODE *s;if(head!=NULL){printf("%s",head->name); //不为空时输出当前结点if(head->left!=NULL) //输出配偶结点{s=head->left;printf("和%s(",s->name);PrintFamily(s->right); //递归调用输出孩子结点printf(")");}if(head->right!=NULL) //递归调用输出兄弟结点{printf(",");PrintFamily(head->right);}}}/*结点定位函数*/FNODE *findnode(FNODE *b,char p[]) //在家谱中定位所要查找结点{FNODE *q;if(b==NULL)return NULL;else if(!strcmp(b->name,p)) //如果与查找人名相同则返回该结点return b;else{q=findnode(b->left,p); //否则递归调用其左结点if(q!=NULL)return q;else return(findnode(b->right,p)); //递归调用右结点}}/*儿子查找函数*/void FindSon(FNODE *b,char p[]){FNODE *q;q=findnode(b,p);if(q!=NULL) //存在孩子结点时输出{q=q->left;if(q==NULL||q->right==NULL) //判断有无子女printf("%s没有子女!\n",p);else{ //输出则配偶结点的所有子女结点q=q->right;printf("%s子女为：",p);while(q!=NULL){printf("%s ",q->name);q=q->right;}printf("\n");}}elseprintf("不存在你要查找的人!\n");}/*祖先查找函数*/int FindAncestor(FNODE *head,char son[]){FNODE *p,*s;FNODE *stack[MAX];int tag[MAX];int top=-1,i;p=findnode(head,son); //定位结点if(p==NULL){ printf("不存在你要查找的人!\n");return 0;}s=head;do{while(s!=NULL) //将其所有左结点进栈{top++;stack[top]=s;tag[top]=0;s=s->left;}if(top>-1){if(tag[top]==1) //被访问过时{if(stack[top]==p) //如果为所查找结点时输出祖先{printf("%s祖先为:\n",son);for(i=0;i<top;i++){if(stack[i]->right==stack[i+1]) //将其兄弟结点删除,只保留父母结点i++;if(i<top) //依次输出夫妻结点printf("%s",stack[i]->name);i++;if(i<top)printf("和%s ",stack[i]->name);}break;}top--;}else //未访问过则访问其右结点并置访问标志{s=stack[top];if(top>0){s=s->right;tag[top]=1;}}}}while(s!=NULL||top!=-1);if(top==-1)printf("查找不到%s的祖先!\n",p);else printf("\n");return 1;}/*选择界面函数部分：*/void PRINT(int &n){do{printf("请选择:\n");printf("1:建立家谱\n");printf("2:输出家谱\n");printf("3:查找某人所有儿子\n");printf("4:查找某人所有的祖先\n");scanf("%d",&n);}while(n<0||n>4);}/*主函数部分：调用选择界面函数，再依据用户的选择，调用相应函数，实现相关功能*/ void main(){FNODE *head;int n=0;char name[MAX];head=NULL;do{PRINT(n);switch(n){case 1: InitialFamily(head);break;case 2: PrintFamily(head);printf("\n");break;case 3: printf("请输入要查找的姓名:\n");scanf("%s",name);FindSon(head,name);break;case 4: printf("请输入要查找的姓名:\n");scanf("%s",name);n=FindAncestor(head,name);printf("\n");break;default: break;}printf("是否继续?是1，否0\n");scanf("%d",&n);}while(n==1);另注:1、源代码部分请附加适当的注释说明；2、打分的表格请置于实验报告最后一页的底端；3、请遵照本实验范例的文字大小和段落格式排版；4、实验报告双面打印；5、每个实验20分，5个实验共100分。