用二叉树实现家谱运算

栏目:资讯发布:2023-09-26浏览:2收藏

用二叉树实现家谱运算,第1张

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;

}

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

得姓始祖

孙书。春秋时,陈(为周武王灭商后所封的妫姓国)厉公的儿子叫陈完,在任陈 国大夫时同太子御寇很要好,御寇被杀后,他怕受株连而逃到齐国。到齐国后,陈完不愿再用 原来的国名为姓,就改成田姓(古时田和陈发音相同)。田完的四世孙田桓子无宇有二子,小儿子田书,字子占,在齐国为大夫,因为伐莒(周代诸侯国)有功,齐景公把他封在乐安(今山东省博兴县北),并赐他孙姓。孙书就成为孙姓始祖。

迁徙分布

唐高宗时期,固始人陈政、陈元光父子入闽开辟漳州时,河南的孙氏族人随同着到了那里安家落户。 唐僖宗时又有河南孙氏族人随同王潮、王审知入闽,定居福建。

据资料记载,有一支孙氏世居河南陈留。唐僖宗时,这支孙氏出任中书舍人、两浙节度使。他有个儿子名叫孙俐,文韬武略,很有才能。当时爆发了黄巢领导的农民起义,孙俐被朝廷选为佰将,带兵征战在闽、越、江右一带,立了军功,被封为东平侯,他和家人定居在了虔州虔化县(今天江西宁都)。他的后代又迁向了福建、广东。清康熙中,这一支孙氏族人迁至广东香山县翠亨村。后来出了伟大的革命先行者孙中山。

据史书记载,唐朝末年,孙氏族人从河南光州(今天河南潢川)迁入福建泉州。台湾的孙氏都是从福建泉州迁徙而来的。

孙氏在国内分布很广泛,海外不少国家也都有孙姓华人。

孙姓自商末周初立姓之后,一直活跃在河南和山东一带。春秋初,姬姓孙氏一直世袭卫国的上卿,权倾一国,孙姓在河南地区发展很快,到春秋末,孙氏在卫国失宠,北迁晋国。发源在山东的妫姓孙氏发展得蓬蓬勃勃,尤其在战国时期出了一位赫赫有名的军事家孙武,其子孙明因父功而封富春侯,封地在今浙江富阳,形成了孙氏的南方著名郡望吴郡。秦汉以后,妫姓孙氏成了全国孙姓的主力,由山东向四周拓展,西进山西太原,南达浙江南部,向西南达到湖北。三国时,孙坚父子在江南建立了吴国,孙氏的发展达到了顶峰。在魏晋南北朝时,北方、中原和江南的孙氏都得到了迅速发展,出现一批孙氏名家大族。到了唐宋时期,孙姓已遍布于大江南北、五湖四海。在宋朝形成的百家姓中,第一句就是赵钱孙李,可见孙姓的社会地位和影响。明末清初,孙姓也进入了台湾。 宋朝时期(公元960-1279年),孙姓大约有105余万人,约占全国人口的1.35,为宋朝第十一位大姓。孙 姓第一大省是安徽,约占全国孙姓总人口的11.8,占安徽总人口的2.8。在全国的分布主要集中于安徽、河南、山东、江苏,这四省孙姓大约占全国孙姓总人口的44;其次分布于江西、河北、四川、浙江、湖南、湖北,这六省的孙姓又集中了44。形成了长江以北孙姓为主力的布局,皖豫鲁苏,长江流域为两个集中分布的孙姓聚集区。

明朝时期(公元1368-1644年),孙姓大约有119万人,约占全国人口的1.28强,为明朝第十四大姓。宋、元、明近600年全国人口纯增长率是20,孙姓人口增长比全国人口的增长要低,近600年中孙姓人口纯增长率只有13,净增加了14万。在全国的分布主要集中于浙江(20.8)、山东(14.5)、江苏(13)、江西(11.9),这四省孙姓大约占孙姓总人口的60;其次分布于陕西(6.7)、河北(5.8)、安徽(5.6)、山西(5.6)、河南(5.1),这五省的孙姓又集中了29。浙江为孙姓第一大省,占浙江总人口的1.6。宋、元、明期间,孙姓的分布总格局变化较大,其人口主要向东南和东部地区迁移,而中原地区孙姓人口萎缩。全国重新形成了浙赣、鲁苏两大块孙姓人口聚集地区,孙姓聚集重心开始向东移动。

当代孙姓的人口已达1 848万,为全国第十二位大姓,大约占全国人口的1.54。从明朝至今600年 中孙 姓人口由119万激增到1 848万,增长了近16倍。明朝的平均人口接近9 300万,当代的人口按12亿计,人口 增长了13倍。孙姓人口的增加速度高,分布于安徽、黑龙江、河北、辽宁、江苏、吉林,这六省又集中了42。山东为当代孙姓第一大省,居住了孙姓总人口的16.9,占省总人口的3.3。占省人口比率最高的省份是黑龙江(3.5)和吉林(3.4)。以长江为分水岭,孙姓显示了北多南少的分布格局,形成了华东沿海省份连接东北三省的孙姓分布带。在最近的600年期间,孙姓人口流动的程度和方向与宋、元、明期间有了很大的区别,其特点是由东南部向华中、华北强劲地回迁,同时,出现了黄河下游的孙姓人群向东北地区的大量移民。

关于更多姓氏知识可以参考百姓通谱。国内最好家谱网站。(wwwjp5000com)

  以word 2007为例,方法如下:

  1、依次单击“插入”、插图框中的“SmartArt”,在出现的对话框中选择“层次结构”、在右边出现的“组织结构图”中选中竖排或横排的结构图例,双击出现的“文本”,填写家谱姓氏辈份等信息。

  2、家族人丁兴旺的可以在不同的辈份(行或列)添加多个文本,具体方法是点击想要添加位置附近文本框,在菜单栏中点击“添加形状”,在子菜单中选择在后、前、上、下添加即可。 

  3、页面布局可以设置为横板,纸张设置大些,因为家谱人员太多,一张A3横板往往都写不下。

家谱: 又称族谱、宗谱等。是一种以表谱形式,记载一个家族的世系繁衍及重要人物事迹的书。皇帝的家谱称玉牒,如新朝玉牒、皇宋玉牒。它以记载父系家族世系、人物为中心,由正史中的帝王本纪及王侯列传、年表等演变而来。

在这里通过手机家谱软件可以帮助您清晰的整理家族信息,追根溯源记录家族发展的故事,让家谱可以更好的传承一代又一代,小编在这里为大家整理了手机家谱制作方法,希望能更好的对家谱进行记录。

工具/原料

手机微信端家谱软件

方法/步骤

首先我们需要创建自己的家谱,找到自己的姓氏,根据姓氏创建

家谱创建成功后,可以通过管理家谱,完善家谱资料

添加家族成员资料。

在整理家族成员资料时,我们还可以邀请家族成员一起来完善资料

可以通过微信的分享功能将家谱传播出去,在家谱树中点击右下角分享再点击右上角…选择分享的渠道。可以分享到微信朋友圈、微信好友、QQ空间、QQ好友等不同渠道。分享出去后用户可以查看家谱信息、申请加入家谱、参与完善家谱信息、分享家谱、邀请家谱、查看电子家谱等。

注意:家谱可以设置不同权限,当设置非自由访问的时候,加入会员需要后台审核后才可以有权限查看访问。

在家谱完善过程中,或者完善后可以将某个成员信息点分派到对应的族人管理完善,这样新族人进入后直接有对应点的管理、编辑权限,不用后台审核方便快捷。点击某个分派的点,点击下面的邀请,点击右上角…,选择微信好友分享给他,用户进入家谱后既绑定对应成员点信息,可以对当前成员点进行编辑、添加、删除等操作。

电子家谱书

资料完善后,家谱资料将以电子电子书的形式展示出来,

在家谱树界面右下角点击电子书,确认信息正确后进入家谱电子书。通过手指左右滑动翻页查看,电子书也会自动翻页。

这样一本手机家谱就制作完成了。

用二叉树实现家谱运算

C++语言: 二叉树实现的简单家谱树/ File Name: BiTreecpp Author: Geng Lequn[glq2000@126com] ...
点击下载
热门文章
    确认删除?
    回到顶部