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

摘 要

在本次家谱课程设计中采用二叉树来表示家谱关系,由于在家谱中每个

家族成员的子女不止一个,而双亲只有一个,所以采用二叉树结构来描述家

族成员之间的关系。在家谱课程设计中还用到单链表,在设计中要将二叉树

存储在文件中,最终要读取文件中的记录,要将文件中的数据还原到内存中

组成二叉树结构,而文件中元素与元素之间的结构是线性,而且直接对文件

中的数据操作很不方便，所以将文件中的元素存储在单链表中,再对单链表

操作还原成内存中的二叉树。

模块，实现了查找某人记录、查找某人的孩子、查找某人的祖先、用括号

表示法输出家谱、用凹入表示法输出家谱等六大功能。

关键词：

Binarytnode save search addRecord del change clear

本程序功能框架图

1

1． 项目总体设计

谱记录存盘。初始化：用户可输入一个家族的族谱，输入完成之后可保存

在文件中。在其后的操作中，可从文件里读取族谱信息、增加新的家族成

员、修改已有的家族成员、删除已存在的家族成员、可清除所有的家族成

员信息。操作完成之后可保存在文件中。

2

查找某人的孩子查找某人的祖先

1.2 系统功能模块设计：

一．问题描述

本课程设计的主要问题是选择一种数据结构来描述家谱中家族成员之

间的关系，在此数据结构上加之一些操作，选用特定的算法来实现家

谱操作的功能和文件操作的功能。

二．基本要求

设计要求：编写一个程序，采用一棵二叉树表示一个家谱关系。

具体要求：

(1) 文件操作功能：记录输入、记录输出、清除全部文件记录和将家

家族成员的子女不止一个,而双亲只有一个,所以采用二叉树结构来描

述家族成员之间的关系。在家谱课程设计中还用到单链表,在设计中要

将二叉树存储在文件中,最终要读取文件中的记录,要将文件中的数据

还原到内存中组成二叉树结构,而文件中元素与元素之间的结构是线性,

而且直接对文件中的数据操作很不方便，所以将文件中的元素存储在

单链表中,再对单链表操作还原成内存中的二叉树。

在对家谱的文件操作中，为了还原家谱方便，采用按层遍历的

3

叉树的层次遍历。

2．算法的设计

本设计从总体上主要分 2 个模块，分别是家谱操作模块和文件

操作模块。

家谱操作模块：

1）Binarytnode* Binarytree::bulid(Binarytnode* p,int num)；

//输入家谱，形参 p 为二叉树根结点的地址，形参 num 为结点的编

号，建立二叉树并返回这棵二叉树的根结点的地址。

算法：首先先建立一个二叉树结点，提示用户输入该结点的姓名，

二叉树。

2）Binarytnode* Binarytree::searchRecord(string name)；

//形参 name 要查找的姓名，按姓名查找某人记录，若找到记录则返

回该节点的地址，反之，则返回一个空指针。

算法：通过层次遍历来和每个结点的成员变量 name 比较若姓名匹配

则返回该节点的地址。首先判断二叉树的根结点是否为为空，若为空

则不进行查找。反之，则将根结点入队列，然后进入一个循环体，使

4

元素的判断它的成员变量 name 是否与查找的姓名相匹配。若匹配则

返回该结点的地址，若不匹配，则删除队头元素将它的左右孩子入队

列（左右孩子不空的情况下），进行循环。若直到遍历完整棵子树都

还没找到，则返回一个空指针。

3）void Binarytree::searchChild(string name)；

//形参 name 要查找的姓名，按姓名查找某人的孩子，若找到记录则

显示该节点孩子的姓名，反之，则提示未找到信息。

算法：调用 Binarytnode* searchRecord(string name)函数查找与参数

name 相匹配的记录，然后判断其返回的地址是否为空，若为空则不

name 相匹配的记录，然后判断其返回的地址是否为空，若为空则不

进行查找其双亲，若不为空，则用循环通过双亲指针按辈分从小到大

输出双亲的姓名，直到双亲的地址为空，结束循环。

5）void Binarytree::addRecord(string parent,string name)；

//插入家族成员记录，形参 parent 为要插入的家族成员的双亲姓名，

形参 name 为要插入家族成员的姓名。

算法：调用 Binarytnode* searchRecord(string name)函数查找与参数

5