#include <iostream.h>
#include <malloc.h>
#define Maxsize 100
#define Maxwidth 40
typedef char elemtype;
typedef struct node
{elemtype data;
struct node *left,*right;
}btree;
void dispstack(btree *stack[],int top);
void creatree(btree *&b,char *str)
{btree *stack[Maxsize],*p;
int top=-1,k,j=0;
char ch;
b=NULL;
ch=str[j];
while(ch!='\0')
{
switch(ch)
{case '(':
top++;
stack[top]=p;
k=1;
break;
case ')':
top--;
break;
case ',':k=2;
break;
default: p=(btree *)malloc(sizeof(btree));
p->data=ch;
p->left=p->right=NULL;
if(b==NULL) b=p;
else{
switch(k)
{case 1:stack[top]->left=p;
break;
case 2:stack[top]->right=p;
break;
}
}
}
j++;
ch=str[j];
}
}
void disptree(btree *b)
{
btree *stack[Maxsize],*p;
int level[Maxsize][2],top,n,i,width=4;
char type;
if(b!=NULL)
{
top=1;
stack[top]=b;
level[top][0]=width;
level[top][1]=2;
while(top>0)
{
p=stack[top];
n=level[top][0];
switch(level[top][1])
{case 0:type='0';
break;
case 1:type='1';break;
case 2:type='2';break;
}
for(i=1;i<n;i++)
cout<<"";
cout<<p->data<<"("<<type<<")";
for(i=n+1;i<=Maxwidth;i+=2)
cout<<"--";
cout<<endl;
top--;
if(p->right!=NULL)
{top++;
stack[top]=p->right;
level[top][0]=n+width;
level[top][1]=1;
}
if(p->left!=NULL)
{
top++;
stack[top]=p->left;
level[top][0]=n+width;
level[top][1]=0;
}
}
}
}
void printree(btree *b)
{if(b!=NULL)
{
cout<<b->data;
if(b->left!=NULL||b->right!=NULL)
{
cout<<"(";
printree(b->left);
if(b->right!=NULL)
cout<<",";
printree(b->right);
cout<<")";
}
}
}
void preorder(btree *b)
{
if(b!=NULL)
{
cout<<b->data<<" ";
preorder(b->left);
preorder(b->right);
}
}
btree *find(btree *b,elemtype x)
{
btree *p;
if(b==NULL)
return NULL;
else if(b->data==x)
return b;
else
{p=find(b->left,x);
if(p!=NULL)return p;
else
return find(b->right,x);
}
}
void inorder(btree *b)
{
if(b!=NULL)
{inorder(b->left);
cout<<b->data<<" ";
inorder(b->right);
}
}
void postorder(btree *b)
{
if(b!=NULL)
{postorder(b->left);
postorder(b->right);
cout<<b->data<<" ";
}
}
int treedepth(btree *b)
{
int leftdep,rightdep;
if(b==NULL)
return(0);
else
{leftdep=treedepth(b->left);
rightdep=treedepth(b->right);
if(leftdep>rightdep)return(leftdep+1);
else
return(rightdep+1);
}
}
void porder(btree *b)
{
btree *stack[Maxsize],*p;
int top;
if(b!=NULL)
{
top=1;
stack[top]=b;
while(top>0)
{
p=stack[top];
top--;
cout<<p->data<<" ";
if(p->right!=NULL)
{
top++;
stack[top]=p->right;
}
if(p->left!=NULL)
{
top++;
stack[top]=p->left;
}
}
}
}
void main()
{
btree *b;
creatree(b,"(a(b(c),d(e(,f),g)))");
cout<<"嵌套表示法:";
printree(b);
cout<<endl<<"先序遍历:";
porder(b);
cout<<endl;
}
