#include <iostream.h>
typedef struct BiTNode
{
 char ch;
 int nNum;
 struct BiTNode *lChild,*rChild;
}BiTNode,BTree,*BiTree;


typedef struct QueueNode
{
 BiTree data;
 struct QueueNode *next;
}QNode,*QueuePtr;
typedef struct
{
 QNode *front,*rear;
}LinkQueue;

bool InitQueue(LinkQueue &Q)
{
 Q.front =Q.rear =new(QueueNode);
 if(!Q.front ) return false;
 Q.front->next =NULL;
 Q.rear->next =NULL;
return true;
}

bool EnQueue(LinkQueue &Q,BiTree data)
{
 QueuePtr p=new(QueueNode);
 if(!p) {cout<<"Alloc error"<<endl; return false;}
 p->data =data;
 Q.rear ->next =p;
 Q.rear =p;

return true;
}
bool DeQueue(LinkQueue &Q,BiTree &data)
{
 if(Q.rear ==Q.front) return false;
 QueuePtr p=Q.front ->next ;
 data=p->data;
 Q.front->next =p->next ;
 if(Q.rear ==p) Q.rear =Q.front ;
 delete [] p;
return true;
}

BiTree CreNode()
{
 BiTree tree;
 tree=new(BiTNode);
 tree->ch=0;
 tree->lChild =NULL;
 tree->rChild =NULL;
 tree->nNum =0;
return tree;
}

BiTree LevelCreateTree()
{
 LinkQueue Q;
 InitQueue(Q);
  int n=1;
 int i;
 BiTree tree,p;
 cout<<"請(qǐng)輸入虛結(jié)點(diǎn)個(gè)數(shù):";
 cin>>i;
 char ch;
 tree=CreNode();
 EnQueue(Q,tree);
 while(n<=i)
 {
     DeQueue(Q,p);
     cin>>ch;
  if(ch=='@') break;
  p->ch=ch;
  p->nNum =n++;
  if(ch=='#')
  {
  p->lChild =NULL;
  p->rChild =NULL;
  }
  else
  { p->lChild =CreNode();
   p->rChild =CreNode();
  if(p->lChild) EnQueue(Q,p->lChild );
  if(p->rChild) EnQueue(Q,p->rChild );}
 }

return tree;
}
void PreTrav(BiTree tree)
{
 if(tree==NULL) return;
   cout<<"No:"<<tree->nNum<<"Value:"<<tree->ch<<endl;
   PreTrav(tree->lChild );
   PreTrav(tree->rChild );
}
LinkQueue LQ;
void TravelTree(BiTree tree)
{
 BiTree p;
 if(tree==NULL) return;
 EnQueue(LQ,tree);
 while(LQ.rear!=LQ.front )
 {
  DeQueue(LQ,p);
  cout<<"節(jié)點(diǎn)號(hào):"<<p->nNum<<"值:"<<p->ch<<endl;
  if(p->lChild ) EnQueue(LQ,p->lChild);
  if(p->rChild ) EnQueue(LQ,p->rChild);
 }
}
void main()
{
 BiTree tree;
 InitQueue(LQ);
 tree=LevelCreateTree();
 cout<<"層次創(chuàng)建并層次遍歷"<<endl;
 TravelTree(tree);
 cout<<"前序遍歷"<<endl;
 PreTrav(tree);
}