#include <iostream>
using namespace std;
typedef char TElemType;
typedef struct TNode
{
	TElemType data;
	TNode*parent,*fc,*ns;
}FNode,*tree,*forest;
typedef forest QElemType;
typedef struct QNode
{
	QElemType data;	QNode *next;
}*LQueuePtr;
struct LQueue{ LQueuePtr front,rear;};
void QueueInit(LQueue &Q);//队初始化
void Enqueue(LQueue &Q,QElemType e);//入队
bool Dequeue(LQueue &Q,QElemType &e);//出队
void ForestLists(tree T);
void TreeLists(tree T);
void CreateForest(forest &T, char s[], int &i);
void CreateForest(forest &T, char s[]);
void ForestLevelOrder(forest F, void visit(TElemType));//森林的层序遍历输出
void visit(TElemType data);
int main()
{
	forest F;
	char s[]="BC#D##F##";
	CreateForest(F,s);
	cout<<"该森林为："<<endl;
	ForestLists(F);
	cout<<endl<<"该森林的层序遍历输出为：";
	ForestLevelOrder( F,visit);
	cout<<endl;
	return 0;
}
void QueueInit(LQueue &Q)
{
	Q.front=new QNode;
	Q.front->next=NULL;
	Q.rear=Q.front;
}
void Enqueue(LQueue &Q,QElemType e)
{
	LQueuePtr p;
	p=new QNode;p->data=e;p->next=NULL;
	Q.rear->next=p;Q.rear=p;
}
bool Dequeue(LQueue &Q,QElemType &e)
{
	LQueuePtr p;
	if(Q.front==Q.rear) return false;
	p=Q.front;Q.front=p->next;e=Q.front->data;
	delete p;return true;	
}
void CreateForest(forest &T, char s[], int &i) 
{  
	i++;
	if (s[i] == '#') { T = NULL; return; }
	T = new TNode;
	T->data = s[i];      //建立根节点
	CreateForest(T->fc, s, i);
	CreateForest(T->ns, s, i);
}
void CreateForest(forest &T, char s[])
{  
	int i = -1;
	CreateForest(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 << ")";
}
void ForestLists(tree T)
{                    
	forest p = T;
	cout << "(";
	while (p) {
		TreeLists(p);
		p = p->ns;
		if (p)cout << ",";
	}
	cout << ")";
}
void visit(TElemType data)
 {
	cout << data;
}
void ForestLevelOrder(forest F, void visit(TElemType))
{
	LQueue q;forest x,y;
	if(!F)return ;
	QueueInit(q);
	for (F; F; F = F->ns) 
	{
		Enqueue(q,F);
	}
	while(Dequeue(q,x))
	{
		visit(x->data);
		for(y=x->fc;y;y=y->ns)		Enqueue(q,y);
	}
}