基于二叉树实现的家谱，数据结构课程设计

在学习过程中，我也能过上网查了不少资料，学以致用，自我创新，独立完成了这份自己的报告，从中在学到用，从用又到学，不断修改，系统更新。3.孩子兄弟表示的家谱类似于二叉树，其firstchild相当于二叉树的左子树，其nextSibling相当于二叉树的右子树，则其前序遍历也相当于二叉树的先序遍历，则其算法思想与二叉树的先序遍历相同。在实验过程中，从需求分析，到概念设计，懂得了不少有关项目建设的知识，

何育思

2974人浏览 · 2023-11-29 14:14:51

何育思 · 2023-11-29 14:14:51 发布

一、课程设计任务要求

【问题描述】

家谱记载了一个家族的世系繁衍及重要人物事迹。使用树型结构对家谱进行管理，实现查看祖先和子孙个人信息，插入家族成员，删除家族成员的功能

【基本要求】

（1）采用树形结构完成对家谱成员信息的建立，可利用孩子兄弟表示方法表示树型结构

（2）完成家谱成员信息查找、插入、修改、删除功能

（3）判断两个人的家族关系

（4）进行子孙、祖先、堂兄弟关系的查询

【拓展要求】

（1）实现树的层次遍历，显示家族每一代的成员

（2）打印家谱的树型结构操作

（3）判断两个成员是否属于直系或旁系三代关系

（4）自行设计家谱的其他操作

二、已完成的项目及完成程度

1.利用孩子兄弟表示方法表示树型结构完成对家谱成员信息的建立

2.完成家谱成员信息查找、插入、修改、删除功能

3.判断两个人的家族关系

4.进行子孙、祖先、堂兄弟关系的查询

5.利用树的层次遍历表示家族每一代的成员

6.打印家谱的树型结构操作

7.判断两个成员是否属于直系或旁系三代关系

三、理论依据

1.利用结构体将家谱中的一个角色的姓名，性别，出生年份，是否具有配偶以及其父辈姓名进行封装；并采用孩子兄弟法构造家谱的树型结构，以体现家谱中各人之间的关系。

2.利用队列来完成家谱的层次遍历，队列元素为CSTree类型。

3.孩子兄弟表示的家谱类似于二叉树，其firstchild相当于二叉树的左子树，其nextSibling相当于二叉树的右子树，则其前序遍历也相当于二叉树的先序遍历，则其算法思想与二叉树的先序遍历相同。

4.在本次课设中引入了文件的插入。

四、主要算法流程

1.树的层次遍历算法

(1)层次遍历，类似于图中的广度优先遍历。定义一个队列，

(2)将根结点入队，先将根结点入队列，(3)当队列不为空时循环进行如下操作：队头元素出队列，访问该元素，将它的子女结点及子女结点的所有兄弟结点入队列。

2树的先根次序遍历。

类似于深度优先遍历，先根次序遍历是先访问根结点，
再先根递归访问它的所有子树；后根次序遍历是先后根递归遍历它的所有子树，再访问根节点。
使用 fopen( ) 函数来创建一个新的文件或者打开一个已有的文件;FILE *fopen( const char * filename, const char * mode );.r 打开一个已有的文本文件，允许读取文件.

五、主要代码

1.通用头文件common.h

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<malloc.h>

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

typedef int Status;

2,结构类型定义头文件CSTreelist.h

#include"common.h"



typedef struct{

    char name[20];//姓名

    int sex;//性别 1为男性 0为女性

    char mate[20];//配偶姓名  

    int seniority;//辈分

    int birthyear;//年龄

    int alive;//1为在世，0为已过世

}TElemType;



typedef struct CSTNode

{

    TElemType data;

    struct CSTNode *firstChild;

struct CSTNode *nextSibling;

struct CSTNode *father;

}CSTNode,*CSTree,*CSForest;//孩子结点类型





typedef struct LNode{               //链表和链表结点类型

    CSTree data;                     //数据域

    struct LNode *next;             //指针域

}LNode, *LinkList;



void createCSTNode(CSTree*T);//创建结点

void initCSTNode(CSTree*T);//初始化结点

void searchNode(CSForest T,char name[20],CSTree*A);//通过姓名查找结点

void insertNode(CSTree*father,CSTree*child);//插入节点

void deleteCSTNode(CSTree *T);//删除节点（包括他的子树）

void destroy(CSTree*T);//销毁某树



void showCSTNode(CSTree*T);

void changeBirthyear(CSTree *T);

void changeFather(CSTree *P,CSForest T);

void refreshSeniority(CSForest*T);

void changeCSTNodeimf(CSTree*P,CSForest T);

Status InitQueue(LinkList *L);                                  //初始化队列

LNode* CreateNode(CSTree t);                                     //新建一个结点

Status Enqueue(LNode *p,CSTree t);                               //元素q入队列

Status Dequeue(LNode *p,CSTree *q);                            //出队列，并以q返回值

Status IfEmpty(LinkList L);                                     //队列判空

void DestroyQueue(LinkList L);                                  //销毁队列

Status Traverse(CSTree T,LinkList L);        //用队列遍历输出树

Status PrintTree(CSTree t);

void changeNode();





void inorderCousin(CSTree T,CSTree A);

void PrintAsTree(CSTree T);



void init();//初始化

void insertNewNode();//插入人物

void search();

void deleteNode();

void changeNode();

void relationship();

void searchrelacen();

void Meau0();//此程序说明界面

void Meau1();//菜单函数选择界面

CSTOperate.cpp文件

#include"common.h"



typedef struct{

    char name[20];//姓名

    int sex;//性别 1为男性 0为女性

    char mate[20];//配偶姓名  

    int seniority;//辈分

    int birthyear;//出生年份

    int alive;//1为在世，0为已过世

}TElemType;



typedef struct CSTNode

{

    TElemType data;

    struct CSTNode *firstChild;

struct CSTNode *nextSibling;

struct CSTNode *father;

}CSTNode,*CSTree,*CSForest;//孩子结点类型





typedef struct LNode{               //链表和链表结点类型

    CSTree data;                     //数据域

    struct LNode *next;             //指针域

}LNode, *LinkList;



void createCSTNode(CSTree*T);//创建结点

void initCSTNode(CSTree*T);//初始化结点

void searchNode(CSForest T,char name[20],CSTree*A);//通过姓名查找结点

void insertNode(CSTree*father,CSTree*child);//插入节点

void deleteCSTNode(CSTree *T);//删除节点（包括他的子树）

void destroy(CSTree*T);//销毁某树



void showCSTNode(CSTree*T);

void changeBirthyear(CSTree *T);

void changeFather(CSTree *P,CSForest T);

void refreshSeniority(CSForest*T);

void changeCSTNodeimf(CSTree*P,CSForest T);

Status InitQueue(LinkList *L);                                  //初始化队列

LNode* CreateNode(CSTree t);                                     //新建一个结点

Status Enqueue(LNode *p,CSTree t);                               //元素q入队列

Status Dequeue(LNode *p,CSTree *q);                            //出队列，并以q返回值

Status IfEmpty(LinkList L);                                     //队列判空

void DestroyQueue(LinkList L);                                  //销毁队列

Status Traverse(CSTree T,LinkList L);        //用队列遍历输出树

Status PrintTree(CSTree t);

void changeNode();





void inorderCousin(CSTree T,CSTree A);

void PrintAsTree(CSTree T);



void init();//初始化

void insertNewNode();//插入人物

void search();

void deleteNode();

void changeNode();

void relationship();

void searchrelacen();

void Meau0();//此程序说明界面

void Meau1();//菜单函数选择界面

main.cpp

#include"CSTreelist.h"



CSForest T;



CSTree A,B;

void init(){

    createCSTNode(&T);

    FILE*r;

    r= fopen("H.txt","r");

    if(r==NULL)

    {

        printf("打开文件失败!");

    }

    A=NULL;

    B=NULL;

    char fatherName[100];

    createCSTNode(&A);

    while(fscanf(r,"%s %d %s %d %d %s",&A->data.name,&A->data.sex,&A->data.mate,&A->data.birthyear,&A->data.alive,fatherName)!=EOF)

    {  

        printf("%s %d %s %d %d %s",A->data.name,A->data.sex,A->data.mate,A->data.birthyear,A->data.alive,fatherName);

        

        searchNode(T,fatherName,&B);

        if(B==NULL){

            printf("此人的父亲不在家谱里！\n");

            free(A);

        }

        if(B->data.seniority!=0&&B->data.birthyear>=A->data.birthyear){

            printf("出生不能比父亲早\n");

            free(A);

        }

        else {

            printf("insert\n");

            insertNode(&B,&A);

            }

        B=NULL;

        A=NULL;

        createCSTNode(&A);

    }

    free(A);

    A=NULL;

    fclose(r);

}





void insertNewNode(){

    char fatherName[100];

    A=NULL;

    B=NULL;

    createCSTNode(&A);

    printf("请输入：姓名 性别(1/0) 配偶姓名 出生年份  生存状况(1/0) 父亲姓名\n ");

    printf(" 例如： 刘星  1         无       1560       1           刘六\n ");

    scanf("%s %d %s %d %d %s",&A->data.name,&A->data.sex,&A->data.mate,&A->data.birthyear,&A->data.alive,fatherName);

    if(A->data.sex!=1&&A->data.sex!=0){

        printf("性别输入有误！\n");

        free(A);

        A=NULL;

        return;

    }

    if(A->data.alive!=1&&A->data.alive!=0){

        printf("生存状况输入有误！\n");

        free(A);

        A=NULL;

        return;

    }

    if(A->data.birthyear>2021||A->data.birthyear<0){

        printf("出生年份输入有误！\n");

        free(A);

        A=NULL;

        return;

    }

    searchNode(T,fatherName,&B);

    if(B==NULL){

        printf("此人的父亲不在家谱里！\n");

        free(A);

        A=NULL;

        return;

    }

    if(B->data.seniority!=0&&B->data.birthyear>=A->data.birthyear){

        printf("出生不能比父亲早\n");

        free(A);

        A=NULL;

        B=NULL;

        return;

    }

    insertNode(&B,&A);

    printf("插入成功\n");

    A=NULL;

    return;

}



void search(){

    char name[20];

    printf("请输入姓名:");

    scanf("%s",name);

    A=NULL;

    searchNode(T,name,&A);

    if(A==NULL){

        printf("不存在名为%s的人\n",name);

        return;

    }

    showCSTNode(&A);

    A=NULL;

}



void deleteNode(){

    A=NULL;

    char name[20];

    printf("请输入姓名:");

    scanf("%s",name);

    searchNode(T,name,&A);

    if(A==NULL){

        printf("不存在名为%s的人\n",name);

        return;

    }

    deleteCSTNode(&A);

    A=NULL;

printf("已删除\n");

}





void changeNode(){

    A=NULL;

    char name[100];

    printf("请输入姓名:");

    scanf("%s",name);

    searchNode(T,name,&A);

    if(A==NULL){

        printf("不存在名为%s的人\n",name);

        return;

    }

    changeCSTNodeimf(&A,T);

    A=NULL;

}





void relationship(){

    B=NULL;

    A=NULL;

    char name[20];

    printf("请输入姓名:");

    scanf("%s",name);

    searchNode(T,name,&B);

    if(B==NULL){

        printf("不存在名为%s的人\n",name);

        return;

    }

int choice;

    C:system("cls");

    showCSTNode(&B);

    printf("\n");

    printf("你想选择哪个关系?\n");

    printf("\n");

    printf("********************************\n");

    printf("\n");

    printf("    1.祖先     2.后代\n");

    printf("\n");

    printf("    3.堂兄弟       \n");

    printf("\n");

    printf("********************************\n");

    printf("\n");         

printf("请输入序号：\n");

while(1){

scanf("%d",&choice);

if(choice>0&&choice<4)

break;

else{

printf("请重新输入(1-3)");

}

}

    switch(choice)

    {

        case 1:

            A=B->father;

            for(;A->data.seniority!=0;A=A->father){

                printf("[%d|%d|%s]\n",A->data.seniority,A->data.birthyear,A->data.name);

            }

            system("pause"); goto C;

        case 2:

            PrintTree(B);

            system("pause"); goto C;

        case 3:

            inorderCousin(T,B);

            system("pause"); goto C;

       

    }

    B=NULL;

    A=NULL;

    return;

}



void searchrelacen(){//三代关系

    A=NULL;

    B=NULL;

    char name[100];

    printf("请输入姓名1:");

    scanf("%s",name);

    searchNode(T,name,&A);

    if(A==NULL){

        printf("不存在名为%s的人\n",name);

        return;

    }

    printf("请输入姓名2:");

    scanf("%s",name);

    searchNode(T,name,&B);

    if(B==NULL){

        printf("不存在名为%s的人\n",name);

        A=NULL;

        return;

    }

    CSTree temp=NULL;

    if(A->data.birthyear>B->data.birthyear){

        temp=B;

        B=A;

        A=temp;

    }

    if((A!=T&&B!=T)&&A==B->father){

        printf("%s是%s的父亲\n",A->data.name,B->data.name);

        if(B->data.sex){

            printf("%s是%s的儿子\n",B->data.name,A->data.name);

        }

        else

        {

            printf("%s是%s的女儿\n",B->data.name,A->data.name);

        }   

        printf("关系：三代内直系\n");

    }

    else if((A!=T&&B!=T)&&A==B->father->father){

        printf("%s是%s的爷爷\n",A->data.name,B->data.name);

        if(B->data.sex){

            printf("%s是%s的孙子\n",B->data.name,A->data.name);

        }

        else

        {

            printf("%s是%s的孙女\n",B->data.name,A->data.name);

        }   

        printf("关系：三代内直系\n");

    }

    else if((A->data.seniority>1&&B->data.seniority>1)&&A->father==B->father){

        

        if(A->data.sex){

            printf("%s是%s的堂兄\n",A->data.name,B->data.name);

        }

        else

        {

            printf("%s是%s的堂姐\n",A->data.name,B->data.name);

        }   

        if(B->data.sex){

            printf("%s是%s的堂弟\n",B->data.name,A->data.name);

        }

        else

        {

            printf("%s是%s的堂妹\n",B->data.name,A->data.name);

        }   

        printf("关系：三代内旁系\n");

    }

    else if((A->data.seniority>1&&B->data.seniority>1)&&A->father==B->father->father){

        

        if(A->data.sex){

            printf("%s是%s的叔叔\n",A->data.name,B->data.name);

        }

        else

        {

            printf("%s是%s的姑妈\n",A->data.name,B->data.name);

        }   

        if(B->data.sex){

            printf("%s是%s的侄子\n",B->data.name,A->data.name);

        }

        else

        {

            printf("%s是%s的侄女\n",B->data.name,A->data.name);

        }   

        printf("关系：三代内旁系\n");

    }

    else

    {

        printf("关系：%s,%s两者非三代内旁系或直系\n",A->data.name,B->data.name);

    }

    A=NULL;

    B=NULL;

    

}



void Meau0(){

printf("\t| -----------------------------------------------------------  |\n");

printf("\t|              家谱系统                       |\n");

printf("\t| -----------------------------------------------------------  |\n");

printf("\t| ***********************************************************  |\n");

printf("\t| *                                                         *  |\n");

printf("\t| *      提示:此家谱采用孩子兄弟表示的树存储形式            *  |\n");

printf("\t| *                                                         *  |\n");

printf("\t| ***********************************************************  |\n");

}

void Meau1(){

printf("\t| -----------------------------------------------------------  |\n");

printf("\t|                       操作选择界面                           |\n");

printf("\t| -----------------------------------------------------------  |\n");

printf("\t| ***********************************************************  |\n");

printf("\t| *                          *                              *  |\n");

printf("\t| *      1.新建人物          *     2.删除人物               *  |\n");

printf("\t| *                          *                              *  |\n");

printf("\t| ***********************************************************  |\n");

printf("\t| *                          *                              *  |\n");

printf("\t| *      3.修改人物信息      *     4.查找人物               *  |\n");

printf("\t| *                          *                              *  |\n");

printf("\t| ***********************************************************  |\n");

printf("\t| *                          *                              *  |\n");

printf("\t| *      5.人物关系查询      *     6. 判断两人关系          *  |\n");

printf("\t| *                          *                              *  |\n");

printf("\t| ***********************************************************  |\n");

printf("\t| *                          *                              *  |\n");

printf("\t| *      7.打印树状家谱      *     8.层次遍历家谱           *  |\n");

printf("\t| *                          *                              *  |\n");

printf("\t| ***********************************************************  |\n");

printf("\t----------------------------------------------------------------\n");

}        

int main()

{



int choose;//功能选择按钮

Meau0();

system("pause");

system("cls");

init();

system("pause");

system("cls");

do

{

Meau1();

printf("请选择相应的操作:");

scanf("%d", &choose);

while (1)

{

if (choose < 1 || choose>9)

{

printf("输入有误，请根据你的功能重新选择对应操作:");

scanf("%d", &choose);

}

else break;

}

switch (choose)

{



case 1:system("cls"); insertNewNode(); break;//插入人物

case 2:system("cls"); deleteNode(); break;//删除人物

case 3:system("cls"); changeNode(); break;//修改人物

case 4:system("cls"); search();; break;//查找人物

case 5:system("cls"); relationship();break;//判断两人关系

case 6:system("cls"); searchrelacen();break;//查三代关系

case 7:system("cls"); PrintAsTree(T); break;//打印人物

case 8:system("cls"); PrintTree(T);break;//层次遍历

}

int t;

printf("是否返回选择界面(1:是，0:否):");

scanf("%d", &t);

while (1)

{

if (t == 0) {

printf("已成功退出系统。\n");

exit(0);

}

else if (t == 1) break;

else {

printf("选择错误，请重新确定你的输入:");

scanf("%d", &t);

}

}

system("cls");

} while (1);

return 0;

}

H.txt文档

张一 1 无 1500 1 无

张二 1 无 1501 1 无

张三 1 李一 1520 1 张一

张四 1 无 1522 1 张二

张五 1 李二 1523 1 张三

张六 1 李三 1558 1 张三

张七 1 无 1569 1 张四

张八 1 李四 1583 1 张七

张九 0 无 1584 1 张七

张十 1 无 1585 1 张五

张十一 1 无 1586 1 张五

张十二 0 无 1587 1 张五

张十三 0 无 1596 1 张六

张十四 1 李五 1598 0 张六

张十五 1 无 1600 1 张六

张十六 1 无 1605 1 张六

张十七 0 无 1620 1 张六

张十八 1 李六 1625 1 张八

张十九 1 无 1635 0 张十四

六、实验结果

实验用例为H.txt

（1）家谱系统界

1.插入人物

成功案例：

不成功案例：

2.删除人物

成功案例：删除张时

不成功案例：

3.修改人物信息

1名字

2性别

3配偶名字

4出生年份

5辈分

4.查找

成功案例：

不成功案例：

人物关系查询

1.祖先

2后代

3堂兄弟

5.判断两人关系

6.打印树状家谱

7.层次遍历打印家谱

七、小结

通过此次数据结构的课程设计，直正达到了学与用的结合，增强了我对二叉树方面应用的理解和掌握。

虽然是用孩子兄弟法表示家谱，但其本质也是特殊的二叉树；在实验过程中，从需求分析，到概念设计，懂得了不少有关项目建设的知识，包括，插入、删除、修改、查询之间的联系，都用到很多关

键的知识点。整个程序和以往所编的程序较大的区别就是要求从文件读入信息，文件是 C语言中较为重要的部分，通过课程设计，加深了对文件知识的掌握。我的课程设计原先是只能从固定的一个文件读入图的

信息，经过修改，它可以通过直接代码执行来提取文件，使程序更加灵活，功能更加完善。在学习过程中，我也能过上网查了不少资料，学以致用，自我创新，独立完成了这份自己的报告，从中在学到用，从用又到学，不断修改，系统更新。虽然不能达到完善系统，但也做到了尽善尽美，加强理论学习对完善系统会有很多帮助。通过此次课程设计还提高了一点改错能力，对于一些常见问题加深了印象。每次课程设计都会有多多少少的收获，这些收获将成为以后学习中一笔不可或缺的财富。