赞
踩
#include <iostream.h>
#define MAXSIZE 100
typedef char ElemType;
typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
void CreateBiTree1(BiTree &T)
{
//先序建立
char ch;
cin>>ch;
if(ch=='#')
T=NULL;
else {
T=new BiTNode;
T->data=ch;
CreateBiTree1(T->lchild);
CreateBiTree1(T->rchild);
}
}
void CreateBiTree2(BiTree &T)
{
//层序建立
if(T==NULL)cout<<"这里存在一个空结点\n";
BiTree a,b;
char c,h;
cout<<"请输入此时的根结点其对应两个孩子的元素值:\n";
cin>>c>>h;
a=T->lchild;
b=T->rchild;
if(c=='#')
a=NULL;
else { a=new BiTNode; a->data=c;}
if(h=='#')
b=NULL;
else { b=new BiTNode; b->data=h;}
CreateBiTree2(T=a);
CreateBiTree2(T=b);
}
void InOrderTraverse1(BiTree T)
{
//先序遍历
if(T)
{
cout<<T->data;
InOrderTraverse1(T->lchild);
InOrderTraverse1(T->rchild);
}
}
void InOrderTraverse2(BiTree T)
{
//中序遍历
if(T) {
InOrderTraverse2(T->lchild);
cout<<T->data;
InOrderTraverse2(T->rchild);
}
}
void InOrderTraverse3(BiTree T)
{
//后序遍历
if(T) {
InOrderTraverse3(T->lchild);
InOrderTraverse3(T->rchild);
cout<<T->data;
}
}
int Depth(BiTree T)
{ //深度
int n,m;
if(T==NULL)
return 0;
else {
m=Depth(T->lchild);
n=Depth(T->rchild);
if(m>n)
return(m+1);
else
return(n+1);
}
}
int NodeCount(BiTree T)
{ //叶子结点的个数
if(T==NULL)
return 0;
else
return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
int main()
{ int i,k,l;
BiTree a;
int height,num;
cout<<"请输入你要进行的操作:1.先序建立2.层序建立\n";
cin>>k;
switch(k)
{
case 1:cout<<"请输入二叉树的元素!\n"; CreateBiTree1(a); break;
case 2:cout<<"请输入二叉树的头结点元素!\n"; char ch; cin>>ch; a=new BiTNode; a->data=ch; CreateBiTree2(a); break;
default: cout<<"错误重输!"; break;
}
for(i=0;i<3;i++)
{cout<<"请输入你要进行的操作:1.先序输出2.中序输出3.后序输出\n";
cin>>l;
switch(l)
{
case 1: cout<<"按先序遍历法输出该二叉树的元素为:\n"; InOrderTraverse1(a); cout<<"\n"; break;
case 2: cout<<"按中序遍历法输出该二叉树的元素为:\n"; InOrderTraverse2(a); cout<<"\n"; break;
case 3: cout<<"按后序遍历法输出该二叉树的元素为:\n"; InOrderTraverse3(a); cout<<"\n"; break;
default: cout<<"错误重输!";break;
}
}
height=Depth(a);
num=NodeCount(a);
cout<<"\n该二叉树深度为:";
cout<<height<<endl;
cout<<"该二叉树结点数为:";
cout<<num<<endl;
return 0;
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。