树的孩子兄弟表示法.docx
《树的孩子兄弟表示法.docx》由会员分享，可在线阅读，更多相关《树的孩子兄弟表示法.docx（8页珍藏版）》请在冰点文库上搜索。
树的孩子兄弟表示法
树的孩子兄弟表示法
#include
#defineMAX30//树节点的最大数
usingnamespacestd;
template
classnode
{
public:
node（）
{
child=nextsibling=NULL;
}
Tele;//节点值
node*child,*nextsibling;//左儿子右兄弟
};
template
classMytree
{
public:
Mytree（）
{
tree=NULL;
}
~Mytree（）
{
deletetree;
}
voidCreatTree（node**）;//构造孩子兄弟表示法的树
TGetParent（node*,Tt）;//返回树的父亲节点
TGetLeftChild（node*,T）;//返回树的最左儿子
TGetRightsibling（node*,T）;//返回树的最右兄弟
TGetRoot（node*）;//返回树的根节点
node*RetPoint（T,node*）;//返回值为t的节点的指针
node*RetParentPoint（T,node*）;//返回值为t的节点父亲指针
voidDisplay（node*）;//树的左儿子右兄弟表示法的前序、中序、后序遍历
private:
voidpreTraverseTree（node*）;//递归先序遍历
voidInTraverseTree（node*）;//递归中序遍历
voidPostTraverseTree（node*）;//递归后序遍历
node*tree;
};
template
voidMytree:
:
CreatTree（node**tree）//构造左儿子右兄弟表示的树
{
//以tree为根节点构建
if（（*tree）!
=NULL）
{
cout<<"输入节点"<<（*tree）->ele<<"的左儿子右兄弟（没有的话输入#）：
";
node*a=newnode;
node*b=newnode;
cin>>a->ele>>b->ele;
if（a->ele!
='#'）（*tree）->child=a;//有左儿子
else（*tree）->child=NULL;
if（b->ele!
='#'）（*tree）->nextsibling=b;//有有兄弟
else（*tree）->nextsibling=NULL;
CreatTree（&（*tree）->child）;//递归构造树
CreatTree（&（*tree）->nextsibling）;
}
}
template
TMytree:
:
GetParent（node*tree,Tt）//返回节点值为t的父亲
{
node*p=RetParentPoint（t,tree）;
if（p）returnp->ele;
elsereturnNULL;
}
template
TMytree:
:
GetRoot（node*tree）//返回树的根节点值
{
returntree->ele;
}
template
TMytree:
:
GetLeftChild（node*tree,Tt）//返回树的左儿子
{
node*p=RetPoint（t,tree）;
if（p&&p->child）returnp->child->ele;
elsereturnNULL;
}
template
TMytree:
:
GetRightsibling（node*tree,Tt）//得到树tree的右兄弟
{
node*p=RetPoint（t,tree）;
if（p&&p->nextsibling）returnp->nextsibling->ele;
elsereturnNULL;
}
template
voidMytree:
:
Display（node*tree）//三种递归遍历
{
cout<<"先序递归遍历：
";
preTraverseTree（tree）;
cout<cout<<"中序递归遍历：
";
InTraverseTree（tree）;
cout<cout<<"后序递归遍历：
";
PostTraverseTree（tree）;
cout<}
template
voidMytree:
:
preTraverseTree（node*tree）//先序递归遍历
{
if（tree）
{
cout<ele<<"";
preTraverseTree（tree->child）;
preTraverseTree（tree->nextsibling）;
}
}
template
voidMytree:
:
InTraverseTree（node*tree）//中序递归遍历
{
if（tree）
{
InTraverseTree（tree->child）;
cout<ele<<" ";
InTraverseTree（tree->nextsibling）;
}
}
template
voidMytree:
:
PostTraverseTree（node*tree）//后序递归遍历
{
if（tree）
{
PostTraverseTree（tree->nextsibling）;
PostTraverseTree（tree->child）;
cout<ele<<"";
}
}
template
node*Mytree:
:
RetPoint（Tt,node*tree）//返回树节点值为t的指针
{
if（tree）
{
if（tree->ele==t）returntree;
elseif（RetPoint（t,tree->child）!
=NULL）
{
returnRetPoint（t,tree->child）;
}
elseif（RetPoint（t,tree->nextsibling）!
=NULL）
{
returnRetPoint（t,tree->nextsibling）;
}
elsereturnNULL;
}
elsereturnNULL;
}
template
node*Mytree:
:
RetParentPoint（Tt,node*tree）
{
if（tree&&tree->child）
{
if（tree->ele==t）returntree;
elseif（RetParentPoint（t,tree->child））
returnRetParentPoint（t,tree->child）;
elseif（RetParentPoint（t,tree->nextsibling））
returnRetParentPoint（t,tree->nextsibling）;
elsereturnNULL;
}
}
intmain（）
{
Mytreemytree;
node*root=newnode;
cout<<"输入根节点：
";
cin>>root->ele;
mytree.CreatTree（&root）;
cout<<"树的根：
"<cout<<"输入t：
";
chart;
cin>>t;
cout<<"t的左儿子"<cout<<"t的右兄弟"<cout<<"t的父节点：
"<cout<<"树的左儿子右兄弟表示法的三种遍历：
"<mytree.Display（root）;
return0;
}
/*
输入根节点：
a
输入节点a的左儿子右兄弟（没有的话输入#）：
bc
输入节点b的左儿子右兄弟（没有的话输入#）：
de
输入节点d的左儿子右兄弟（没有的话输入#）：
##
输入节点e的左儿子右兄弟（没有的话输入#）：
fg
输入节点f的左儿子右兄弟（没有的话输入#）：
##
输入节点g的左儿子右兄弟（没有的话输入#）：
##
输入节点c的左儿子右兄弟（没有的话输入#）：
h#
输入节点h的左儿子右兄弟（没有的话输入#）：
##
树的根：
a
输入t：
c
t的左儿子h
t的右兄弟
*/
升级会员 