#include<iostream.h>
typedef char DataType;

class CSTree{
    DataType  d;
    CSTree *c,*s;
public:
    void Out();//输出
    char *Create(CSTree *T,char *s);//创建
    int Depth(CSTree *T);//求树深
    int Node(CSTree *T);//求结点数
    int Leaf(CSTree *T);//求叶子数
    void FRT(CSTree *T);//按先根遍历输出
    void LRT(CSTree *T);//按后根遍历输出
};

void CSTree::Out(){//按广义表形式输出
    cout<<'(';
    if(!this){cout<<')'; return ;}//空树
    cout<<'(';
    cout<<this->d;//输出根
    if(this->c){cout<<',';this->Out();}//输出子树
    cout<<')';
    if(this->s){cout<<',';this->Out();}//输出小兄弟
    cout<<')';
}
char *CSTree::Create(CSTree *T,char *s){//按广义表形式输入
    if(*s!='('||!*++s||*s=='('||*s==','){
        cout<<"\n非法字符串!"<<endl;    throw;
    }
    if(*s==')'){T=0;    return s;}
    T=new CSTree;
    if(!T){cout<<"\n内存不足!"<<endl;    throw;}
    T->d=*s;    T->s=0;    CSTree *p=T;
    while(*++s==',')s=Create(p->s,s+1),    p=p->s;//兄弟链
    T->c=T->s;
    T->s=p->s=0;//长子
    if(*s!=')'){cout<<"\n非法字符串!"<<endl;    throw;}
    return s;
}
int CSTree::Depth(CSTree *T){//求树深
    int i,j=0;
    if(!this)return 0;
    i=1+Depth(this->c);//本树深度
    j=Depth(this->s);//兄弟们深度
    return(i>j?i:j);
}
int CSTree::Node(CSTree *T){//求结点数
    if(!this)return 0;
    return Node(this->c)+Node(this->s)+1;
}
int CSTree::Leaf(CSTree *T){//求叶子数
    if(!this)return 0;
    if(!this->c&&!this->s)return 1;
    return Leaf(this->c)+Leaf(this->s);
}
void CSTree::FRT(CSTree *T){//按先根遍历输出
    if(!this)return;
    cout<<this->d<<' ';
    FRT(this->c);
    FRT(this->s);
}
void CSTree::LRT(CSTree *T){//按后根遍历输出
    if(!this)return;
    LRT(this->c);
    cout<<this->d<<' ';
    LRT(this->s);
}

void main(){
    CSTree *t=0;
    cout<<"T=";   t->Out();
    t->Create(t,"(A,(B,(D),(E,(H),(I)),(F)),(C,(G)))");
    cout<<"\nT=";t->Out();
    cout<<"\n树深="<<t->Depth(t);
    cout<<"\n结点数"<<t->Node(t);
    cout<<"\n叶子数="<<t->Leaf(t);
    cout<<"\n先根遍历：";    t->FRT(t);
    cout<<"\n后根遍历：";    t->LRT(t);
    cout<<endl;
}