数据结构（二叉树）家谱管理系统

1、数据结构（二叉树）家谱管理系统摘 要 在本次家谱课程设计中采用二叉树来表示家谱关系,由于在家谱中每个家族成员的子女不止一个,而双亲只有一个,所以采用二叉树结构来描述家族成员之间的关系。在家谱课程设计中还用到单链表,在设计中要将二叉树存储在文件中,最终要读取文件中的记录,要将文件中的数据还原到内存中组成二叉树结构,而文件中元素与元素之间的结构是线性,而且直接对文件中的数据操作很不方便，所以将文件中的元素存储在单链表中,再对单链表操作还原成内存中的二叉树。 在对家谱的文件操作中，为了还原家谱方便，采用按层遍历的顺序保存二叉树中各结点的信息，在层次遍历中，使用队列来实现二叉树的层次遍历。 本家谱主要

2、包括两个模块，第一个是文件操作功能模块，此模块实现了家谱记录输入、读取存盘记录、清除家谱存盘记录、添加成员、存盘 、修改家谱成员信息、删除家谱成员等七大功能;第二个是家谱操作功能模块，实现了查找某人记录、查找某人的孩子、查找某人的祖先、用括号表示法输出家谱、用凹入表示法输出家谱等六大功能。 关键词: Binarytnode save search addRecord del change clear 1 本程序功能框架图 家谱管理系统 文件操作功能 家谱操作功能 家读清添存修删查查查用用谱取除加盘 改除找找找括凹记存家成家家某某某号入录盘谱员 谱谱人人人表表输记存成成记的的示示入 录 盘员员

3、录 孩祖法法记信子 先 输输录 息 出出家家谱 谱 2 1( 项目总体设计 1.1 需求分析 (1) 文件操作功能:记录输入、记录输出、清除全部文件记录和将家谱记录存盘。初始化:用户可输入一个家族的族谱，输入完成之后可保存在文件中。在其后的操作中，可从文件里读取族谱信息、增加新的家族成员、修改已有的家族成员、删除已存在的家族成员、可清除所有的家族成员信息。操作完成之后可保存在文件中。 (2) 家谱操作功能:用括号表示法和凹入法输出家谱二叉树，并能查找某人的配偶、所有孩子、所有祖先、兄弟等功能。 1.2系统功能模块设计: 一(问题描述 本课程设计的主要问题是选择一种数据结构来描述家谱中家族成员之

4、间的关系，在此数据结构上加之一些操作，选用特定的算法来实现家谱操作的功能和文件操作的功能。 二(基本要求 设计要求:编写一个程序，采用一棵二叉树表示一个家谱关系。 具体要求: (1) 文件操作功能:记录输入、记录输出、清除全部文件记录和将家谱记录存盘。 (2) 家谱操作功能:用括号表示法和凹入法输出家谱二叉树，并能查找某人所有的儿子，查找某人的所有祖先。 三(概要设计 1(数据结构的设计 3 在家谱课程设计中采用二叉树来表示家谱关系,由于在家谱中每个家族成员的子女不止一个,而双亲只有一个,所以采用二叉树结构来描述家族成员之间的关系。在家谱课程设计中还用到单链表,在设计中要将二叉树存储在文件中,

5、最终要读取文件中的记录,要将文件中的数据还原到内存中组成二叉树结构,而文件中元素与元素之间的结构是线性,而且直接对文件中的数据操作很不方便，所以将文件中的元素存储在单链表中,再对单链表操作还原成内存中的二叉树。 在对家谱的文件操作中，为了还原家谱方便，采用按层遍历的顺序保存二叉树中各结点的信息，在层次遍历中，使用队列来实现二叉树的层次遍历。 2(算法的设计 本设计从总体上主要分2个模块，分别是家谱操作模块和文件操作模块。 家谱操作模块: 1)Binarytnode* Binarytree:bulid(Binarytnode* p,int num); /输入家谱，形参p为二叉树根结点的地址，形参

6、num为结点的编号，建立二叉树并返回这棵二叉树的根结点的地址。 算法:首先先建立一个二叉树结点，提示用户输入该结点的姓名，将 用户输入的姓名写入到该结点的成员变量name中，将形参num写入到该结点的成员变量number中，将双亲结点的地址赋给结点的成员变量的双亲指针，提示用户是否有左孩子，若有左孩子则递归调用通过形参将双亲结点的地址传递过去，递归调用返回的地址赋给它的双亲结点的左孩子指针，右孩子的建立同理可得，通过递归来建立整棵二4 叉树。 2)Binarytnode* Binarytree:searchRecord(string name); /形参name要查找的姓名，按姓名查找某人记录

7、，若找到记录则返回该节点的地址，反之，则返回一个空指针。 算法:通过层次遍历来和每个结点的成员变量name比较若姓名匹配则返回该节点的地址。首先判断二叉树的根结点是否为为空，若为空则不进行查找。反之，则将根结点入队列，然后进入一个循环体，使循环为真的条件是队列不为空，循环体语句是取队头元素，然后对该元素的判断它的成员变量name是否与查找的姓名相匹配。若匹配则返回该结点的地址，若不匹配，则删除队头元素将它的左右孩子入队列(左右孩子不空的情况下)，进行循环。若直到遍历完整棵子树都还没找到，则返回一个空指针。 3)void Binarytree:searchChild(string name);

8、/形参name要查找的姓名，按姓名查找某人的孩子，若找到记录则显示该节点孩子的姓名，反之，则提示未找到信息。 算法:调用Binarytnode* searchRecord(string name)函数查找与参数 name相匹配的记录，然后判断其返回的地址是否为空，若为空则不进行查找其子女，若不为空，则输出其左右孩子(左右孩子不空的情况下)。 4)void Binarytree:searchParent(string name); /形参name要查找的姓名，按姓名查找某人的祖先，若找到记录则按辈份从小到大显示该节点的祖先，反之，则提示未找到信息。 算法:调用Binarytnode* searc

9、hRecord(string name)函数查找与参数 5 name相匹配的记录，然后判断其返回的地址是否为空，若为空则不进行查找其双亲，若不为空，则用循环通过双亲指针按辈分从小到大输出双亲的姓名，直到双亲的地址为空，结束循环。 5)void Binarytree:addRecord(string parent,string name); /插入家族成员记录，形参parent为要插入的家族成员的双亲姓名，形参name为要插入家族成员的姓名。 算法:调用Binarytnode* searchRecord(string name)函数查找与参数 name相匹配的记录，然后判断其返回的地址是否为空，

10、若为空则不进行插入操作，若不为空，则判断其是否左子树是否为空，若为空则建立一个结点将参数name赋给结点的成员变量name中去，然后通过它的双亲结点的编号计算出它的编号为2*number，将编号、双亲的地址分别赋给它的成员变量number、parent 。若不为空，再判断它的右子树是否为空，若为空则按建立左孩子的同样的方法建立右孩子。若还为空，则说明左右子树都不为空，则不允许添加记录。 6)void Binarytree:change(string name); /修改家族成员的信息，行参name为要修改的家族成员的姓名。 算法:调用Binarytnode* searchRecord(stri

11、ng name)函数查找与参数 name相匹配的记录，然后判断其返回的地址是否为空，若为空则不进行修改操作，若不为空，则将参数name赋给它的成员变量name中。 7)void Binarytree:del(string name); /删除家族成员，行参为要删除的家族成员的姓名。 算法:调用Binarytnode*searchRecord(string name)函数查找与参数 name相匹配的记录，然后判断其返回的地址是否为空，若为空则不进6 行删除操作，若不为空，则判断其左右子树是否为空，若左右子树都为空，则将其双亲结点的对应的左或右孩子指针赋为空，释放其结点的空间。反之，则不删除该结点

12、。该函数只允许删除叶子结点。 8) Binarytnode* Binarytree:load(node* head, Binarytnode* parent) / 读取存盘记录，将单链表还原为二叉树，返回该二叉树的根结点的地址。 算法:通过递归调用来重建二叉树。首先，调用函数node* node: read()，该函数的作用是将文件中二叉树的信息存放在单链表中，返回单链表的头指针的地址。若返回的指针为空，则，不进行读取存盘记录操作，若不空，则建立一个二叉树结点，取单链表的的一个节点，将其结点的信息写入到二叉树结点的相应的成员变量中，通过编号计算出该左孩子的的编号(由于孩子的编号肯定小于双亲的编

13、号，而编号在单链表是从小到大排列的)从当前单链表的结点往下寻找编号相匹配的结点 若找到，则将该结点的地址和二叉树结点的地址通过函数的参数递归调用该函数返回的地址赋给二叉树的左孩子指针，右子树的建立同左子树的建立同理。建立完整个二叉树后，返回该二叉树根结点的地址。 9)void Binarytree:displaytree1(Binarytnode* root) /括号法显示, 形参root为根结点的的地址。 算法:用递归来实现二叉树的括号法表示。首先，判断二叉树根结点是否为空，若为空，则不显示二叉树，若不为空，则显示根结点的数据，输出(,再递归调用显示它的左孩子(左孩子不空的情况下)，7 然后

14、输出，再递归调用显示它的右孩子(右孩子不空的情况下)，然后输出)。 10)void Binarytree:displaytree2(Binarytnode* root,int n); /凹入法显示，形参root为根结点的地址,行参n为缩进量。 算法:用递归来实现二叉树的凹入法表示。首先，判断二叉树是否为空，若为空，则不显示二叉树，设置输出宽度(由形参 n决定)，递归显示它的左孩子输出宽度为它双亲结点的输出宽度的2倍，换行，通力递归显示它的右孩子，换行。 文件操作模块: 1) void Binarytree:save(Binarytnode* root) /存盘，将家谱保存到文件中，行参为二叉树

15、根结点的地址。 算法:为了还原二叉树方便采用按层次遍历(其记录按编号由从小大到大的顺序存储在文件中)的顺序来保存二叉树的信息。首先，先清空原来文件的内容，判断二叉树根结点的是否为空，若为空，则不进行存盘操作，若不为空，将根结点入队列，进入循环，循环为真的条件是对列为空，循环体为，取队头元素，将对头元素的姓名和编号写入文件，然后删除对头元素，再将其左子树和右子树入队列(若左右子树存在的情况下)。当循环结束的时候，整棵二叉树都保存在文件中(遍历结束)。 2)void Binarytree:clear();/清除文件内容。 算法:删除存档文件jiapu.txt。并建立一个空文件jiapu.txt。

16、2) node* node: read(); /将文件中二叉树的信息存放在单链表中，返回单链表的头指针的地址 8 算法:首先，判断文件是否为空，若文件为空，则不进行读取操作，返回一个空指针若不空，则将二叉树按文件中的排列顺序存储在单链表中，并返回该单链表的头指针的地址。 2(详细实现步骤、流程图、代码: 2.1实现步骤: 收集资料 1)2)概要设计、详细设计 编码 3)4)测试 2.2流程图 开始 Meun Binarytree:bulid(输入) Save Load/read Clear choose Add record Search Del Change Y Meun N 结束 9 1)

17、主菜单 代码: #include Binarytree.h #include #include void menu() coutendl; cout *欢迎使用家谱管理系统*endl; cout * *endl; cout * &文件操作功能& &家谱操作功能& *endl; cout * *endl; cout * 家谱记录输入-1 * 查找某人记录-8 *endl; cout * 读取存盘记录-2 * 查找某人的孩子-9 *endl; cout * 清除家谱存盘记录-3 * 查找某人的祖先-c *endl; cout * 添加成员-4 * 用括号表示法输出家谱-k *endl; cout

18、* 存盘-5 * 用凹入表示法输出家谱-n *endl; cout * 修改家谱成员信息-6 * *endl; cout * 删除家谱成员-7 * *endl; cout * 10 *endl; cout *显示菜单-m*endl; cout *退出-0*endl; coutendl; void main() char s; menu(); /显示菜单 string name,str,name2; Binarytree tree; /建立一个二叉树对象 node f; /建立一个单链表 while(1) cout请选择相应功能的序号按enter进入操作:str; if(str.size()!=

19、1)s=m; else s=str0; /用于判断用户是否有错误操作 switch(s) case 1 : cout输入姓名:; tree.outroot()=tree.bulid(NULL,1);break;/输入家谱 case 2 : if(f.read()=NULL) cout文件内容为空!无法读取数据!endl;/判断单链表是否为空 else tree.outroot()=tree.load(f.read(); cout家谱已载入!endl; break; /将文件中内容还原为二叉树 case 8 : coutname; Binarytnode* p; p=tree.searchRec

20、ord(name); if(p!=NULL)coutGetname()endl;break;/查找某人的信息 case 9 : coutname; tree.searchChild(name);break;/查找某人孩子的信息 case c : coutname; tree.searchParent(name);break;/查找某人祖先信息 case k : tree.displaytree1(tree.outroot();coutendl;break;/用括号法表示 case n : tree.displaytree2(tree.outroot(),0);break;/用凹入法表示 cas

21、e 5 : if(tree.outroot()=NULL) cout你没有输入家谱记录!无法保存家谱记录!endl; else tree.save(tree.outroot();break;/家谱保存 case 3 : tree.clear(); cout家谱记录清除成功!endl; break;/删除记录文件 case m : menu();break; case 4 : if(tree.outroot()!=NULL) cout请输入要添加成员的姓字:name; cout请输入该成员双亲的姓名:name2; tree.addRecord(name2,name); else cout家谱记录

22、为空!无法完成添加操作!endl;break; case 6 : if(tree.outroot()!=NULL) 11 cout输入要修改成员的姓名:name; tree.change(name);/调用 else cout家谱记录为空!无法完成修改操作!endl;break; case 7 : if(tree.outroot()!=NULL) cout输入要删除成员的姓名:name; tree.del(name);/调用删除函数 else cout家谱记录为空!无法完成删除操作!endl;break; case 0 : exit(0); /退出 default: cout错误操作!name

23、; /输入姓名 m-Getname()=name; m-parent()=p; /存放双亲结点的地址 12 m-Getnumber()=num; /获取节点的编号 coutGetname()n; if(n=Y|n=y) /判断是否有右子树 cout输入他左孩子的姓名:left()=bulid(m,2*num);/递归调用建立左子树 else m-left()=NULL;/无左子树则左孩子指针赋为空 coutGetname()是否有右孩子(Y/N):n; if(n=Y|n=y)/判断是否有左子树 cout输入他右孩子的姓名:right()=bulid(m,2*num+1);/递归调用建立右子树

24、else m-right()=NULL;/无左子树则左孩子指针赋为空 return m; 3) 添加成员 13 主要实现代码 void Binarytree:addRecord(string parent,string name)/(功能4的主要实现函数) /插入家族成员记录，形参parent为要插入的家族成员的双亲姓名，形参name为要插入家族成员的姓名 Binarytnode* q; q=searchRecord(parent); if(q!=NULL) Binarytnode* p;/定义指针 p=new Binarytnode; if(q-left()=NULL)/左子树 q-left

25、()=p; p-Getname()=name;/新加结点的值 p-Getnumber()=2*(q-Getnumber();/新加结点编号 p-parent()=q; cout添加成功!right()=NULL)/右子树操作 q-right()=p; p-Getname()=name; p-Getnumber()=2*(q-Getnumber()+1; p-parent()=q; cout添加成功!right()!=NULL&q-left()!=NULL)/左子树不等于空值 cout无法添加成员!endl; 4) 存盘 14 主要实现代码: void Binarytree:save(Binar

26、ytnode* root)/以层次遍历的顺序保存二叉树各结点(功能5的主要实现函数) fstream outfile;/定义文件 outfile.open(jiapu.txt,ios:out); outfile.close(); system(del jiapu.txt);/清空文件内容 queueQ;/Q为队列,队列元素是二叉树结点指针 Binarytnode* p; if(root!=NULL) Q.push(root);/根结点入队列 while(!Q.empty()/判断文件 p=Q.front();/取队头元素 outfile.open(jiapu.txt,ios:app|ios:o

27、ut); if(!outfile) cout文件不能打开!endl; abort(); outfileGetname() Getnumber()left()!=NULL) Q.push(p-left();/左孩子结点入队列 15 if(p-right()!=NULL) Q.push(p-right();/右孩子节点入队列 cout已保存到文件!endl; 5) 修改家谱成员信息 主要实现代码: void Binarytree:change(string name)/修改家谱成员的姓名(功能6的主要实现函数) string str; Binarytnode* p; p=searchRecord(

28、name); if(p!=NULL) cout请输入修改后的姓名:str; p-Getname()=str; cout记录修改成功!left()=NULL&p-right()=NULL) q=p-parent(); if(q-left()=p) q-left()=NULL; else q-right()=NULL; delete p; cout记录已删除!Getnext(); p-Getname()=head-Getname(); p-Getnumber()=head-Getnumber(); p-parent()=parent; while(m!=NULL&m-Getnumber()!=2*

29、(head-Getnumber() m=m-Getnext(); if(m!=NULL) p-left()=load(m,p);/用递归建立左子树 else p-left()=NULL; m=head-Getnext(); while(m!=NULL&m-Getnumber()!=2*(head-Getnumber()+1) 18 m=m-Getnext(); if(m!=NULL) p-right()=load(m,p);/用递归建立右子树 else p-right()=NULL; return p; 8)查找某人记录 主要实现代码: Binarytnode* Binarytree:sear

30、chRecord(string name)/用层次遍历来查找某个记录(功能8的主要实现函数) queueQ; /Q为队列,队列元素是二叉树结点指针 Binarytnode* p; if(this-outroot()!=NULL) Q.push(this-outroot();/根结点入队列 while(!Q.empty() p=Q.front();/取队头元素 if(p-Getname().compare(name)=0)/判断是否找到结点的值相同 19 return p; Q.pop();/删除队头元素 if(p-left()!=NULL) Q.push(p-left();/左孩子结点入队列

31、if(p-right()!=NULL) Q.push(p-right();/右孩子节点入队列 cout未找到相匹的姓名!left()!=NULL) coutGetname()的左孩子的姓名为:endl; coutleft()-Getname()endl;/显示它的左孩子 else coutGetname()无左孩子!right()!=NULL) coutGetname()的右孩子的姓名为:endl; coutright()-Getname()endl;/显示它的右孩子 else coutGetname()无右孩子!parent()=NULL)cout此人没有双亲!endl; else cout

32、此人的祖先按辈份从小到大排序为:parent(); 21 while(p!=NULL) coutGetname()parent();/指针移动到它的双亲节点 coutendl; 11)括号输出法 主要实现代码: void Binarytree:displaytree1(Binarytnode* root) /用递归来实现括号法表示(功能k的主要实现函数) if(root!=NULL) coutGetname();/输出根结点 if(root-right()!=NULL|root-left()!=NULL)/判断左子树或者右子树是否为空 coutleft(); coutright(); cout); 22 12)用凹入法输出家谱 主要实现代码: void Binarytree:displaytree2(Binarytnode* root,int n)/