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;

}

欧式家谱体例，是现在用得最多的家谱模式。它是北宋大文学家欧阳修家族家谱模式的简称。它的特点就是:世代分格，由右向左;五世一表，一表一提。上下为父子，左右为兄弟。1、 欧式家谱一般是一页左右十竖行，上下五层横格。上下为父子，左右为兄弟。2、上下五层横格，为五世。从上往下数，一、二、三、四、五，五世。每上下相邻的两层均为父子关系。

3、同一层横格中左右相排的人均为同辈的兄弟。以年齿论，右边的排行为长，向左依次递减为老二、老三、……。4、父亲只有一子，则竖行中父子名讳上下相对;如果父有三子，正对父亲名下的是长子，紧邻长子左边的两格则填写老二老三的名讳。5、同辈的人数较多，一页填写不完可往下页延续，但表示世系辈份的横格不能舛错，不然的话，世系辈就乱了。6、一个竖格，填写夫妇二人名讳，右边写男人名讳，左边写妻子名讳。需要加注的，名字旁边加注小字。7、首页五世，这五世不论占了几页，都是同表，都得一提。提，就是把本表最下一横层

中，第五世的所有名字，都提到下一表中最上层的第一层横格中，按原来的顺序从右到左依次排好。提的作用就是上下两表关系的承上启下，互相衔接，不致舛错、断裂。8、提到第二表的五世，领续下面的六、七、八、九四世。由于此表领续的五世是上表未世的重复，所以此表实际上只续了四世。下边后续的各表都是如此，这叫"五世一提，实续四世"。9、家族较大，

支系众多，可续完一支，再续另外一支，在卷首编好目录页码，便于日后的查阅。10、以上9项，都是世系排序的元素。世系是家谱的主要内容，除世系外，还有凡例、序言、影像、家规、题名、耆寿、节烈等诸多项目。由于各个家族具体情况不同，所以家谱编写的内容也不尽相同。

目录方法1：研究你的家族史1、了解你的族谱。2、决定追溯到多远。方法2：起草一个绘制计划1、选择纸和绘图用具。2、决定你的家谱将采取什么样的形式。方法3：绘制家谱1、用铅笔画树。2、写下你的名字。3、添加你的父母和兄弟姐妹。4、写下你的阿姨和叔叔，表兄弟姐妹，祖父母和外祖父母。5、纳入更多的人。6、用更多的细节来丰满家谱。绘制家谱可以帮助孩子们了解自己的家族史，认识曾祖父母和其他他们可能永远不会有机会见到的家庭成员。对于成年人来说，它可以是纪念逝者的一个机会，是对美好家族历史的纪念。阅读如何制作家谱的信息。

方法1：研究你的家族史

1、了解你的族谱。有些人谙熟他们的家族史，有些人则不太了解他们的祖父母，曾祖父母，表兄弟等。在制作家谱前，你需要通过以下方式进行研究并得到所有的信息：向家庭成员询问信息。如果你正在为一个学校项目制作家谱，你的父母亲也许能告诉你一切你需要了解的家庭信息。对于广泛的家族史项目，考虑寻找族谱数据库。像Familysearchorg这样的网站可能有你不知道的长期失散亲人的信息。

要彻底。如果有人被不小心遗漏掉，家谱就没有意义了。您可能要多渠道检查来源，以确保您的信息是准确的。

2、决定追溯到多远。尽可能远的追溯你的家族史是很有趣的，但是当你绘制一个家谱的时候，记录超过前几代的信息就不切合实际了。你会受到使用的纸张大小的限制，因为你需要在一个页面上写上所有的名字。很多人选择追溯到他们的曾曾祖父母和他们的兄弟姐妹，或是他们的曾祖父母和他妈的兄弟姐妹。这些是你，你的父母或是祖父母曾经见过的人，所以他们比其他的远亲跟你的联系更要密切。

如果你的家庭是有很多叔叔阿姨表兄弟等等的大家族，你可能得以更近的一代结束以把所有人写在一个页面上。如果你的家庭成员人数较少，你可以把家谱延伸到更遥远的一代。

方法2：起草一个绘制计划

1、选择纸和绘图用具。既然你正在花时间去研究和绘制你的家谱，挑选出好的绘制材料使信息能够好好的呈现出来。美术用品商店出售大型的单页纸张。选择一张坚固的、有吸引力的，比如水彩纸。

一个更方便的选择可能是一块布告牌。这种类型的纸张也单独出售，它有多种颜色。可以在药店找到它。

用铅笔来绘制家谱，并用好的钢笔或记号笔描绘。

2、决定你的家谱将采取什么样的形式。有些家谱被绘制成实际树木的形状，家庭的每个分支都有一个树枝。其他的更像是家庭图表，最终的效果像树，但家庭成员的名字并不是真的在树上叠加显示。使用你在课堂上被分配到的风格，或者干脆选择一种您喜欢的。

方法3：绘制家谱

1、用铅笔画树。设想它看起来像什么，并计划你需要写多少空间来写所有的名字和绘制必要的连接线。用铅笔工作，这样如果画错了你可以在一个树枝上重新开始。

2、写下你的名字。因为这是你的家庭树，这一切由你开始。把你的名字写在页面的一个点上，周围可以写下所有的其他名字的大量空间。写你的名字的地方就是树开始的地方。如果你把它写在页面底部，树枝就向上突出。你可以写在页面顶部，让其他部分向下分流，或把它写在页面的边上，让树在另一个方向上绽放。

如果你决定用一个实际的树的形状，行动起来，用铅笔线勾勒出的树的形状，把你的名字写在喜欢的地方。

3、添加你的父母和兄弟姐妹。把你父母的名字放在你名字的正上方或正下方，这取决于你想要让树往什么方向分流。把你的兄弟姐妹的名字写在你名字的同一水平线上，这样他们就从你父母的名字旁边延伸出来了。如果你和你的兄弟姐妹有配偶或子女，也把他们写上。配偶的名字直接写在他们的伴侣旁边，孩子的名字写在父母的名字的下面。如果你愿意就把家长和他们的孩子用线连起来。

定制适合你家庭的家谱。如果你有一个父母，或两个以上的父母时，把他们都写上。在绘制包括继父母，继兄弟姐妹和其他你家庭的一部分的成员时，你要发挥创造力。家谱最重要的方面是确保每个人都包括在内。

要精心组织你的家谱，使用有规律的顺序列出的兄弟姐妹。例如，最大的兄弟在左边，然后把所有后面的兄弟姐妹依次写在右边，反之亦然。无论哪种方式，整个家谱保持一致。

4、写下你的阿姨和叔叔，表兄弟姐妹，祖父母和外祖父母。在这里树开始分裂成分支。在父亲这边的家谱上，写下他的兄弟姐妹的名字，他们的配偶和他们的孩子（你的表兄弟姐妹）。把你父亲的父母的名字写在上一个水平线上，把一根线从他们身上延伸到他们的每一个孩子上。在你母亲那边的家谱上做同样的事，直到把所有的家庭成员都包括在内。

5、纳入更多的人。继续加入你伟大的叔叔阿姨的他们的配偶和孩子，你的曾祖父母的名字等等，只要你愿意在家谱上写的尽可能多写。

6、用更多的细节来丰满家谱。用黑色或彩色墨水把家谱重新描一遍，使名字和轮廓更加鲜明。您可以添加装饰和其他细节，使家谱更有趣。下面是一些例子：男性和女性使用不同的形状。例如，女性可以使用椭圆形，男性用矩形，或其他任何您想要的图案。这样一来，别人看你的家谱就可以一下便知不同个体的性别。

使用虚线表示离婚夫妇。通过这种方式，你仍然可以表达父母与子女之间的生物关系，即使他们没有婚姻关系。

添加出生日期及（如适用的话）死亡日期。这可以添加大量的信息，并使得家谱对于你的朋友和其他家庭成员来说更有趣。

添加每一个人履历资料，如出生地，娘家姓，中间名，等等。

小提示一个相对简单的方法是用免费的在线工具来绘制你的家庭树。

家族树是制作家谱的软件吗？

是的，家族树支持注册用户建立数字家谱，包括邀请家族人员进入家族树进行协作管理，家族成员在共有的家族空间一起体验娱乐互动应用，而且家族树还有寻根辅助功能，根据你填写的信息，自动匹配可能会是你家族成员的人。家族网还有群组、博客、相册、档案馆、姓氏百科、时间轴等多种功能。这些功能和应用使家族树中的成员有良好的互动性，增加亲人感情和家庭温情。

有什么软件做族谱最好的？可以做家族树的那种~~

这个平台，估计才是你想要的吧，这是系统后台根据每个人的关系信息，自动生成的家族树，操作起来比较繁琐，要家庭成员分别建立自己的账户，管理自己的个人信息，然后通过父母子女的关系认可进行链接，但这却是最为严谨的家族树系统，没有人可以随意修改其中成员，完全以血缘关系来形成这棵树，女孩子同样作为树的延续分枝拓展下去，而且每个人的信息都是在网络中永久保存的。。。

家族树的作用意义

其实看完这张图，大家就会有一些概念了，让家族的每一个成员都可以对自己的亲人关系一目了然，或许有些人已经开始疏远，但是他们之间都是有着不可改变的血缘关系，其中每一个人，也各自记录自己一生的精彩，可以让血脉后人可以有所认知。。。

求一张英语家庭树，简单一点的~

英语家庭树如下：

称谓介绍：

一、mum

1、含义：n <英口>妈妈，母亲。

2、用法

作名词含有沉默，<口>妈咪，妈，妈妈，烈性啤酒，摩姆啤酒，马姆酒，<口>菊花（=chrysanthemum）等意思。

If your Mum finds out what you've done, you'll really be in the soup!

要是你妈妈发觉你干的事，你就要倒霉了！

Your mum will go spare if she finds out what you've done!

要是你妈妈知道你干的事，她会气坏的！

二、dad

1、含义：n 爸爸。

2、用法

作名词含有<口>爸爸，爹爹，老兄，老弟，老伙计，任何老年人，一大块；一大片；一大份，有力的一击(或一拳)等意思。

Dad was snoozing by the fire

爸爸正在炉火旁打盹。

Mom and dad never see eye to eye on anything

妈和爸从来没有对任何一件事有一致的看法。

三、brother

1、含义：n 兄弟；教友；同胞；<俚>老兄。

2、用法

brother指“兄”或“弟”皆可，“兄”是“elder brother”,“弟”是“younger brother”。但除了必须分清是“兄”还是“弟”时外，习惯上不论“兄”还是“弟”，都用brother。

在美国通常不用elder brother，而用older brother。与brother相对应的阴性名词是sister。

brother可指亲兄弟，也可指同父异母或同母异父兄弟，或继父与其前妻或继母与其前夫之子，不指堂或表兄弟。但引申可指“同行，同事”解。

brother作“教友”“会友”解时，它的复数形式是brethren。

brother可用作称呼语。

John and Peter are brothers

约翰和彼得是兄弟。

The man who captained the home team is my brother

率领主队的是我的兄弟。

四、sister

1、含义：n 姐妹。

2、用法

sister的意思是“姐，妹”，通常指同胞姐妹，包括同父异母或同母异父的姐妹。

在西方，“姐姐”和“妹妹”都叫sister，只有需要特别表明年龄大小时或其他必要情况下，才分为elder sister和younger sister。堂姐妹应说cousin。

sister有时还可指“(掌管病房的)护士，护士长”“(修道院的)修女”。

在口语中， sister可用于称呼女子； 在正式文体中， sister可用于比喻。

Joan and Lily are sisters

琼和丽丽是姐妹。

You should take care of your niece for the sake of your sister

看在姐妹的份上，你应该照顾你的侄女。

五、aunt

1、含义：n 伯母；姑；婶；姨。

2、用法

aunt指与父母亲同辈的女性亲属，即父母亲的姐妹“姑母，姨母”或父母亲兄弟的妻子“伯母，婶母，舅母”。与其对应的阳性名词是uncle。

aunt用于口语中还常指小孩对成年女邻或父母亲的朋友、同事中的成年女性的称呼。

aunt是普通名词，但当其与表示人名的专有名词连用时，首字母须大写。

习惯上人们用aunt指代了全部的伯母，姑姑，婶婶，姨母和舅母，不会特地去区别。若是在必要区分的场合时，paternalaunt（父方的）指得是伯母，姑姑和婶婶，而maternalaunt（母方的）指得是姨母和舅母。

She has no relations besides an aged aunt

她除了有一个年老的伯母以外，再没有亲戚了。

My aunt gave me one of her brooches as a keepsake

我姑母把她的一支胸针送给我作记念。

家族树是由什么组成的？

家族树是家族网团队研发的一项应用，它就好比是一个树状的数字家谱，用户在树上可以进行沟通互动娱乐等。

具体来说呢， 家族树，是指利用互联网技术，依据血缘关系或亲祖关系把人联系起来，再按照辈份排序构成树的模型。 在树中的成员可以清楚的知道自己的家族起源、家族关系以及其他成员的基础信息，并且享有记录、分享等沟通娱乐服务。 作用和功效有几个： 追祖溯源 汇聚亲情 沟通分享 传承家族文化 家族树的树状特征和原理可以让树无限延伸和扩大，添加家庭成员，是目前用于家庭沟通比较好的网络工具之一。 你去自己亲自建立一颗家族树会更清楚！ 求一个带家族树的家族网源代码

我有一个，跟关系网差不多的源程序，不过跟软件一样的，你看看代码有用吗

家族(25)作用(4)