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中的完全二又树存放在一维数组bree中，将发现结点的编号正好与数组元素的下标对应。

岳飞后裔统一字谱：

自二十二世起用：

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

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

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

从二十五世起：

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

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

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

自十九世起：

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

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

自三十世起：

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

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

自二十三世起：

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

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

自二十七世起：

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

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

从十三世岳俊青起：

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

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

自十五世起：

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

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

从十八世起：

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

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

从二十一世起：

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

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

从二十二世开始：

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

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

从二十八世起：

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

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

从二十六世起：

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

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

自三十世起：

维武乃言，广济世传。

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

自二十二世始：

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

山东曲阜、泗水后裔

从二十六世始：

绪本西都衍, 东千顺大明

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

从七世起：

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

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

从三十一世起：

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

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

从二十七世始：

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

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

从十六世起：

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

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

从十九派开始：

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

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

从二十三世起：

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

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

从十世起：

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

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

从二十二世起：

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

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

从三十世起：

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

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

从二十三世始：

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

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

从二十五世起：

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

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

约从十七世起：

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

贵州绥阳岳氏

如国世正兴 明朝志大清

安邦元立德 美景万年春

洞庭贻谋远 江阳圣泽新

功勋昭宋殿 甘露兆天灵

河北滦县岳氏

庭余崇金成 春光绪祖先

富贵传文武 诗书纪世年

四川宜宾文兴县岳氏

可世再传后 仑钟朝上天

步登观奉启 承继向宏铮

安徽肥西县岳氏

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

河南桐柏县岳氏

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

山东威海雷系字谱

从33世开始

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

1、河北侯氏一支：天廷云久书

2、河北南宫：成赐云香庆瑞……

3、湖南湘潭衡州：太守裔建业盛冈林文武多俊杰历朝列晋绅忠恕泽洪广贻廉德懋光英华辉上国贤达显荣昌肇唐勋烈继绍宋典型彰培植锤名士修齐兆福祥

4、湖南岳阳：士业奇仁玉文华焕楚邦家声芳大振国泽庆平章克象昭民德承荣献俊良光先启佑永万代锡蕃昌

5、湖南张家界：宗德启万世

6、湖南会泽：开堂世明金

7、山东乐陵杨安镇：玉长殿德廷飞

8、山东菏泽：天朴文继广存凯  

扩展资料：

侯氏人口分布：

明朝时期，侯姓大约有26万余人，约占全国人口的028%，排在第七十七位。宋元明600年全国人口纯增长率是20%，侯姓人口增长为负值，净减少了8万。面对战乱和屠杀，受害群体首先应是主体在北方的人群，侯姓是北方地区姓氏，自然受到了惨重的损失。陕西为侯姓第一大省，约占侯姓总人口的176%。

在全国的分布主要集中于陕西、山西、浙江，这三省侯姓大约占侯姓总人口的44%，其次分布于山东、河南、甘肃、江苏、河北，这五省的侯姓又集中了33%。宋元明600余年，侯姓的分布总格局变化较大，其人口主要由北方向东南和西部迁移。全国重新形成了北部秦晋豫鲁、东南江浙两大块侯姓人口聚集地区。

-侯氏

盖闻根深者枝茂源远者流长凡子孙绳绳子孙千亿皆祖宗德泽所遗也故为子孙者宜立家谱树墓志以溯根源之所自吾祖自历下迁居年远而祖益蕃家谱墓志概未之修尝深憾焉幸哉弟豳等以护茔地十有馀亩倡率子侄协力耕种开其财源积蓄数载磨刻碑石尊祖敬宗於去岁十月间两茔均树墓志兼重修济南府老茔碑碣又共议於余曰墓志虽立而左昭右穆先人之名字俱未之载不如敬修家谱以广其传余想谱牒之重於天下尚矣以彰先人之德以笃宗族之谊以贻後嗣之谋若迟延不修阅世旣久坟墓虽存支派已迷至於羣然杂遝茫然其先人之名号者比比也余因是嘱侄尚义等於九支内详人之事迹序子弟之名次询其母族志其妻族尊卑长幼羣登於谱分支绘图瞭如指掌数年後子孙名字各续於后庶可以歴久远。

道光十七年岁次丙申夏月

六世孙秦世荣 敬撰

侄 秦岫 秦崶 谨志

孙 秦尚义 敬书 中华民国二十五年闰三月十四日重修

敬撰： 十世孙 秦大智

谨志： 十一世孙 秦玳声

敬书： 十二世孙 秦宝华

本家谱共分为四部分

1家族人物表部分有总谱系表；有秦良才、秦良玉、秦良弼三兄弟支系表；还有秦礼、秦浩等家族成员一览表。凡是已经去世的族人，用黑字，未去世的人用红字，为了便于现代人阅读，采用从左到右的横排版方式，对庶出的人用标出。对抱养的人用≠标出，为了保障秦氏族人的整体安全，为了保护秦氏族人的隐私，其公开的部分（电子版），将国字辈的秦氏族人的姓名去除，但保留空格位置，这样，秦氏族人仍可以查到家谱中的各类信息。而外人则不易获知。

2家族人物的生平和事迹因对前辈古人的事迹不了解，以民国以后的出生的人的生平和事迹为主，共列入 位，这些人物也包括秦氏族人中的女子。其中，在世的人只写生平，不入传记。

3秦氏家族人物的居住地和单位地址、办公电话号、手机号、邮箱号、QQ号等****，为保密和安全，在网上公开的电子版中将设置密码。

4秦氏家族人物的作品专集主要收录秦氏族人创作的短篇文章、字画、歌曲、照片、**、电视视频、艺术作品的影像资料等内容。