用二叉树实现家谱运算
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世开始
恭俭传世,仁孝泽长,建华景俊,文惠宪章;天开鸿运,继寿永昌,尽忠报国,万代安康。
杨姓谱牒修撰的历史相当悠久。汉代刘歆在《七略》中提到与他同时的杨雄有《家牒》,而一些古代地方志中摘引的《家牒》片断涉及杨雄身后世。《世说新语》刘孝标注提到数十种南朝士族家谱,其中有《杨氏谱》。《隋书经籍志·谱系类》录有:《杨氏血脉谱》2卷,《杨氏家谱状并墓记》1卷,《杨氏支分谱》1卷,《杨氏谱》1卷。此外,古籍中还提到北齐有佚名的《杨愔家传》。以杨姓和王姓等为多,南北朝时的杨姓大族,已有编撰家谱之风。
民国十二年(1923年)杨姓重新立宗续谱字辈:登、成、永、宏、福、生、考、义、和、平十字排辈为序。 近代杨贵德等在桐梓县娄山关镇虎峰山杨价崇德庙开会讨论百字谱: 弘农俊杰英、荣华泽祥祯、文武科举锦、福禄宁康兴、太师忠书令、唐宋才嘉兵、汉隋相尉权、崇德怀仁君、兰桂照辉映、侯州尽雄伟、盛海波涛涌、觉理冲凌云、启后继乾坤、慎思贵富民、树以成良言、勋著永绵传、严洁孝顺模、喜庆辅龙腾、昌发山西籍、源远承家业。 后修改为:三知承俊杰、荣华泽祥祯、汉隋相尉才、盛德怀仁君、文武科举锦、唐宋建奇勋、太师奉旨令、侯州忆雄英、沧海波涛涌、虎跃起龙腾、满门忠烈鼎、丰功壮凌云、慎思传清白、后裔靖康宁、兰桂照辉映、福禄显家声、昭著千秋范、源远伟业兴、廉洁行孝顺、继发晋乾坤。
用二叉树实现家谱运算
本文2023-09-30 20:31:12发表“资讯”栏目。
本文链接:https://www.lezaizhuan.com/article/144796.html