C++语言: 二叉树实现的简单家谱树

/

File Name: BiTreecpp

Author: Geng Lequn[glq2000@126com]

Thur July 1 2010

Discription: 建立二叉家谱树,实现输入任意两个人的名字,查找得到其关系

/

#include <iostream>

#include <string>

#include <cstring>

#include <cstdlib>

#include <vector>

#include <mathh>

using namespace std;

typedef struct _Node

{

string sex; //性别 m 男; f 女

string name; //此人的姓名

string spause; //配偶的姓名

unsigned short level; //层次 辈分最高一层为1,下一层为为2,以此类推

struct _Node l_child; //指向其第一个孩子的指针

struct _Node r_brother; //指向其某一个兄弟姐妹的指针, 即左孩子为其后代,右孩子为其兄弟姐妹

struct _Node btr; //指向其父亲或者母亲的指针

_Node():level(0),l_child(NULL),r_brother(NULL),btr(NULL){cout<<"constructor"<<endl;}

~_Node(){cout<<name<<" destructor"<<endl;}

}Node, PNode;

void CreateBiTreePreOrder(PNode &pn, PNode pback, unsigned short depth);//建立二叉家谱树,以先序方式

void VisitBiTreePreOrder(PNode root); //前序遍历此二叉树

void TellRelation(PNode root); //判断两人关系

void DestroyBiTreePostOrder(PNode root); //销毁二叉树,释放节点占用的空间

void FindPersonMiddleOrder(PNode root, string name, PNode &presult); //返回家谱中指向某人的指针,找不到返回NULL

Node root=NULL; //全局变量,二叉树的根节点

unsigned findPersonFlag = 0; //标志位,0 没找到; 1 找到,找到后就不再搜索直接返回;利用此flag可避免将整个tree遍历一遍(若该name在tree中存在的话)

int main()

{

cout<<"请按先序遍历的顺序根据提示输入家谱信息,不存在则输入\"#\""<<endl;

CreateBiTreePreOrder(root, NULL, 1);//建立二叉家谱树,以先序方式

VisitBiTreePreOrder(root); //前序遍历此二叉树

TellRelation(root); //判断两人关系

DestroyBiTreePostOrder(root); //销毁二叉树

getchar();getchar();getchar();

return 0;

}

/

function:建立二叉家谱树,以先序方式

argument:

pn: 指向二叉树节点的引用

pback: pn这个节点的btr指针的值,即指向其parent的指针

depth: 该节点的层次,分最高一层为1,下一层为为2,以此类推

/

void CreateBiTreePreOrder(PNode &pn, PNode pback, unsigned short depth)

{

string str;

cin>>str; //输入该人信息,格式是 sex-name-spausename,如不存在则输入#

if(str == "#") //如: M-tom-marry, 表示此人叫tom, 男性, 配偶名字marry

{

pn = NULL;

return;

}

//如果是自定义的struct/class，应该使用构造函数。如果是内建数据类型，

//比如int，应该memset。 当然，更好的建议是使用vector取代new出来的数组

pn = new Node;

//处理输入的字符串

vector<string> v;

for(size_t b=0, e=strfind('-'); ; e=strfind('-', b))

{

if(e == string::npos)

{

vpush_back(strsubstr(b));

break;

}

else

vpush_back(strsubstr(b, e-b));

b = e+1;

}

//初始化该节点

pn->sex = v[0];

pn->name = v[1];

pn->spause = v[2];

pn->btr = pback;

pn->level = depth;

//递归建立左右子树的节点

CreateBiTreePreOrder(pn->l_child, pn, depth+1); //注意后两个参数的值

CreateBiTreePreOrder(pn->r_brother, pback, depth); //注意后两个参数的值

}

/

function: 前序遍历此二叉树

/

void VisitBiTreePreOrder(PNode pn)

{

if(!pn)

return;

cout<<endl<<"sex:"<<pn->sex<<endl;

cout<<"name:"<<pn->name<<endl;

cout<<"spause:"<<pn->spause<<endl;

cout<<"level:"<<pn->level<<endl;

cout<<"father's name:"<<((pn->btr == NULL)"NULL":pn->btr->name)<<endl;

cout<<"======================"<<endl;

VisitBiTreePreOrder(pn->l_child);

VisitBiTreePreOrder(pn->r_brother);

}

/

function: 中序遍历找到家谱中的一个人,返回其指针,若找不到,返回NULL

isSpause 1表示是找到的节点的配偶 0表示不是所找到的节点的配偶

/

void FindPersonMiddleOrder(PNode pn, string name, PNode &presult)

{

if(!pn)

return;

FindPersonMiddleOrder(pn->l_child, name, presult);

if(findPersonFlag) return;

if(name == pn->name || name == pn->spause)

{

presult = pn;

findPersonFlag = 1; //全局标志位,0 没找到; 1 找到,找到后就不再搜索直接返回;利用此全局flag可避免将整个tree遍历一遍(若该name在tree中存在的话)

return; //下次使用前不要忘记置为0

}

FindPersonMiddleOrder(pn->r_brother, name, presult);

}

/

function: 判断两人关系,若两人中至少一人不在树中,则两人无关系

若两人在树中,先判断两人是否同层次,若同层,判断是否是亲兄弟姐妹;

若不同层,设辈分大的人为A,辈分小的人为B,判断A和B是亲的还是表的,

比如,A为男性,且比B大一倍,判断A是否为B的爸爸,或亲叔叔(舅舅),或表叔叔(舅舅)

简单起见,此处没有区分是叔叔还是舅舅

比如,A为男性,且比B大两倍,判断A是否为B的亲爷爷(姥爷),或亲爷爷(姥爷)的亲兄弟

,或亲爷爷(姥爷)的表兄弟

简单起见,此处没有区分是叔叔和舅舅等做进一步区分

简单起见,查询时只输入节点中的name,不查询spause,否则处理起来太麻烦

/

void TellRelation(PNode pn)

{

string name1, name2;

//p1指向name1, p2指向name2, pbig指向辈分大的,psmall指向辈分小的

PNode p1 = NULL, p2 = NULL, pbig = NULL, psmall = NULL;

int differ = 0; //两人辈分数的差别

string title;

Label:

cout<<endl<<"输入想查询关系的两个人的名字,不想查则将两人名字输成#:"<<endl;

while(cin>>name1 && cin>>name2)

{

if(name1=="#" && name2=="#") return;

p1 = NULL; p2 = NULL; //因为程序是循环执行的,需要将上次遗留的值清掉

findPersonFlag = 0;

FindPersonMiddleOrder(root, name1, p1);

findPersonFlag = 0;

FindPersonMiddleOrder(root, name2, p2);

if(!p1 || !p2) //若有一个为空或都为空,说明至少有一个人不在家谱中,故两人无亲缘关系

{

cout<<name1<<((!p1)" 不在":" 在")<<" 家谱树中"<<endl;

cout<<name2<<((!p2)" 不在":" 在")<<" 家谱树中"<<endl;

cout<<name1<<" 和 "<<name2<<" 间没有关系"<<endl<<endl;

goto Label;

}

differ = (int)abs(p1->level - p2->level);

if(!differ) //辈分一样大

{

if(p1->sex == p2->sex)

{

if(p1->sex == "M") title = "兄弟关系";

else title = "姐妹关系";

}

else title = "兄妹(姐弟)关系";

if(p1->btr == p2->btr) //parent相同

cout<<name1<<" 和 "<<name2<<" 间是 "<<" 亲 "<<title<<endl;

else

cout<<name1<<" 和 "<<name2<<" 间是 "<<" 表 "<<title<<endl;

}

else //辈分不一样大

{

if(p1->level < p2->level) {pbig = p1; psmall = p2;}

else {pbig = p2; psmall = p1;}

switch(differ)

{

case 1:

if(psmall->btr == pbig)

title = ((pbig->sex == "M")"爸爸":"妈妈");

else

{

if(psmall->btr->btr == pbig->btr)

title = ((pbig->sex == "M")"亲叔(舅)":"亲姑(姨)");

else

title = ((pbig->sex == "M")"表叔(舅)":"表姑(姨)");

}

break;

case 2:

if(psmall->btr->btr == pbig)

title = ((pbig->sex == "M")"爷爷(姥爷)":"奶奶(姥姥)");

else

{

string tmp = ((pbig->sex == "M")"兄弟":"姐妹");

if(psmall->btr->btr->btr == pbig->btr)

title = ((psmall->btr->btr->sex == "M")"爷爷(姥爷)的亲":"奶奶(姥姥)的亲") + tmp;

else

title = ((psmall->btr->btr->sex == "M")"爷爷(姥爷)的表":"奶奶(姥姥)的表") + tmp;

}

break;

default:

string tmp2;

PNode pt = psmall;

int n = differ-2; //计算"老"字 (即grand这个字) 出现的个数

for(int i=0; i<n; ++i)

tmp2 += "老";

for(int i=0; i<differ; ++i)

pt = pt->btr;

if(pt == pbig)

title = tmp2 + ((pbig->sex == "M")"爷爷(姥爷)":"奶奶(姥姥)");

else

{

string tmp3 = ((pbig->sex == "M")"兄弟":"姐妹");

if(pt->btr == pbig->btr)

{title = tmp2 + ((pt->sex == "M")"爷爷(姥爷)的亲":"奶奶(姥姥)的亲"); title+=tmp3;}

else

{title = tmp2 + ((pt->sex == "M")"爷爷(姥爷)的表":"奶奶(姥姥)的表"); title+=tmp3;}

}

break;

}

cout<<pbig->name<<" 是 "<<psmall->name<<" 的 "<<title<<endl;

}

goto Label;

}

}

/

function: 后序遍历销毁此二叉树,释放节点占用的内存空间

/

void DestroyBiTreePostOrder(PNode pn)

{

if(!pn) return;

DestroyBiTreePostOrder(pn->l_child);

DestroyBiTreePostOrder(pn->r_brother);

delete pn;

}

在亿图图示中，点击组织结构图，里面有绘制家谱/树形图的功能。

直接点进去就可以绘制的，操作十分的简单，还有现成的模板可以使用。制作家谱图，可以用来有效地展示你的家族历史。首先从最高辈分的人开始画，排布出他的子女，然后每一代创建一个家庭树分支。通过简单加工与整理就可以把这个图变成一个值得展览的艺术品，或者保存给子孙后代，让家族文化世代传承。

岳飞后裔统一字谱：

自二十二世起用：

重开奇秀，永佐朝邦；崇修（德）喜彩，忠（增、宗）耀远光；英贤辅弼，金玉其相；武穆家风，山高水长。

你有家谱的话，查一查你是第几世，延续下就行了。

本人也是忠武穆后裔，家里就有家谱。我们这一支是岳霆次子岳玙河南获嘉县后裔：

从二十五世起：

士在植步尔，绍学修希凤，会全思成忠，宪君北陶恢。本人凤字辈，是岳飞第三十四世孙。

各地都有不同的字谱，我给你搜集了一下，你看看自己能套用上那一套。

岳云长子岳甫湖南益阳后裔：

自十九世起：

时太灵山锤异最，青云志上佐朝廷。文章大启宏诗礼，敬作承先肇本宁。绪守虞衡常念祖，道宗孔孟重传经。安邦定国资家教，伟烈丰功耀鼎铭。

岳云长子岳甫山东临沂市后裔：

自三十世起：

忠孝国祯，仁义端祥，思承厚德，嗣绪永昌。

岳雷次子岳纬山东莘县观城后裔：

自二十三世起：

钟际林肇锡，新然有三振，国法九世清，训谟广垂统，继述善守成，嗣绪其永昌。

岳雷次子岳纬河南原阳县后裔：

自二十七世起：

良富廷远美（连），光生（继）王茂荣，和平传世广，积德显芳铭。

岳雷四子岳纪云南贵州后裔

从十三世岳俊青起：

俊桂锐宗乾，钟天山应连，忠勋铭玉鼎，朝廷保英贤，泰衡贻世泽，华蒿显万年，文武靖大国，礼义修徵传。鲁鄂根深固，西南茂荣繁，怀笑平安福，家兴祖德权。

岳雷四子岳纪贵州赫章县后裔：

自十五世起：

想宗辅钟，天祜应连，祥世振朝，都远绍克，佳智宏开，顺琼恒良。崇恩敬先，盈禄寿康，绪维豫汤，育衍云贵，恭俭承继，孝信守章。博学萃林，财隆盛旺，锦誉浩扬。

岳霖长子岳琮河南巩义市后裔：

从十八世起：

生景国进，三元承志，五德世稀，克绍祖法，光显玉玑。

岳霖长子岳琮洛阳寺里碑后裔：

从二十一世起：

崇钟惟生，文至德显，忠绳先启后，明道成义荣前耀昆。

岳霖次子岳琛山东桓台县后裔：

从二十二世开始：

毓德振宗，端本可大，维道乃兴，念祖先发，儒业传家，英俊华国。

岳霖三子岳珂河南平顶山后裔：

从二十八世起：

功德勋业广，荣庆福寿长，宗士恭忠雅，耀仁承志祥，远华锦茂润，贤彩秀繁昌。

岳霖三子岳珂江西南昌后裔：

从二十六世起：

崇修喜彩、忠耀远贤，开昌启运。

岳霖三子岳珂山东安丘北张洛后裔：

自三十世起：

维武乃言，广济世传。

岳霖三子岳珂江苏丰县后裔：

自二十二世始：

重开奇才，永佐朝邦。崇修喜彩，宗耀远贤。慎怀先志，恭俭世绵。树春久常，兴玉传广。彦兆龙继，金少敏昌。万代有绪，同起凤翔。建华景峻，东西明光。保法良成，文会宪章。

山东曲阜、泗水后裔

从二十六世始：

绪本西都衍, 东千顺大明

岳震三子岳玭四川南江流溪房、强家岭后裔：

从七世起：

之鼎文思绍，忠泰本一守。玖训春允魁，直（惠）儒岚腾川。宋廷中玉（毓） 秀，文光焕斗山。才华飞翰顶，荣臣登高攀。

岳震三子岳玭四川盐亭、蓬溪后裔：

从三十一世起：

定蕴崇辉兆，祥腾美庆安，显成荣锦世，嘉泽发奇元，泰德隆昌茂，阳刚耀自乾，常清守焕丕，广载久长全，舒怀开极盛，华采固维宣，肇继启光秉，文章应克传。

岳震四子岳琚湖南常德后裔：

从二十七世始：

昭右有序，载锡之光，诗书道远，仁孝泽长，宗功丕振，祖德克扬，天开宏运，万世永昌。

岳震四子岳琚湖南石门县后裔

从十六世起：

正子玉准兴，学善仕宏开，上升光万国，有志成忠怀，德业绍先祖，文章佐贤才，传家克大定，永昌庆方来，敬宋宜外振，显名在修培，敦厚可立本，纯儒应占魁。

岳震四子岳琚湖南衡东后裔、岳震四子岳琚贵州赫章白果镇后裔：

从十九派开始：

友元仲大正，尚良应永兴，文昌开万代，学士绍三登，成宪惟能继，芳规乃克绳，荣名光典策，祖德世相承。

岳震四子岳琚重庆綦江县三会后裔：

从二十三世起：

国朝兴正永，宗仕智明家。恩德承芳远，学相启人贤。万吉光廷秀，福禄寿长春。

岳霆长子岳璠湖南邵阳县后裔：

从十世起：

汝仲应元永、添志廷继文、伯大正光启、祖宗万世荣、有子经纶重、诒谋德泽新、守先延绪业、待后广修明。（根据《岳飞家史考》第七册100页和岳志勇《双清区岳飞后裔源流考记》改正）

岳霆长子岳璠安徽凤台岳张集支系：

从二十二世起：

正学传千古，人文粹一家，承先多世泽，继贤广良才。

岳霆长子岳璠安徽阜阳市后裔：

从三十世起：

崇德敬祖，福禄寿康，文显皖颍，忠衍豫汤，恭俭传世，孝信永芳，景行维端，善心循良。

岳霆次子岳玙河南遂平县马庄后裔：

从二十三世始：

蓝纲林辉全，清峰彬正文，春岭海连永，年高泽志富，祺成恒国荣。

岳霆次子岳玙河南获嘉县后裔：

从二十五世起：

士在植步尔，绍学修希凤，会全思成忠，宪君北陶恢。

岳霆次子岳玙天津宁河岳道口村后裔：

约从十七世起：

友洪真明守，秀自文可秉，九连和树广，锡士景国荣，云来庆大有，雨致喜年丰。

贵州绥阳岳氏

如国世正兴 明朝志大清

安邦元立德 美景万年春

洞庭贻谋远 江阳圣泽新

功勋昭宋殿 甘露兆天灵

河北滦县岳氏

庭余崇金成 春光绪祖先

富贵传文武 诗书纪世年

四川宜宾文兴县岳氏

可世再传后 仑钟朝上天

步登观奉启 承继向宏铮

安徽肥西县岳氏

国朝文学，甫世贤良，忠友余庆，孝本传芳

河南桐柏县岳氏

仁意力功进 万兴政清林文秀有家祥

山东威海雷系字谱

从33世开始

恭俭传世，仁孝泽长，建华景俊，文惠宪章；天开鸿运，继寿永昌，尽忠报国，万代安康。

本人李普云 ，在本族中属于云字辈。上辈属于树字辈，孙子李吉鑫属于吉字辈 。由于当今的字辈打破了常规 。加之族谱只有十余代 。因无依据 。吉字辈以后用什么字辈 。也就只能根据以后的具体情况来确定了 。。。。

目录部分1：研究你家族的历史1、写下你想要包含在图中的人。2、通过一些研究填补漏洞。3、确定你想要突出的其他信息。4、决定是否要包含照片。部分2：创建树状图1、从你们这一代开始。2、从你的父母辈填写。3、画你的祖父母那一代。4、决定你要追溯到几代之前。部分3：使其独一无二1、自己来美化你的家族树状图。2、使用软件来创建一个计算机生成的树。3、考虑让一个艺术家做一个原始的再现。制作家谱图，可以用来有效地展示你的家族史。首先从最高辈分的人开始画，找出谁是他的子女，然后每一代创建一个家庭树分支。然后加工一下，可以把这个图变成一个值得展览的艺术品，或者仅仅是为了保存给子孙而制图，世世代代传下去。请参阅步骤1开始。

部分1：研究你家族的历史

1、写下你想要包含在图中的人。家谱从你的家庭开始，家谱树从那里出来分支出来。首先写下你的直系亲属人的名字，然后移动到你的上一代。请确保你没有遗漏的人！你的家谱将是你家族历史的一个重要部分，所以需要时间来建立一个准确的图。写下你的名字，你的兄弟姐妹的名字，和你父母的名字。

写下你的祖父母的名字，你叔叔阿姨的名字和你的表兄弟姐妹的名字。

写下你的曾祖父母的名字和你大叔叔阿姨的名字。

很多人在那里就停止了，但只要你想，你就可以尽可能多的多画几代。

2、通过一些研究填补漏洞。一旦你追溯到前几代，填名字可能就比较困难了。努力确保每个人都有包括在内、所有的名字是准确的，进行一些研究，仔细检查自己的家谱树。这是一个大好机会去更多地了解你的家族历史。和你的家庭老年成员谈谈，去了解更多信息。找出你的祖父母的兄弟姐妹及其配偶，子女的姓名。尽你所能问问周围的人。如果你幸运的话，你也有机会可以听到一些奇怪的家庭故事和秘密了。

用家谱工具在网上做研究。网上有很多工具，你只需输入你的名字和你父母的名字，然后会为你做所有的研究调查。这些网站通常给你一个有限的可用信息量，然后你需要更多的深入研究。如果你是认真在绘制你的祖先，这是一个很好的方式来收集信息。

3、确定你想要突出的其他信息。此外，要包括你家人的姓氏和名字，你可能想要列出他们的出生日期，死亡日期（如适用），注册结婚日期，等等。在家族树上有了这些日期会有更加详细的信息作为你的家人的一个历史文件。除了日期，你可以考虑，包括你的亲人"的发祥地和家乡。

4、决定是否要包含照片。如果你有机会得到你祖先的照片，在每个人上面你可以有一个小小的肖像。相对包含的话此选项最适合家庭树，因为照片可能会占用很多的空间在你的成品图上。如果你只有几张照片，你可以只包含你的直系家庭成员的照片。

尽可能多的追查家族成员的照片。如果你想使他们所有的照片大小相同，扫描到您的计算机。使用PS或其他照片编辑程序来更改比例。

部分2：创建树状图

1、从你们这一代开始。这是树的基础上，包括你，你的父母，你的兄弟姐妹。图的形状会是你的选择。如果你想让它另辟蹊径垂直，并延续向浓密的上方，像一棵树，从一大张纸的底部开始。你也可以开始于一张纸的左边，这样的图将很容易从左侧看向右侧。无论你希望你的图是什么形状，填写以下信息即可开始：写下你的名字。

画一条线从你的名字到你母亲的名字。从你的名字到你父亲的名字再画另一条线。画一条水平线连接你的母亲和父亲。

如果你有兄弟姐妹，画一条线从你父母的名字到他们的名字。

如果你的兄弟姐妹有配偶，把他们名字写上，并用线连接起来。

如果你的兄弟姐妹有孩子，把他们名字写上，并用线将他们连接起来。

2、从你的父母辈填写。现在是时候填写第二代-你的父母辈。连接横线在每个已婚夫妇上，然后连接一条线向他们的孩子。写你外公外婆的名字在你妈的名字上面。写你的祖父母的名字在你父亲的名字上面。

把你的外公外婆的名字和你妈的兄弟姐妹名字姐连接起来。把你的祖父母的名字和你父亲的兄弟姐妹的名字连接起来。

添加你叔叔阿姨配偶的名字。

添加你叔叔阿姨的孩子，你的表兄弟姐妹的名字。

3、画你的祖父母那一代。如果你有一个大的家庭，你的图可能已经有要投奔的页面边缘的威胁了。有些人停在了这里，有两组祖父母作为他们家谱图中的树冠。如果你想继续前进，是时候包括你的祖父母那一代了。记住要连接已婚夫妇是水平线，然后话一条线连接家长和子女。添加你的外祖母的父母亲和你祖外公的父母亲的名字。这是你的曾祖父母。

添加你的曾祖母的父母亲和你曾祖父的父母亲的名字。这是你的曾曾父母。

添加您的外祖父母的兄弟姐妹的名字-你的叔外祖父叔外祖母

添加你的祖父母的兄弟姐妹的名字-你的舅爷和姨奶奶。

填写你叔外祖父母的配偶和子女的姓名。

4、决定你要追溯到几代之前。如果你正在享受你研究家族历史的经验，尽你所能不断追溯就可以。没有限制你的家族树状图的潜在规模，尤其如果是它的数量！

部分3：使其独一无二

1、自己来美化你的家族树状图。现在你的图完成了，该考虑把它艺术化就可以自豪地与您家里的其他人分享。用铅笔复制家谱图在一大张绘制图上，然后用漂亮的墨水或油漆呈现出名称，并添加丰富多彩的装饰。您可以选择使用经典的树的形状，或尝试一些新的创意来说明你的祖先。这里有几个想法：把连接线分行，并在不同的叶子上写下每个人的名字。孩子的名字也可以写在苹果或浆果上。

使你的家族谱画成一个星系，并在行星和恒星写上大家的名字。如果你想也可以把你的名字写在"太阳"上。

创建你的家族谱成为一个家庭邻里，在每一个小房子上写下每个人的名字，全部由街道相连。

2、使用软件来创建一个计算机生成的树。如果你想让你的图看起来优美，但你不希望自己来创建，从网上选择有数以百计的选择。搜索"免费家谱"拿出模板或自动生成的图表，你可以打印出来，挂在墙上。

3、考虑让一个艺术家做一个原始的再现。找一个艺术家来呈现你的家谱作为一个原始艺术的美丽作品。您可以选择用书法的方式写上名字，并已对其中设定一个华丽的背景。如果你做一个网上搜索"家谱艺术家"，你会发现艺术家的名单可以委托他们制作。，在不同的组合仔细看，找到一个艺术家的作品适合你家的风格。