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