/*
* File Name: BiTree.cpp
* Author: Geng Lequn[glq2000@126.com]
* Thur July 1 2010
*Discription: 建立二叉家谱树,实现输入任意两个人的名字,查找得到其关系
*/
#include
#include
#include
#include
#include
#include
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."<
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<<"请按先序遍历的顺序根据提示输入家谱信息,不存在则输入\"#\""<
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
for(size_t b=0, e=str.find('-'); ; e=str.find('-', b))
{
if(e == string::npos)
{
v.push_back(str.substr(b));
break;
}
else
v.push_back(str.substr(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<
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<
{
if(name1=="#" && name2=="#") return;
p1 = NULL; p2 = NULL; //因为程序是循环执行的,需要将上次遗留的值清掉
findPersonFlag = 0;
FindPersonMiddleOrder(root, name1, p1);
findPersonFlag = 0;
FindPersonMiddleOrder(root, name2, p2);
if(!p1 || !p2) //若有一个为空或都为空,说明至少有一个人不在家谱中,故两人无亲缘关系
{
cout<
}
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<
cout<
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
for(int i=0; i
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<
goto Label;
}
}
/*
* function: 后序遍历销毁此二叉树,释放节点占用的内存空间
*/
void DestroyBiTreePostOrder(PNode pn)
{
if(!pn) return;
DestroyBiTreePostOrder(pn->l_child);
DestroyBiTreePostOrder(pn->r_brother);
delete pn;
}
