用二叉树表示家谱关系并实现各种查找功能.pdf-资料库

用二叉树表示家谱关系并实现各种查找功能 ---by 汤唐

目录 1、设计目的与内容 ............................................................................................. 3 1.1 问题七：用二叉树表示家谱关系并实现各种查找功能 ............. 3 2、算法的基本思想 ............................................................................................. 4 2.1 问题七概述： ............................................................................................. 4 3、源程序及系统文件使用说明...................................................................... 4 4、算法结果与分析 ........................................................................................... 12 4.1 菜单函数功能测试 ................................................................................. 12 4.2 输入功能函数测试 ................................................................................. 12 4.3 输出功能函数测试 ................................................................................. 13 4.4 查询功能函数测试 ................................................................................. 13 4.5 二叉树的各种表示法函数测试 .......................................................... 13 5、心得体会 ......................................................................................................... 14 6、开发环境与开发工具.................................................................................. 14 7、参考文献 ......................................................................................................... 15

1、设计目的与内容 1.1 问题七：用二叉树表示家谱关系并实现各种查找功能目的：掌握二叉树遍历算法的应用，熟练使用先序、中序、后序 3 种递归遍历算法进行二叉树问题的求解。内容：采用一棵二叉树表示一个家谱关系，要求具有以下功能：①、文件操作功能，即家谱记录的输入、家谱记录的输出、清除全部文件记录和将家谱记录存盘。②、家谱操作功能，即用括号表示法输出家谱二叉树、查找某人的所有儿子、查找某人的所有祖先。需求分析：模块 1：功能选择分析：功能选择模块函数，主要提供 1：文件操作 2：家谱操作两个功能模块让用户选择。输入数字 1 的时候，出现界面 1：输入 2：输出 3：清盘 4：更换始祖 0：存盘返回。返回后输入数字 2，出现界面 1：括号表示法 2：二叉树表示法 3：找某人的所有儿子 4：找某人所有祖先，用户可以根据自己的需求进行选择。模块 2：二叉树的建立分析：二叉树的结点有三个域，数据域和两个指针域，数据域用来存放数据，两个指针域用来分别存放指向该结点左右孩子的指针。并且还有个 root 结点，称二叉树的根节点。模块 3：家族成员信息的输入与输出分析：依次输入一个家庭的父亲、母亲和孩子的姓名，先用定义好的结构体数组存储数据，并通过 i/o 流将它们保存在相应的文件里。通过循环依次输出 fam 数组中的数据，即输出每个家庭的父亲、母亲和孩子的姓名。模块 4：查找某人的儿子分析：首先输入父亲的姓名，在二叉树中查找是否有此人，如果没有就输出不存在这样的父亲。如果有就先查看它的左孩子是否存在，不存在就输出这个父亲没有妻子，如果存在就查找左孩子的右孩子，没有右孩子就输出这个父亲没有孩子，存在就输出右孩子的姓名，即为查找到的儿子。模块 5：查找某人的祖先分析：采用后序非递归遍历方法输入从根结点到*s 结点的路径，首先输入一个成员的姓名，用一个栈存入查找的路径，当找到时栈中的元素即为它的所有祖先。模块 6：二叉树的各种表示法分析：①、括号表示法：通过先序遍历，先输出根节点，若根节点的左孩子结点或右孩子结点非空，则先输出（，然后递归左子树；如果根节点的

右孩子结点非空，递归右子树，然后输出）。②、二叉树树形表示法：在二叉树凹入表示法的基础上，对母亲结点的左右子树如何输出做了一些控制，设置每一个结点的固定宽度，分清其左右结点，循环输出至为空。 2、算法的基本思想 2.1 问题七概述：设计一个对数据输入，输出，储存，查找的多功能程序，需要保存家族的基本信息，包括姓名及它们的关系，并采用二叉树来表示它们的关系，头结点作为父亲节点，他的左孩子为他的妻子，妻子结点的右孩子为他的孩子，依次存储每个家庭的信息。该题还需要具有保存文件的功能，以便下次直接使用先前存入的信息。家谱的功能是查询家族每个人的信息，并且输出它们的信息，而且还要具有查询输出的功能。主程序流程：首先创建始祖名称，完成整个家谱的重构。进入主菜单界面，输入不同的数字进行不同的操作，1：文件操作；2：家谱操作；0：退出系统；输入其他选择，则报错。若输入的操作为 1，则进入文件操作界面，1：输入调用 InputFam(fam,n)函数，完成数据输入操作；2：输出调用 OutputFile(fam,n)函数，完成数据的输出操作；3：一键清空调用 DelAll(fam,n)函数；0：存盘返回调用 SaveFile(fam,n)函数运用 i/o 流将已保存到数组的数据存到相应的文件中，输入其他选择，则报错。若输入的操作为 2，则进入家谱操作界面，1：括号表示法调用 DispTree1(bt)函数，通过先序遍历，输出（，），完成其括号表示法的输出；2：二叉树家谱调用 DispTree2(bt)函数，在二叉树凹入表示法的基础上，对母亲结点的左右子树如何输出做了一些控制，设置每一个结点的固定宽度，分清其左右结点，循环输出至为空，以期望达到能够输出二叉树树形结构的目标；3：找某人所有儿子调用 FindSon(bt)函数通过输入父亲姓名来检索该姓名所位于的位置，判断其是否有妻子、是否有儿子，如果有儿子将儿子输出；4：找某人所有祖先调用 Ancestor(bt)函数，输入某姓名，对该姓名先进行检索，若成功检索，调用 Path（bt,p）路径函数，通过后序非递归遍历将该姓名所处位置的结点的祖先结点全部输出； 0：返回；输入其他选择，则报错。 3、源程序及系统文件使用说明问题七： #include #include #include #include #include

//从fam(含n个记录)递归创建一棵二叉树 //找到了该姓名的记录 //将root中的COPY复制到bt->name中 int i=0,j; BTree *bt,*p; bt=(BTree *)malloc(sizeof(BTree)); //创建父亲节点 strcpy(bt->name,root); bt->lchild=bt->rchild=NULL; while (ilchild=p->rchild=NULL; strcpy(p->name,fam[i].wife); bt->lchild=p; for (j=0;jrchild=CreatBTree(fam[j].son,fam,n); p=p->rchild; //创建母亲节点 //找所有儿子 //代表了姓名字符、最大场宽、数组元素树 //家谱树类型 char name[MaxSize]; struct tnode *lchild,*rchild; char father[MaxSize]; //父 //母 char wife[MaxSize]; char son[MaxSize]; //子 using namespace std; #define MaxSize 30 typedef struct fnode { } FamType; typedef struct tnode { } BTree; //创建二叉树 BTree *CreatBTree(char *root,FamType fam[],int n) { } //以括号表示法输出二叉树 void DispTree1(BTree *b) //先序遍历 { } //二叉树家谱表示法 void DispTree2(BTree *bt) cout<name; if (b->lchild!=NULL || b->rchild!=NULL) { } if (b!=NULL) { } cout<<"("; DispTree1(b->lchild); if (b->rchild!=NULL) DispTree1(b->rchild); cout<<")"; cout<<","; //累计

BTree *St[MaxSize],*p; int Level[MaxSize][2],top,n,i,x=0,width=4; int flag=0; if (bt!=NULL) { cout<<" >>二叉树家谱表示法:"<0) { top=1; { } } //以凹入表示法输出 void DispTree3(BTree *bt) { top=1; } //将左子树根节点进栈 cout<<" "; //退栈并凹入显示该节点值 cout<lchild->name; flag=1; n=0; top++; St[top]=p->lchild; Level[top][0]=0; Level[top][1]=1; p=St[top]; n=Level[top][0]; for (i=1;i<=n;i++) //其中n为显示场宽,字符以右对齐显示 cout<name<lchild!=NULL) { } top--; if (p->lchild!=NULL) { } if(p->lchild!=NULL&&p->rchild!=NULL) { } if (p->rchild!=NULL&&p->lchild==NULL) { } top++; St[top]=p->rchild; Level[top][0]=n+width; Level[top][1]=2; top++; St[top]=p->rchild; Level[top][0]=n+width; Level[top][1]=2; //显示场宽增width //为右孩子节点 //显示场宽增width //为左孩子节点 //显示场宽增width //为右孩子节点 //将右子树根节点进栈 BTree *St[MaxSize],*p; int Level[MaxSize][2],top,n,i,width=4; if (bt!=NULL) { cout<<" >>家谱凹入表示法:"<

cout<<"--"; cout<<"(l)"; //退栈并凹入显示该节点值 p=St[top]; n=Level[top][0]; for (i=1;i<=n;i++) //其中n为显示场宽,字符以右对齐显示 cout<<" "; cout<name; if (Level[top][1]==1) else for (i=n+1;i<=MaxSize-6;i+=2) cout<rchild!=NULL) { } if (p->lchild!=NULL) { } top++; St[top]=p->rchild; Level[top][0]=n+width; Level[top][1]=2; top++; St[top]=p->lchild; Level[top][0]=n+width; Level[top][1]=1; //显示场宽增width //为左孩子节点 //显示场宽增width //为右孩子节点 //将右子树根节点进栈 //将左子树根节点进栈 //根节点进栈 cout<<"(r)"; St[top]=bt; Level[top][0]=width; while (top>0) { } } //采用先序递归算法找name为xm的节点 BTree *FindNode(BTree *bt,char xm[]) { } //输出某人的所有儿子 void FindSon(BTree *bt) { if (strcmp(p->name,xm)==0) else { } BTree *p=bt; if (p==NULL) else { } char xm[MaxSize]; return(NULL); return(p); } bt=FindNode(p->lchild,xm); if (bt!=NULL) else return(bt); return(FindNode(p->rchild,xm));

cout<<" >>"<>"<>不存在"<name<<" "; p=p->rchild; p=p->rchild; if (p==NULL) else { } cout<<" >>"<lchild; if (p==NULL) else { } BTree *p; cout<<" >>父亲姓名:"; cin>>xm; p=FindNode(bt,xm); if (p==NULL) else { } } //采用后序非递归遍历方法输出从根节点到*s节点的路径 int Path(BTree *bt,BTree *s) { BTree *St[MaxSize]; BTree *p; int i,flag,top=-1; do { //将bt的所有左节点进栈 top++; St[top]=bt; bt=bt->lchild; while (bt) { } p=NULL; //p指向当前节点的前一个已访问的节点 flag=1; //设置bt的访问标记为已访问过 while (top!=-1 && flag) { bt=St[top]; //取出当前的栈顶元素 if (bt->rchild==p) //右子树不存在或已被访问,访问之 { if (bt==s) //当前访问的节点为要找的节点,输出路径 { return 1; } else cout<<" >>所有祖先:"; for (i=0;iname<<" "; cout<

资料库

用二叉树表示家谱关系并实现各种查找功能.pdf

相关推荐

开发技术

热门标签

最新资料