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;

}

那什么是家谱，族谱？怎么制作？

谱，又称家乘、宗谱、公谱、祖谱、谱书、家牒、族牒。它是记录家族组织活动的档案材料。福建的族谱兴于宋代，盛于明清之后。修谱的动机是“溯渊源，分疏戚，序尊卑。”（安溪《谢氏总谱》卷首《联谱序》）族谱的形式有装订成册的（古为线装，今与一般印刷物相同），也有图表式的。许多家族把编纂族谱作为后代子孙的一项义务写进族规，重修族谱年限不等。闽北浦城的季氏和李氏家族，均规定族谱30年一修。房氏则规定“宗谱有贤子孙或十年、三十年一修，则存没葬地，时日不爽。先儒云，一世不修谱为不孝，宜知之。”（清·光绪《闽浦房氏族谱》）类似的族规，使修谱用家族法的形式永久化了。

族谱所载内容详略不一，通常除记载全族的户口、婚配和血缘关系外，还有全族的坟墓、族田族产、祠庙等的方位、数量及管理使用办法、家族的规约训诫、修谱凡例义则、各类合同契约文书等。一些较详的族谱，还记载有家族历代的重大事件、与外界的纠纷、可嘉奖的人物传记、科举出仕、名人传记以及义行节烈等。 族谱的核心内容是记载家族的世系源流、血缘系统。以防血缘关系紊乱而导致家族瓦解。连城《新泉张氏族谱》卷首说得明白：“亲疏派别得谱则溯其源，上下分支得谱则穷其本，即荡析代变，而皆有所考焉。”为达到显示血统的目的，各地族谱均有认中国先朝名人为远祖的习俗，这种附会的谱风，虽能使其家系倍增光彩，但往往导致家史失真和对后代误导。安溪湖头的李氏宗谱，认先祖为道教创始人李耳，直系则“出陇西，为唐高祖李渊公之苗裔。”南靖庙兜郭姓，认始祖为周文王之弟“虢叔”（“虢”与“郭”音近），并由虢叔是黄帝的二十七世裔孙，郭子仪是虢叔的第六十世孙、黄帝的八十七世裔孙，而推论自己的宗族嫡出于中唐名将郭子仪。（《南靖文史资料》第二期89页《庙兜郭姓的历史渊源》何柳枝）这些记载，易使族人深信不疑。其他的如刘姓必溯祖为刘邦，肖姓多探源为萧何，都是这种攀强名流、附会望族的修谱心态之反映。 族谱中，家族迁居（开基）始祖之下的代系排列严格分明，不容混淆。这往往是族谱中最具史实价值的部分。福建的许多家族，都实行名字排行制（古称“昭穆”），俗称“排辈份”。即在同一辈份的族人中名或字须用某个统一规定的单字起头，再与其他单字结合成名或字，以示区别。如某一父辈生三子，儿辈名按“永”字排列，分别称“永志”、“永仁”、“永贵”。如此，在族谱中一看“永”字排行便可知其为兄弟或堂兄弟辈份。已去世者，则在其名上写上谥称并加上“公”字，以示区别，沙县一带习俗，收养子若无族长和六亲认可，不可上谱排字辈，否则会被骂为“出透的人”而遭岐视。排辈份除少数由祖、父辈临时决定外，大多是按先祖早已选定的排行用字。南靖县双峰村《丘氏族谱》载：从其二十一世始，标定的昭穆用字是：“文章 ，诗礼传家。创垂显奕，继述藏嘉。光前荣耀，世德作裘。仁亲义祖，燕翼贻谋。桂芳兰茂，日新月盛。思皇多佑，福禄来成。庆余善积，谱泽绵延。宗风丕振，亿万斯年。”（《南靖文史资料》第二期86页《双峰丘氏的历史渊源》林明波）目前已传至“垂”、“显”字辈，即第三十至三十一世。这种按族谱排辈份的方法，使农村常可见到这样的俗象，由于世系分支发展速度不一，一些年届七旬的老翁，要向三岁稚童称“叔”或“伯”。永定俗谓：“白头哥，坐地叔”（即对平辈的白头老翁仅呼“哥”，而尚在襁褓中的叔辈，即使上年纪老者也要唤其为叔）。为了区别同辈中的年龄次序，“排辈份”之外还要“排号”。永泰县同安乡张氏族谱规定，族人添丁按先后次序排号，日常称呼常舍其名而直呼其号，如同辈中是第20个出生的，就直呼“二十”以代名字。这一习俗在当地一些年高者中至今仍颇为流行。 同一姓氏的不同分支家族，还经常利用族谱中的血缘世系排行记载，进行“联谱”活动。安溪谢氏家族，曾于民国年间合数十宗支进行大联谱。辈份分明后，各宗支子孙公议决定排行班次悉归画一，修纂总谱，旨在扩大家族势力。谢氏家族裔孙谢维峻在《联谱序》中称：“联之以谱，化弱小为强大，转柔软为坚刚，众志成城。”此外还有，当族谱分支过多时另分几个房派修谱（房谱和族谱通称家谱）。如一房人外迁，其房谱分出后就成为新的族谱。 由于族谱为同一姓氏家族承继的依据，故一般只记男丁。少数族谱也将族中所谓“贞妇烈女”记载入乘。族谱有的依不同对象规定用笔着色的。据《岛居三录》载：“泉郡向修族谱，世系图所牵连之线，有红有黑，体例甚严。红线者，一本至亲，虽远房承宗亦然；黑线者，乞养异姓，即显宦不能免，此亦春秋诛心之法也。”有功名成就或能光宗耀祖之人，族谱中用红笔记入以示表彰，过去秀才或秀才以上的读书人也用朱笔入谱。现在一些新修族谱仍沿此习。寿宁《刘氏总谱》中，凡上大学的族人，名下都划上红线，所书的姓名用谱名（即按族谱排行而起的名字），抱养子用黑线注明（连城一带是用蓝线）。修谱和查阅族谱也很有讲究。旧时对祖谱保管十分重视，须慎重保存，定期曝晒，认真缮修。霞浦一带，谱系分正谱、副谱（草谱）。副谱可以查阅，而正谱修好后，要入箱上锁，将开锁的钥匙丢入祖祠神龛，以示此谱交祖先收存，以后禁开锁。若遇副谱丢失，有事要查谱时，要先做“牲福”，祭请祖先同意，方可开锁。 旧时一些宗族修谱，每逢初一、十五日要祭祀祖宗。族谱告成后，还要造灵厝、做功德，请和尚法师观灯；观灯时造3座大灵厝（纸糊房子），供已超度的神魂居住，另设一些黑龛，供无子孙后代及未超度的神魂居住。福建省连城一带宗族，每年正月要拜“代图”（即写在布上的族谱）。行仪时，本族男丁都要到场，先是“新丁上图”（即新添男丁的名字入谱），上图之家要给执笔者一个红包，并烧香燃炮，用三牲祭祖。若逢大祭，要用整头猪羊置于下厅的支架上；继而是鸣锣击鼓放鞭炮；最后会餐，座位严格按辈份排列。族人围坐喝酒谈心，气氛很好。连城人把正月“拜代图”的宗族聚会称为“闹花灯”。 用Excel如何制作家谱

建议以Word编辑，用插入“组织结构图”编写家谱。

当然，你也可以下载专门的家谱软件，如《族谱家谱制作编辑软件》或《族脉家谱》编写。 族谱家谱制作的9大步骤

一、拟定修家谱计划

1、版本：精装、平装、光碟、网络。 2、时间：完成期限、工作时程。 3、预算：经费、人员。 4、范围：同宗、合族、家族。 5、工具：图表、问卷、电脑。 二、组织章程 组织委员、修谱大纲、责任分配、发凡起例。 三、筹集基金 一人负担、众人分摊、家族劝募、早请补助、公开销售组织内容大纲，制作世系图表、填写行实履历、撰写名人家传、考订姓氏渊源、记录迁徙过程、著录文艺著作、附录照片图版、其它次要内容。 四、资料分析 前修旧谱、相说族谱、族谱研究资料、研究与过滤资料、请教族谱专家。 五、寻找史料 家谱文献、世系资料、出生、过世登记证、户籍、除户登记资料、神龛祖先牌位、家庙晋主名册、祭祀公业章程、名册，墓碑文字、坟葬座落方位，讣文、疏文、功德薄，长辈口述记录，家传、年谱、纪念集，老照片、录音、录影资料，古文书、契约、证书，正史、方志，人名录、同学录，旧报纸、电话薄。 六、编辑内容 组织内容大纲、制作世图表、填写行实履历、撰写名人家传、考订姓氏渊源、记录迁徙过程、著录文艺 著作、附录照片图版、其它次要内容。 七、审定内容 专家审稿、多次校稿、最后完稿。 说明：最好有学者专家参与审订，审稿时一定要仔细，可以慢一些但要保持精准。 八、印刷出版 黑白或彩色、纸本或光碟、选定印刷厂、印制若干份、设家族网站。 九、领谱典藏 办祭谱活动，族人领族谱，寄存图书馆。 如何把纸质家谱族谱做成电子版？

把纸质家谱做成电子版，就得找这样的软件。或找会做网站的专业人员帮你做。非专业人士在没有软件的情况下应该是做不成的。

如何制作家谱图表

家谱，又称族谱、家乘、祖谱、宗谱等。一种以表谱形式，记载一个以血缘关系为主体的家族世系繁衍和重要人物事迹的特殊图书体裁。

用PS图像处理软件制作家谱图表步骤/方法：　1、首先打开PS软件，然后选择菜单栏上的文件选项，选择下拉列表的新建文件。　2、弹出新建对话框，给新建的文档设置一个宽度和高度　3、设置好宽度和高度之后单击确定按钮，新建一个新的文档。　4、选择工具栏上的矩形选框工具，也可以选择椭圆工具，根据自己喜欢的形状来选择，这里我选择矩形选框工具。　5、然后在文档上拖动鼠标，拉进一个长方形的选区。　6、然后新建一个新的图层，选择软件右下角的新建小图标，新建一个新的图层　7、新建完图层之后为图层填充颜色，填充你自己喜欢的颜色，选择软件左侧的工具栏，单击颜色按钮，弹出的窗口选择你喜欢的颜色。　8、选择好颜色之后单击确定按钮即可，然后按下键盘上的ALT+Backspace退格键为刚才新建的图层填充颜色。　9、按键盘上的CTRL+D键，取消选择选区。　10、然后选择工具栏上的文字工具，选择直排文字工具，为刚填充颜色图案上面填写上名字。　11、选择完之后我们选择颜色图标，把颜色更换为白色，然后在文档上面输入文字。　12、如果觉得文字太小的话，可以在菜单栏顶部设置文字的大小，接下来就是要现点竖线，选择左侧工具栏上的自定义形状工具里面的直线工具。　13、然后在文档拉动，由于刚更换颜色为白色，现在将颜色更换为红色，拉动之后按键盘上的CTRL+CENTER然后再按CTRL+D取消选择。　14、“爷爷”已经制作好了，接下来制作“爸爸”，依次这样制作下来，大家发挥自己的想象力，颜色之类都可以更改，包抱直线等。再请参考： 怎样制作家谱图表_家谱吧_百度贴吧 ://tiebabaidu/p/3634444285 有谁知道用“WORD”制作传统式家谱（族谱）？

用文本框（双击文本框，设置文本框颜色为无线条色）就可以制作了。中间的连接线用自选图形里面的 连接符。

先画出来一个文本框，然后双击设置好格式（双击 文本框－－颜色与线条，改成无线条色，然后 点文本框（顶部 倒数第2组），设置4个边距均为0）。然后第一个框框就弄好了。 选中这个文本框，ctrl ＋鼠标左键，拖拽到适当的位置（比如最上面是 家族的族长，下面的第二层，是第二辈分的人，按要求摆放位置即可。这样所有的文本框均是同样的尺寸，同样的格式。 弄好了之后 ，再添加连接线。 每一页都是这样的编辑方式。可以根据大概情况，提前 弄出多页面来。 制作家谱用什么软件好

传承家谱程序是专门做树形家谱的程序，而且输出为WORD文档，也可以图形输出。 输出树形谱系为TXT文件，可以输出任意大小的树形谱系，避免了版面上的限制。 可以在百度搜索，最新版本为520

如何制作家谱？

可以考虑用Microsoft Office Visio进行绘制。使用方法和word类似

在word中可以考虑采用“组织机构图”的绘制方法 家谱(23)族谱(13)

一般家谱的主要内容有：

1、谱序。稍具规模的家谱，卷首一定会有一篇至几十篇不等的序文，它是每部家谱不可缺少的内容之一。谱序包括新序、旧序、族外人的客序、跋语、目录和刻印人名以及其它关于本族的记述。

2、凡例。主要是阐述家谱的纂修原则和体例。一般而言，一些家谱在每一次续修时都会订出若干条适合社会潮流与需要的规则，以作为修谱时所要遵循的原则。

3、姓氏源流。意思就是同一族姓的来源、迁移等。中国上下五千年，渊源古老，如果没有家谱，后人就很难搞清楚。每套《家谱》都认清自己姓氏源流，这样才能世世代代承继，也能将族系根缘流传千百年。

中国家谱素来有＂叙本系，述始封＂的传统，明清以来各家谱也大多有记姓氏源流的一章，或称姓氏源流，或称宗族源流。它主要是用来记述本姓来源、本族的历史渊源、始祖、世派、迁徙、各支派间关系甚至改姓的原委等。

4、写清堂号。堂号名称一般取自于郡号名，或者是史祖自创。一般来说，堂号多取自于郡号名，郡是秦、汉时期对行政区域的建置，郡号名又取自于郡名，或诸侯国名，地方府、州、县名。如任氏的“五知堂”（知恩、知道、知命、知足、知幸）。

5、家训、族规。很多家谱中，都记录了许多治家教子的名言警句，流传到后世了，比如我们熟悉的颜氏家训、朱子治家格言等。家规是宗族家族成员共同制定的、用以约束和教化族人的宗族法规，是家谱中的重要组成部分。其名称各异，种类很多，诸如家规、家戒、家法、家礼、族规、族约、祠规、戒谕等。

扩展资料

不用横竖线连接世代人名间的关系，而是纯用文字来表述这种关系，形式固定，次序分明，比较简约。每一种世系图表形式都各有特色，侧重不同。其中宝塔式随着流传发展，衍生出了多种形式，以树形图谱和线形图谱最为常见。

树形图谱很象是一张组织结构图，看起来清晰美观，使用更普遍一些。编修家族世系图要做到易看易懂、世序分明、内容真实、语言简练。

随着时代发展，现在很多家族在修撰家谱时，开始运用一些好的计算机软件来方便快捷地绘制编辑图谱，还可以融入一些现代审美的样式。