#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;

}