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;

}

家谱又称族谱、家乘、祖谱等。是一种以表谱形式，记载一个以血缘关系为主体的家族世系繁衍和重要人物事迹的特殊图书体裁。家谱是中国特有的文化遗产，在历史民族大融合中，各个民族中开始出现族谱。族谱也是中华民族的三大文献（国史，地志，族谱）之一。

追溯最早家谱的产生为口述家谱，资料显示：“瞽蒙主诵诗，并诵世系”之说，家谱最初的功能就是辨析亲疏，凝聚族群，优化生育，即所谓“亲亲以相及”。此后万变不离其“别”与“聚”这两个基本功能，但随时代推移，社会制度不同，其具体内涵和所起作用也不一样。它的发展也是根据历史朝代的政治体制来进行兴衰交替的演变。现在就跟着小编来了解一下家谱的起源吧。

家谱发展及其功能嬗变的脉络，大致可分为周代、两汉、魏晋南北朝、隋唐和五代以后几个阶段。

周代

周代的宗法分封制度，经过春秋战国战火的局面影响，特别是秦王扫除六合后，宗族组织由兴到衰，由破坏到重建，到东汉时已由世族和宗族代替。

周代行的是宗法封建制度。“族”本来只是 有血缘关系的群体，并无尊卑主从之别，但进入阶级社会，便有了“宗”，也就是在亲族之中奉一人以为主，主者为尊并享有特权，其死后则由宗子继承。这样，家谱“ 别亲疏、明统系”的功能便渗进了主从尊卑的阶级斗争里，其功能也是宗法封建政治服务的内容。

“辨昭穆者，帝系《世本》之中，皆自有昭穆亲疏，故须辨之云”。由此可见：周代的家谱《世本》之类，是属于以周 天子为首的周室宗族的，它所明的统系，是周宗室的帝王统系；所辨的亲疏，是尊卑贵贱的亲疏。所以，周代的家谱完全是为推行宗法分封，巩固周王朝统治服务的。

两汉时期

两汉时期基本是世族地主占统治地位，“命官以贤，诏爵以功”，君统与宗统开始分离。所以，两汉的家谱功能是为恢复、复建宗族和形成、巩固世族的统治服务。

魏晋南北朝、隋唐时期

魏晋南北朝时期实行的是士族政治、魏立九品中正制，“上品无寒门，下品无势族”，选官品人，婚姻嫁媾，士庶分明，尊卑严格，“官之选举，必由簿状；家之婚 姻，必由谱系”，因而维系门阀制度的家谱特别兴盛。

此时的家谱成了政府选举、士族出仕、门第婚姻的根据，同时也成为士族政治服务的工具。正因为家谱对于人 们的社会地位、发展前途、社交层次有如此重大的作用，造假的现象也泛滥起来，这也是利益驱动所致。

五代以后

由于北方战乱频繁，大量中原人口南迁，经济中心南移，特别是宋明清商品货币经济的发展，城镇商业繁荣和商帮的出现，推动着社会权力的进一步下放，士族宗族也向平民宗族发展。五代以后家谱由于失去了以前的政治功能，也由官修变为私修，内容也就更加广泛丰富起来，它的功能也由政治功能向社会功能的方向发展。

具体地说，私修家谱通过姓氏原始、迁徙本末、世系渊源的展现，起着追踪溯源、联宗收族，维系和强化宗族的作用。尤其到了明清时期，家谱的作用已经上升到规范族人行为准则的一种约束力，其姓氏文化也得到大力的发展，为现在历史学家研究历史提供了大量的民间史料。

总之，家谱在我国源远流长，在历史的长河中，已经形成有独特内涵、浸润着民族情愫的谱牒文化，它已经成为历史学家探究真实历史的考证资料，它的文化价值是毋庸置疑的。它的产生与发展，同社会群体氏族、家族、家庭相联系，它的功能是随社会结构、社会制度的变化而改变，从社会功能至政治功能再回归到社会功能，自有文字家谱以来，总的发展趋势是由贵族到士族再到平民，维系和凝聚的人群也越来越广。它从家族史的角度来阐释、反映、印证中华民族的历史进程，对我们今天弘扬民族文化，热爱祖国，增强民族凝聚力，以及研究社会学、人口学、民族学、历史学等学科，都起了很大的作用。

　 家谱 是一个家族的发展史。一个家族要发展壮大，除需要雄厚的物质条件外，还需要足以“强宗固族”的精神条件，而良好的家风的形成，正是这种精神条件的基础和内容之一。”良好的家风是家族文化的最重要内容，但是，现今社会上已经不是以前的纯封建大家庭，一个大家庭实际上是老辈家庭与小辈家庭的组合，都有相对独立性。尤其是社会风气变了，以前是“嫁鸡随鸡嫁狗随狗”，现今是“女方提出：‘要结婚，必须在婚房产证上写我的名字。’”而且，女婿是岳家的义务劳力。社会阴盛阳衰，必然造成岳家文化对家族文化的极大影响。

　 一、现今社会中，岳家无子或者独生女儿的情况很多。 社会上女人有一种普遍的错误观念：“我与父母有血缘关系，与公婆无血缘关系，当然对娘家亲。”中国古代，为了女儿出嫁后不受气，就在嫁妆上加码（当然，娘家的社会地位也是重要筹码）。现今社会，娘家的女儿“出嫁前教育”大多是“如何保护自己？如何对付婆家？”家庭关系中，历来最微妙、最难处的是婆媳关系，但婆媳关系融洽与否又直接影响整个家庭中其他人际关系，如：夫妻关系、亲子关系、兄弟姐妹关系及祖孙关系等。

　家庭基本关系有两种：夫妻关系与亲子关系，两者构成家庭结构的基础。其它关系，如：兄弟姐妹关系、姑嫂关系、婆媳关系、祖孙关系等都在此基础上派生出来。婆媳关系既不是婚姻关系，也无血缘联系，是由亲子关系和夫妻关系的延伸而形成的特殊关系。因此，这种人际关系一无亲子关系的稳定性，二无婚姻关系的密切性。自古以来，婆媳关系就极复杂。封建社会中，婆媳关系不平等，媳妇必须俯首听命于婆母，没有独立、平等的人格尊严。“洞房昨夜停红烛，待晓堂前拜舅姑”是旧社会做媳妇艰难的生动写照。同时，“多年媳妇熬成婆”形成一种妇女压迫妇女的恶性循环。改革开放以来，女人地位不断升高，婆媳矛盾也随之升级。据有关方面调查，现今多数家庭是媳妇“执政”，因而在解决婆媳矛盾中，媳妇负有首要责任，尤其是婆媳共同生活的家庭。

　中国传统文化中，男女“授受不亲”，公公和媳妇大多因避嫌而相安无事。但婆媳都是女人，一个是儿子的老妈，一个是儿子的老婆，一旦因生活琐事发生矛盾，婆婆认为儿子“娶了媳妇忘了娘”，而媳妇心想“到底不是婆婆亲生，婆婆不会把自己当亲人”。于是，儿子受夹板气，偏向老娘就会受老婆的“冷暴力”，偏向老婆就背上“不孝”罪名。

　对于从旧社会过来的婆婆，思想上、生活上、习惯上难免带有旧痕迹。媳妇思想较新，常不易理解婆婆的习惯 ，故一些举动会引起婆婆反感，从而引起婆媳不合。即使是红旗下成长的婆婆，与媳妇仍然有代沟。在婆媳共同生活的家庭中，还有一个经济利益的分歧：我国家庭有“男治外、女治内”的传统，婆婆做了几十年的内当家，现在把权力交给媳妇，婆婆往往不易适应。有的婆婆虽已年过花甲，却仍希望继续保持家庭中的经济支配权，难以接受由媳妇掌握家庭经济大权的事实；而做媳妇的往往不甘让步，这就难免发生矛盾。另外，婆媳原来生活在不同家庭中，家族文化不同，难免不相适应。

　 二、婆媳相处本是一家人，就怕你认为对方是外人甚至是冤家、仇人。 现今社会的家庭中，婆家与娘家不能一碗水端平（利益分歧）是夫妻争吵的重要原因，其责任方一般是媳妇的“不是婆婆亲生”的理念。有的媳妇成为娘家利益的代理人，“娘家驻婆家的全权大使”。这样的家庭怎么会有太平？当然也有的婆婆认为“媳妇不是亲生”而不信任。婆媳都刁蛮的婆媳关系往往不可救药。

　所以，岳家文化对家族文化的影响主要是通过媳妇。

　 三、岳家文化对外孙的影响也不可忽视，尤其是子女由岳家带领的家庭。 所以，为了子代的健康成长，必须注意生活在什么家族文化的环境中。因为孩子还没有成熟的`判断力，“近朱者赤近墨者黑”，这种文化影响会作用孩子的一辈子。

　 四、在兄弟姐妹多的大家庭中，妯娌关系比姑嫂关系、嫂叔关系更加重要。 姑嫂关系、嫂叔关系之间只有一个中介；而妯娌关系之间有两个中介。例如：兄弟姐妹为房子发生矛盾，如果是姑嫂关系、嫂叔关系，夹在中间涉及利益的是兄妹、兄弟，背后只有一个岳家（嫂子的娘家）。而妯娌关系涉及利益的虽然也是兄妹，背后则有两个岳家（妯、娌的娘家）。所以，在处理这类矛盾时，不能不考虑背后的岳家。这里不是简单的是非问题。

　如果家族文化有兄弟和睦、相互谦让、互相帮助的风气，势必涉及谦让方夫妻的关系，因为利益关系，势必要谦让方夫对妻做思想工作。而更多的情况是谦让方夫本人内心并不愿意，于是就借妻或岳家不愿意为由，拒绝谦让。要求对方谦让的夫妻，因为利益一致，态度一致。对方不肯谦让，矛盾就会激化。

　 五、在重婚、二奶、小三等的情况下，夹在中间涉及利益的是不仅是正房与二奶、小三等的关系，还有背后的“岳家”利益。 这里也不是简单的是非问题。

　问题是：“岳家”文化有极大的差异，谁也无法改造“岳家”文化。因此，找老婆其实就是找岳母。你无法抵制不良的“岳家”文化。