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

57 阅读 0 评论 38 点赞

我是靠谱客的博主从容寒风，最近开发中收集的这篇文章主要介绍用二叉树表示家谱关系并实现各种查找功能，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

/**
* 实验题目:
* 用二叉树表示家谱关系并实现各种查找功能
* 实验目的:
* 掌握二叉树遍历算法的应用，熟练使用先序、中序、后序3种递归
* 遍历算法进行二叉树问题求解。
* 实验内容:
* 设计程序，采用一颗二叉树表示一个家谱关系(由若干家谱记录构成，每个
* 家谱记录由父亲、母亲和儿子姓名构成，其中姓名是关键字)。要求程序具有如下
* 功能:
* 1、文件操作功能:家谱记录输入，家谱记录输出，清除全部文件记录和将家谱记录
* 存盘。要求在输入家谱记录时按祖先到子孙的顺序输入，第一个家谱记录的父亲域
* 为所有人的祖先。
* 2、家谱操作功能:用括号表示法输出家谱二叉树，查找某人所有儿子，查找某人所有
* 祖先(这里的祖先是指所设计的二叉树结构中某结点的所有祖先结点)。
* 备注:由于家谱是一颗树结构，而不是一颗二叉树，所以在存储时要转换成二叉树的形式，
* 这里规定:一个父亲结点的左孩子结点表示母亲结点(父亲结点无右孩子结点)，母亲结点
* 的右子树表示他们的所有儿子等。
* 基本结构如图所示:
* 父
* /
* 母
*
* 子1
* /
* 媳1 子2
* /
* 媳2 子3
* /
* 媳3
*/

#include <stdio.h>
#include <malloc.h>
#include <string.h>

#define MAX_SIZE (30) // 栈的最大元素个数
#define NAME_WIDTH (10) // 姓名的最多字符个数

typedef struct fnode
{
char father[NAME_WIDTH]; // 父亲姓名
char wife[NAME_WIDTH]; // 母亲姓名
char son[NAME_WIDTH]; // 儿子姓名
}fam_type; // 家谱文件的记录类型

typedef struct tnode
{
char name[NAME_WIDTH]; // 姓名
struct tnode *lchild; // 左孩子指针
struct tnode *rchild; // 右孩子指针
}btree; // 家谱二叉树结点类型

static int n; // 家谱记录个数
static fam_type fam[MAX_SIZE]; // 家谱记录数组

/*---------------------家谱二叉树操作算法------------------*/
/*---------------------从fam(含n个记录)递归创建一颗二叉树------------------*/
static btree *create_btree(char *root)
{
btree *b;
btree *p;
int i = 0;
int j;

b = (btree *)malloc(sizeof(btree)); // 创建父亲结点
strcpy(b->name, root);
b->lchild = b->rchild = NULL;
while(i < n && strcmp(fam[i].father, root) != 0)
{
i++;
}

if(i < n) // 找到该姓名的记录
{
p = (btree *)malloc(sizeof(btree));
p->lchild = p->rchild = NULL;
strcpy(p->name, fam[i].wife);
b->lchild = p;
for(j = 0; j < n; j++) // 找所有儿子
{
if(strcmp(fam[j].father, root) == 0) // 找到一个儿子
{
p->rchild = create_btree(fam[j].son);
p = p->rchild;
}
}
}

return b;
}

/*--------------------------以括号表示法输出二叉树----------------------*/
static void disp_btree(btree *b)
{
if(b != NULL)
{
printf("%c", b->name);
if(b->lchild != NULL || b->rchild != NULL)
{
printf("("); // 有孩子结点时才输出(
disp_btree(b->lchild); // 递归处理左子树
if(b->rchild != NULL) // 有右孩子结点时才输出,
printf(",");
disp_btree(b->rchild); // 递归处理右子树
printf(")"); // 有孩子结点时才输出)
}
}
}

/*--------------------------采用先序递归算法查找name为xm的结点----------------------*/
static btree *find_node(btree *b, char xm[])
{
btree *p;

if(b == NULL)
return NULL;
else
{
if(strcmp(b->name, xm) == 0)
return b;
else
{
p = find_node(b->lchild, xm); // 递归处理左子树
if(p != NULL)
return p;
else
return find_node(b->rchild, xm); // 递归处理右子树
}
}
}

/*--------------------------输出某人的所有儿子----------------------*/
static void find_son(btree *b)
{
char xm[NAME_WIDTH];
btree *p;

printf(" >>父亲姓名:");
scanf("%s", xm);
p = find_node(b, xm);
if(p == NULL)
printf(" >>不存在%s的父亲!n", xm);
else
{
p = b->lchild;
if(p == NULL)
printf(" >>%s没有妻子n", xm);
else
{
p = p->rchild;
if(p == NULL)
printf(" >>%s没有儿子!n", xm);
else
{
printf(" >>%s的儿子n", xm);
while(p != NULL)
{
printf("%10s", p->name);
p = p->rchild;
}
printf("n");
}
}
}
}

/*---------------------采用后序非递归遍历算法输出从根结点到s结点的路径------------------*/
static int path(btree *b, btree *s)
{
btree *st[MAX_SIZE]; // 定义顺序栈
btree *p;
int top = -1; // 栈指针设置初值
int i;
bool flag;

do
{
while(b) // 将b的所有左下结点进栈
{
top++;
st[top] = b;
b = b->lchild;
}
p = NULL; // p指向当前结点的前一个已访问的结点
flag = true; // flag为真表示正在处理栈顶结点
while(top != -1 && flag)
{
b = st[top]; // 取出当前的栈顶元素
if(b->rchild == p) // 右子树不存在或已被访问,访问之
{
if(b == s) // 当前访问的结点为要找的结点,输出路径
{
printf(" >>所有祖先:");
for(i = 0; i < top; i++)
printf("%s ", st[i]->name);
printf("n");
return 1;
}
else
{
top--;
p = b; // p指向被访问的结点
}
}
else
{
b = b->rchild; // b指向右子树
flag = false; // 表示当前不是处理栈顶结点
}
}
}while(top > -1);

return 0; // 其他情况时返回0
}

/*---------------------输出某人的所有祖先------------------*/
static void ancestor(btree *b)
{
btree *p;
char xm[NAME_WIDTH];

printf(" >>输入姓名:");
scanf("%s", xm);
p = find_node(b, xm);
if(p != NULL)
path(b, p);
else
printf(" >>不存在%sn", xm);
}

/*---------------------销毁家谱二叉树------------------*/
static void destroy_btree(btree *b)
{
if(b != NULL)
{
destroy_btree(b->lchild);
destroy_btree(b->rchild);
free(b);
}
}

/*---------------------家谱文件操作算法------------------*/
/*---------------------清除家谱文件全部记录------------------*/
static void del_all(void)
{
FILE *fp = NULL;

fp = fopen("fam.dat", "wb");
if(fp == NULL)
{
printf(" >>不能打开家谱文件n");
return;
}
n = 0;

fclose(fp);
}

/*---------------------读家谱文件存入fam数组------------------*/
static void read_file(void)
{
FILE *fp = NULL; // 文件指针
long len; // 家谱文件长度
int n; // 家谱文件中的记录个数

fp = fopen("fam.dat", "rb");
if(fp == NULL)
{
n = 0;
return;
}
fseek(fp, 0, SEEK_END); // 家谱文件位置指针移到家谱文件末尾
len = ftell(fp); // len求出家谱文件长度
rewind(fp); // 家谱文件位置指针移到家谱文件开头
n = len / sizeof(fam_type);// n求出家谱文件中的记录个数
for(int i = 0; i < n; i++)
fread(&fam[i], sizeof(fam_type), 1, fp); // 将家谱文件中的数据读到fam数组中
fclose(fp);
}

/*---------------------添加一个记录------------------*/
static void input_fam(void)
{
printf(" >>输入父亲、母亲和儿子姓名:");
scanf("%s %s %s", fam[n].father, fam[n].wife, fam[n].son);
n++;
}

/*---------------------输出家谱文件全部记录------------------*/
static void output_file(void)
{
int i;

if(n <= 0)
{
printf(" >>没有任何记录n");
return;
}

printf(" 父亲母亲儿子n");
printf(" ------------------------------------n");
for(i = 0; i < n; i++)
printf(" %10s %10s %10sn", fam[i].father, fam[i].wife, fam[i].son);
printf(" ------------------------------------n");
}

/*---------------------将fam数组存入数据家谱文件------------------*/
static void save_file(void)
{
int i;
FILE *fp = NULL;

fp = fopen("fam.dat", "wb");
if(fp == NULL)
{
printf(" >>数据家谱文件不能打开n");
return;
}

for(i = 0; i < n; i++)
{
fwrite(&fam[i], sizeof(fam_type), 1, fp);
}
fclose(fp);
}

/*---------------------家谱文件操作------------------*/
static void file_operation(void)
{
int sel;

do
{
printf(" >1:输入 2:输出 9:全清 0:存盘返回请选择:");
scanf("%d", &sel);
switch(sel)
{
case 1:
input_fam();
break;
case 2:
output_file();
break;
case 9:
del_all();
break;
case 0:
save_file();
break;
}
}while(sel != 0);
}

/*---------------------家谱二叉树操作------------------*/
static void btree_operation(void)
{
btree *b;
int sel;

if(n == 0) // 家谱记录为0时直接返回
return;
b = create_btree(fam[0].father);
do
{
printf(" >1:以括号表示法输出二叉树 2:找某人所有儿子 3:找某人所有祖先 0:返回请选择:");
scanf("%d", &sel);
switch(sel)
{
case 1:
printf(" >>");
disp_btree(b);
printf("n");
break;
case 2:
find_son(b);
break;
case 3:
printf(" >>");
ancestor(b);
break;
}
}while(sel != 0);

destroy_btree(b); // 销毁家谱二叉树
}

int main(int argc, char *argv[])
{
btree *b;
int sel;

read_file();
do
{
printf("*1:文件操作 2:家谱操作 0:退出请选择:");
scanf("%d", &sel);
switch(sel)
{
case 1:
file_operation();
break;
case 2:
btree_operation();
break;
}
}while(sel != 0);

return 0;
}