C语言二叉树家谱管理系统.doc

摘 要 本文设计了一个对数据输入，输出，储存，查找的多功能软件，本文需要保存家族的基本信息，包括姓名及它们的关系，但是由于家族信息很巨大而且关系很复杂所以采用二叉树来表示它们的关系。并且具有保存文件的功能，以便下次直接使用先前存入的信息。家谱的功能是查询家族每个人的信息，并且输出它们的信息，还要具有查询输出功能。 本文采用二叉树来存取家族的基本信息，头结点作为父亲节点，他的左孩子为他的妻子，妻子结点的右孩子为他的孩子，依次存储每个家庭的信息。可以查找每个父亲的孩子和每个人的所有祖先。 关键词： 二叉树 家谱 结点 目录 1 系统功能概述 1 1.1 系统功能 1 图2 成员二叉树功能模块图 4 1.2 总体功能模块 4 2 系统各功能模块的详细设计 4 2.1功能选择 4 2.2信息输入 6 2.3信息输出 7 2.4信息存盘 7 2.5信息清盘 8 2.6信息查询 8 2.7源程序 10 3设计结果与分析 16 3.1菜单函数功能测试 16 4.2输入功能函数测试 16 3.3输出功能函数测试 17 3.4清盘功能函数测试 17 3.5存盘功能函数测试 17 3.6查询功能函数测试 18 总结 19 参考文献 20  1 系统功能概述 1.1 系统功能 实现的方法是先定义一个二叉树，该二叉树上的每个结点由三个元素组成：姓名、指向它左孩子的指针、以及指向它右孩子的指针构成。该家谱管理系统将信息用文件的方法进行存储管理，再从文件中将成员信息以递归的方法创建二叉树。该输入成员信息的方法是将父亲结点存上父亲的信息，然后父亲结点的左孩子存上母亲的信息，母亲结点的右孩子存上孩子的信息。 (1)定义结构体 结构体为表示一个对象的不同属性提供了连贯一致的方法，结构体类型的说明从关键词struct开始，成员可以由各种数据类型混合构成，成员甚至还可以是数组或者其他类型的结构，但是，结构体中不能包含自身定义类型的成员。本文定义了两个结构体，分别是家族成员和二叉树结点的结构体。代码如下： typedef struct fnode { char father[NAMEWIDTH]; char wife[NAMEWIDTH]; char son[NAMEWIDTH]; }FamType; typedef struct tnode { char name[NAMEWIDTH]; struct tnode *lchild,*rchild; }BTree; (2) 二叉树的建立 二叉树的结点有三个域，数据域和两个指针域，数据域用来存放数据，两个指针域分别存放指向该结点左右孩子的指针。并且还有个root结点，称二叉树的根节点。代码如下： BTree *CreatBTree(char *root,FamType fam[],int n) { int i=0,j; BTree *bt,*p; bt=(BTree *)malloc(sizeof(BTree)); strcpy(bt-name,root); bt-lchild=bt-rchild=NULL; while(in strcmp(fam[i].father,root)!=0) i++; if(in) { p=(BTree *)malloc(sizeof(BTree)); p-lchild=p-rchild=NULL; strcpy(p-name,fam[i].wife); bt-lchild=p; for(j=0;jn;j++) if(strcmp(fam[j].father,root)==0) { p-rchild=CreatBTree(fam[j].son,fam,n); p=p-rchild; } } return(bt); } (3)家族成员信息的输入 依次输入一个家庭的父亲、母亲和孩子的姓名。并将它们保存在相应的文件里。 (4)家族成员信息的输出 依次输出每个家庭的父亲、母亲和孩子的姓名。 查找某人的儿子 首先输入父亲的姓名，在二叉树中查找是否有此人，如果没有就输出不存在这样的父亲。如果有就先查看它的左孩子是否存在，不存在就输出这个父亲没有妻子，如果存在就查找左孩子的右孩子，没有右孩子就输出这个父亲没有孩子，存在就输出右孩子的姓名，即为查找到的儿子。 (6)查找某人的祖先 采用后序非递归遍历方法输入从根结点到*s结点的路径，首先输入一个成员的姓名，用一个栈存入查找的路径，当找到时栈中的元素即为它的所有祖先。 该家谱管理系统将各个家庭的信息以文件的形式存储，具体步骤如下图：