数据结构——家谱管理系统
一、功能要求
（1）用缩进表示法输出家谱二叉树
（2）查找某人所有的儿子
（3）查找某人所有的祖先
二、功能模块图
三、测试分析
- 系统界面
- 建立家谱
-
查询家谱树
- 查询儿子
- 查询祖先
- 退出页面
- 不合理数据
四、源码
-
singly_linked_tree.h
#ifndef SINGLY_LINKED_TREE_H
#define SINGLY_LINKED_TREE_Htypedef struct Node
{char data;int flag; struct Node* lchild;struct Node* rbrother;
}SLNode;extern SLNode* p;void Initiate(SLNode** T);
SLNode* Insertright(SLNode* arr, char x);
SLNode* Insertleft(SLNode* arr, char x);
void input(SLNode* arr);
void PrintTree(SLNode* T, int n);
void Searchchild(SLNode* T, char x);
void SearchAncestor(SLNode* T, char x);#endif-
singly_linked_tree.cpp
#include "singly_linked_tree.h"
#include <stdio.h>
#include <stdlib.h>SLNode* p;void Initiate(SLNode** T)
{*T = (SLNode*)malloc(sizeof(SLNode));(*T)->lchild = NULL;(*T)->rbrother = NULL;
}SLNode* Insertright(SLNode* arr, char x)
{SLNode* m, * t;if (arr == NULL) return NULL;if (arr->rbrother != NULL) arr = arr->rbrother;t =arr->rbrother;m = (SLNode*)malloc(sizeof(SLNode));m->data = x;m->rbrother = t;m->lchild = NULL;arr->rbrother =m;return arr->rbrother;
}
//左孩子写在右兄弟下面，因为要用左孩子调用右兄弟，编译器是顺序编译SLNode* Insertleft(SLNode* arr, char x)
{SLNode* m, * t;if (arr == NULL) return NULL;//在arr和arr->right的中间插入，为保证顺序插入需要让arr向后移一个else if (arr->lchild == NULL){t = arr->lchild;m = (SLNode*)malloc(sizeof(SLNode));m->flag = 0;m->data = x;m->lchild = t;m->rbrother = NULL;arr->lchild = m;return arr->lchild;}else Insertright(arr->lchild, x);
}void input(SLNode* arr)
{char p = 0;if (arr == NULL) return;printf("请输入%c所有的儿子结点,若没有儿子或者输完所有儿子，输入#即可:\n", arr->data);getchar();scanf("%c", &p);while (p != '#'){Insertleft(arr, p);getchar();scanf("%c", &p);}//递归兄弟结点，再递归孩子结点（使所有兄弟输完接着输兄弟的孩子）if (arr->rbrother != NULL )input(arr->rbrother);if (arr->lchild != NULL )input(arr->lchild);
}void PrintTree(SLNode* T, int n)
{int i;if (T){for (i = 1; i < n; i++) printf(" ");printf("%c", T->data);printf("\n");//左孩子n+1,整体向右推移一位，右兄弟依然是nPrintTree(T->lchild, n + 1);PrintTree(T->rbrother, n);}
}void Searchchild(SLNode* T, char x)
{SLNode* p;//要用T data和x比较，所以要保证T不为空指针if (T != NULL && T->data != x){Searchchild(T->lchild, x);Searchchild(T->rbrother, x);}//加入限定条件只允许T data==x时通过if (T != NULL && T->lchild != NULL && T->data == x){printf("%c结点的儿子结点为：%c ", T->data, T->lchild->data);p = T->lchild;while (p->rbrother != NULL){printf("%c", p->rbrother->data);p = p->rbrother;printf("\n");}}
}void SearchAncestor(SLNode* T, char x)
{if (T != NULL && T->data != x){SearchAncestor (T->lchild, x);SearchAncestor (T->rbrother, x);}//保证p为不变的指针，指向选择的结点if (T != NULL && T->data == x){p = T;}if (T != NULL && T->lchild != NULL && (T->lchild == p || T->lchild->rbrother == p)){printf("%c ", T->data);p = T;}
}int main()
{SLNode* T;char p;int n;Initiate(&T);do{printf(" \n");printf(" 家谱管理系统 \n");printf("------------------------- 功能选项 -------------------------");printf("\n\n");printf(" 【 1-开始建立家谱 】\n");printf(" 【 2-查询-家谱树 】\n");printf(" 【 3-查询-儿子 】\n");printf(" 【 4-查询-祖先 】\n");printf(" 【 0-退出系统 】\n");printf("\n\n");printf("------------------------------------------------------------"); printf("\n 请选择需要的功能(数字):");char ch;ch = getchar();switch (ch){case '1':{printf("请输入祖先结点：");getchar();scanf("%c", &p);Insertleft(T, p);input(T->lchild); getchar(); break;};case '2':{PrintTree(T, 1); getchar(); break;};case '3':{printf("请输入要查询的结点的所有儿子：");getchar();scanf("%c", &p);Searchchild(T, p); getchar(); break;};case '4':{printf("请输入要查询的结点的所有祖先：");getchar();scanf("%c", &p);SearchAncestor (T->lchild, p); getchar(); break;};case '0':exit(0);default:{printf("输入有误，请重新输入：\n");ch = getchar();}}} while (1);
}