#include <iostream.h>
typedef struct BiTNode
{
char data;
int bit;
struct BiTNode *lchild,*rchild,*parent;
}BiTNode;
void InitBT(BiTNode *&t)//1、初始化,不带头结点
{
t=NULL;
}
/*void InitBT(BiTNode *t)//初始化,带头结点
{
t=new BiTNode;
t->lchild=t->rchild=t->parent=NULL;
}*/
int EmptyBT(BiTNode *t)//判断队空
{
if(t==0)
return 1;
else
return 0;
}
BiTNode *creatBT(BiTNode *t,int b)//2、创建二叉树
{
BiTNode *p;
char ch;
cin>>ch;
if(ch=='#')return 0;
else
{
p=new BiTNode;
p->data=ch;
p->parent=t;
p->bit=b;
t=p;
t->lchild=creatBT(t,0);
t->rchild=creatBT(t,1);
}
return t;
}
void preorder(BiTNode *t)//3、先序遍历
{
if(!EmptyBT(t))
{
cout<<t->data;
preorder(t->lchild);
preorder(t->rchild);
}
}
void inorder(BiTNode *t)//中序遍历
{
if(!EmptyBT(t))
{
inorder(t->lchild);
cout<<t->data;
inorder(t->rchild);
}
}
void postorder(BiTNode *t)//后序遍历
{
if(!EmptyBT(t))
{
postorder(t->lchild);
postorder(t->rchild);
cout<<t->data;
}
}
void coutBT(BiTNode *t,int &m,int &n,int &i)//4、计算二叉树中叶子结点、度为2的结点和度为1的结点的个数
{
if(!EmptyBT(t))
{
if((t->lchild==0) && (t->rchild==0))
m++;//叶子结点
else if((t->lchild!=0) && (t->rchild!=0))
i++;//度为2的结点
else
n++;//度为1的结点
coutBT(t->lchild,m,n,i);
coutBT(t->rchild,m,n,i);
}
}
void coutNode(BiTNode *t,int &k)//5、求二叉树中结点个数
{
if(!EmptyBT(t))
{
k++;
coutNode(t->lchild,k);
coutNode(t->rchild,k);
}
}
int BTdepth(BiTNode *t)//6、求二叉树的深度
{
int i,j;
if(EmptyBT(t))
return 0;
else
{
i=BTdepth(t->lchild);
j=BTdepth(t->rchild);
return (i>j?i:j)+1;
}
}
int Xdepth(BiTNode *t,char x)//7、查找x的层数
{
int num1,num2,n;
if(t==NULL)
return 0;
else{
if(t->data==x)
return 1;
num1=Xdepth(t->lchild,x);
num2=Xdepth(t->rchild,x);
n=num1+num2;
if(num1!=0||num2!=0)
n++;
return n;
}
}
static int flag;
void SearchChild(BiTNode *t,int k)//8、查找第k个结点的左右孩子
{
if(!EmptyBT(t))
{
if(k==0)
{
cout<<"位置不能为0!"<<endl;
return;
}
else
{
flag++;
if(flag==k)
{
if(t->lchild==0)
cout<<"无左孩子! ";
else
cout<<"左孩子为:"<<(t->lchild->data)<<" ";
if(t->rchild==0)
cout<<"无右孩子!"<<endl;
else
cout<<"右孩子为:"<<(t->rchild->data)<<endl;
}
else
{
SearchChild(t->lchild,k);
SearchChild(t->rchild,k);
}
}
}
}
int Xancestor(BiTNode *t,char x)//9、查找x结点祖先
{
int n,num1,num2;
if(t==NULL)
return 0;
else
{
if(t->data==x)
return 1;
num1=Xancestor(t->lchild,x);
num2=Xancestor(t->rchild,x);
n=num1+num2;
if(n!=0)
{
n++;
cout<<t->data<<" "<<endl;
}
}
}
void BTNodePath(BiTNode *t)//10、输出所有叶子结点路径
{
if(!EmptyBT(t))
{
if((t->lchild==0) && (t->rchild==0))
{
cout<<t->data<<"的路径为:";
for(BiTNode *p=t;p!=0;p=p->parent)
cout<<p->data;
cout<<endl;
}
else
{
BTNodePath(t->lchild);
BTNodePath(t->rchild);
}
}
}
void BTNodebit(BiTNode *t)//11、输出所有叶子结点编码
{
if(!EmptyBT(t))
{
if((t->lchild==0) && (t->rchild==0))
{
cout<<t->data<<"的编码为:";
for(BiTNode *p=t;p->parent!=0;p=p->parent)
cout<<p->bit;
cout<<endl;
}
else
{
BTNodebit(t->lchild);
BTNodebit(t->rchild);
}
}
}
void main()
{
BiTNode *t;
int m,n,i,d,q,k;
char x;
cout<<"1、初始化..."<<endl;
InitBT(t);
cout<<"2、创建二叉树..."<<endl;
t=creatBT(t,0);
cout<<"3.1、先序遍历..."<<endl;
preorder(t);
cout<<endl;
cout<<"3.2、中序遍历..."<<endl;
inorder(t);
cout<<endl;
cout<<"3.3、后序遍历..."<<endl;
postorder(t);
cout<<endl;
m=n=i=0;
cout<<"4、计算叶子结点,度为1的结点和度为2的结点的个数..."<<endl;
coutBT(t,m,n,i);
cout<<"叶子结点个数为:"<<m<<endl;
cout<<"度为1的结点个数为:"<<n<<endl;
cout<<"度为2的结点个数为:"<<i<<endl;
q=0;
cout<<"5、计算结点个数..."<<endl;
coutNode(t,q);
cout<<"结点个数为:"<<q<<endl;
d=0;
cout<<"6、计算深度..."<<endl;
d=BTdepth(t);
cout<<"深度为:"<<d<<endl;
cout<<"7、求x的层数..."<<endl;
cout<<"输入x:";
cin>>x;
if(Xdepth(t,x)==0)
cout<<"x不存在!"<<endl;
else
cout<<Xdepth(t,x)<<endl;
cout<<"8、输入要查找孩子的结点在先序遍历中的位置k(不等于0):";
cin>>k;
SearchChild(t,k);
if(k>flag)
cout<<"位置超出长度!"<<endl;
cout<<"9、查询结点的所有祖先,请输入结点x:";
cin>>x;
int num;
num=Xancestor(t,x);
if(num==0)
cout<<"结点不存在!"<<endl;
if(num==1)
cout<<"根结点无祖先!"<<endl;
cout<<"10、输出所有叶子结点路径(叶→根):"<<endl;
BTNodePath(t);
cout<<"11、输出所有叶子结点编码(叶→根):"<<endl;
BTNodebit(t);
}
温馨提示:答案为网友推荐,仅供参考