#include <iostream.h>
#include <malloc.h>			
#include <stdio.h>			
#include <stdlib.h>
#define N 50
#define OVERFLOW 0
#define NULL 0

typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;		
}*BiTree;		

typedef struct queue
{
	BiTree elem;
	int front;
	int tail;
}queue;

void CreateBiTree(BiTree &T)	//先序擴展序列建立二叉樹的遞歸算法 
{  
	char ch;
	scanf("%c",&ch);
	if (ch=='*') 
	{
		T = NULL;		
	}
	else 
	{ 
		if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
		{
			exit(OVERFLOW);
		}
		T->data=ch;
		CreateBiTree(T->lchild); 
		CreateBiTree(T->rchild); 
	}  
} 


queue* CreateQueue () 
 {							// 構造一個空隊列Q
	queue *q;
	q=(queue *) malloc(sizeof (queue));
	if (!q) exit (OVERFLOW);	
    q->elem = (BiTree) malloc(N*sizeof (struct BiTNode));
    if (!q->elem) exit (OVERFLOW);		              
    q->front = q->tail = 0;
     return q;
 }


BiTree SubQueue(queue *q)
{
	BiTree p;
	p=&(q->elem[q->front]);
	(q->front)++;
	return p;
}


void AddQueue(queue *q,BiTree T)
{
	q->elem[q->tail]=*T;
	q->tail++;
	return;
}


void main()	//層次遍歷二叉樹的非遞歸算法的主程序
{
	queue *q;
    BiTree p;
    BiTree b;		
	printf("請按先序擴展序列輸入二叉樹,空用*表示\n");
	CreateBiTree(b);
    printf("\n層次遍歷二叉樹\n");	
	q=CreateQueue();				
	AddQueue(q,b);					
	while(q->front!=q->tail)		
		{
			p=SubQueue(q);
			printf("%c",p->data);
			if(p->lchild) AddQueue(q,p->lchild);
			if(p->rchild) AddQueue(q,p->rchild);
		}
	
	printf("\n");
}