#include <iostream>
using namespace std;
typedef char TElemType;
typedef struct TNode
{
TElemType data;
TNode*parent,*fc,*ns;
}*tree;
void Treelists(tree T);//树的广义表形式输出
int duTree(tree T);//非空树的度
void CreateTree(tree &T, char s[]);
void CreateTree(tree &T, char s[], int &i);
int main()
{
tree T;
char s[]="ABDF##E##C#H###";
//char s[]="AB#C###";
//char s[]="A##";
CreateTree(T,s);
cout<<"该树的广义表形式输出为："<<endl;
Treelists(T);
cout<<endl<<"该树的度为"<<duTree(T)<<endl;
return 0;
}
void CreateTree(tree &T, char s[], int &i)
{
i++;
if (s[i] == '#') { T = NULL; return; }
T = new TNode;
T->data = s[i];
CreateTree(T->fc, s, i);
CreateTree(T->ns, s, i);
}
void CreateTree(tree &T, char s[])
{
int i = -1;
CreateTree(T, s, i);
}
void Treelists(tree T)
{
tree p;
if(!T){cout<<'#';return;}
cout<<T->data;
p=T->fc; if(!p) return;
cout<<'(';
while(p)
{
Treelists(p);p=p->ns;
if(p) cout<<',';
}
cout<<')';
}
int duTree(tree T)
{
int m = 0;
if (!T) { return 0; }
tree p = T->fc;
while (p)
{
m++;
p=p->ns;
}
int n1 = duTree(T->fc);
if (n1 > m)m = n1;
int n2 = duTree(T->ns);
return m > n2 ? m : n2;
}