#include<iostream.h>
#include<STRSTREAM.H>
typedef char elemtype;
struct btreenode
{
elemtype data;
btreenode *lchild;
btreenode *rchild;
};
void initbtree ( btreenode *&bt )
{ bt=NULL;}
void precrttree ( btreenode *&bt )
{
char ch;
cin>>ch;
if ( ch=='#' )
bt=NULL;
else
{
bt=new btreenode;
bt->data=ch;
precrttree ( bt->lchild );
precrttree ( bt->rchild );
}
}
void crtbtree ( btreenode *&bt,char *a )
{
char ch;
btreenode *s[20];
int top=-1;
bt=NULL;
btreenode *p;
int k;
istrstream ins ( a );
ins>>ch;
while ( ch!='@' )
{
switch ( ch )
{
case'(':
top++;
s[top]=p;
k=1;
break;
case')':
top--;
break;
case',':
k=2;
break;
default:
p=new btreenode;
p->data=ch;
p->lchild=p->rchild=NULL;
if ( bt==NULL )
bt=p;
else
{
if ( k==1 ) s[top]->lchild=p;
else s[top]->rchild=p;
}
}
ins>>ch;
}
}
int btreeempty ( btreenode *bt )
{ return bt==NULL;}
void preorder ( btreenode *bt )
{
if ( bt!=NULL )
{
cout<<bt->data<<' ';
preorder ( bt->lchild );
preorder ( bt->rchild );
}
}
void inorder ( btreenode *bt )
{
if ( bt!=NULL )
{
inorder ( bt->lchild );
cout<<bt->data<<' ';
inorder ( bt->rchild );
}
}
void postorder ( btreenode *bt )
{
if ( bt!=NULL )
{
postorder ( bt->lchild );
postorder ( bt->rchild );
cout<<bt->data<<' ';
}
}
void levorder ( btreenode *bt )
{
btreenode *q[30];
int front=0,rear=0;
btreenode *p;
if ( bt!=NULL )
{
rear= ( rear+1 ) %30;
q[rear]=bt;
}
while ( front!=rear )
{
front= ( front+1 ) %30;
p=q[front];
cout<<p->data<<' ';
if ( p->lchild!=NULL )
{
rear= ( rear+1 ) %30;
q[rear]=p->lchild;
}
if ( p->rchild!=NULL )
{
rear= ( rear+1 ) %30;
q[rear]=p->rchild;
}
}
}
int btreedepth ( btreenode *bt )
{
if ( bt==NULL )
return 0;
else
{
int dep1=btreedepth ( bt->lchild );
int dep2=btreedepth ( bt->rchild );
if ( dep1>dep2 )
return dep1+1;
else
return dep2+1;
}
}
int btreecount ( btreenode *bt )
{
if ( bt==NULL )
return 0;
else
return btreecount ( bt->lchild ) +btreecount ( bt->rchild ) +1;
}
int btreeleafcount ( btreenode *bt )
{
if ( bt==NULL )
return 0;
else if ( bt->lchild==NULL&&bt->rchild==NULL )
return 1;
else return btreeleafcount ( bt->lchild ) +btreeleafcount ( bt->rchild );
}
void printbtree ( btreenode *bt )
{
if ( bt==NULL )
return;
else
{
cout<<bt->data;
if ( bt->lchild!=NULL||bt->rchild!=NULL )
{
cout<<'(';
printbtree ( bt->lchild );
if ( bt->rchild!=NULL )
cout<<',';
printbtree ( bt->rchild );
cout<<')';
}
}
}
void clearbtree ( btreenode *&bt )
{
if ( bt!=NULL )
{
clearbtree ( bt->lchild );
clearbtree ( bt->rchild );
delete bt;
bt=NULL;
}
}
void main()
{
btreenode *bt;
initbtree ( bt );
char b[50];
int tag;
cout<<"1.pre order create btree"<<endl;
cout<<"2.glist create btree"<<endl;
cout<<"input selecte 1 or 2:";
cin>>tag;
if ( tag==2 )
{
cout<<"input @ end glist:"<<endl;
cin.getline ( b,sizeof ( b ) );
crtbtree ( bt,b );
}
else
{
cout<<"input pretree and '#':"<<endl;
precrttree ( bt );
}
printbtree ( bt );
cout<<endl;
cout<<"pre order:";
preorder ( bt );
cout<<endl;
cout<<"in order:";
inorder ( bt );
cout<<endl;
cout<<"post order:";
postorder ( bt );
cout<<endl;
cout<<"level order:";
levorder ( bt );
cout<<endl;
cout<<"btree depth is:";
cout<<btreedepth ( bt ) <<endl;
cout<<"btree node num is:";
cout<<btreecount ( bt ) <<endl;
cout<<"btree leaf node num is:";
cout<<btreeleafcount ( bt ) <<endl;
clearbtree ( bt );
}