#include<iostream>
#include<cmath>
#include<stdio.h>
using namespace std;
#define MAXSIZE 50
#define FALSE 0
#define TRUE 1
//定義二叉樹
typedef struct Node
{
	char data;
	struct Node *Lchild;
	struct Node *Rchild;
}BiTNode,*BiTree;



/***************************************************
typedef struct Node
{
	char data;
	struct Node  *next;
}LinkQueueNode;


typedef struct
{
	LinkQueueNode *front;
	LinkQueueNode *rear;
}LinkQueue;


int InitQueue(LinkQueue *Q) 
{  Q->front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
	if(Q->front!=NULL)
	{
		Q->rear=Q->front;
		Q->front->next=NULL;
		return 1;
	}

	else  return 0;
}


int EnterQueue(LinkQueue *Q,char x)
{
	LinkQueueNode *NewNode;
    NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
	if(NewNode!=NULL)
	{
		NewNode->data=x;
		NewNode->next=NULL;
		Q->rear->next=NewNode;
		Q->rear=NewNode;
		return 1;
	}
	else  return 0;
}



int DeleteQueue(LinkQueue *Q,char *x)
{
	LinkQueueNode *p;
	if(Q->front==Q->rear)
	   return 0;
	p=Q->front->next;
	Q->front->next=p->next;
	if(Q->rear==p)
	  Q->rear=Q->front;
	*x=p->data;
	free(p);
	return 1;
}
******************************************************/

template<class Type>
class SeqQueue{
	public:
		SeqQueue():front(0),rear(0){}
		//~SeqQueue();
		int EnterQueue(Type x)
		{
			if((rear+1)%MAXSIZE==front)
				return(FALSE);
			element[rear]=x;
			rear=(rear+1)%MAXSIZE;
			return(TRUE);
		}


		int DeleteQueue(Type *x)
		{
			if(front==rear) return(FALSE);
			*x=element[front];
			front=(front+1)%MAXSIZE;
			return(TRUE);
		}
		int IsEmpty()
		{
			if(front==rear) 
			{
				//cout<<"該隊列為空";
				return(TRUE);
			}
			else return(FALSE);
		}

	private:
		Type element[50];
		int front,rear;
};





void CreateBiTree(BiTree * bt)
{
	char ch;
	ch=getchar();
	if(ch=='.')*bt=NULL;
	else
	{
		*bt=(BiTree)malloc(sizeof(BiTNode));
		(*bt)->data=ch;
		CreateBiTree(&((*bt)->Lchild));
        CreateBiTree(&((*bt)->Rchild));
	}
}










void Print(BiTree bt)
{
	int i=0,n=0,j;
	SeqQueue<BiTree>Q;
	BiTree p=(BiTree)malloc(sizeof(BiTNode));

	if(bt==NULL)return;
	Q.EnterQueue(bt);

	while(!Q.IsEmpty())
	{
		Q.DeleteQueue(&p);
		j=n;
		n=log(i+1);
		i++;
		if(j!=n)cout<<endl;

		int t=1;
		for(int k=0;k<n+1;k++)
			t=2*t;

		if(p->data!='#')
		{
			for(int i=0;i<t;i++)
				cout<<" ";
			cout<<p->data;
			for(int q=0;q<t;q++)
				cout<<" ";
			for(int g=0;g<t;g++)
				cout<<" ";

            if(p->Lchild)
			{
				Q.EnterQueue(p->Lchild);
			}
			else
			{
                BiTree a=(BiTree)malloc(sizeof(BiTNode));
				a->data='#';

				Q.EnterQueue(a);
			}

			if(p->Rchild)
			{
				Q.EnterQueue(p->Rchild);
			}
			else
			{
                BiTree b=(BiTree)malloc(sizeof(BiTNode));
				b->data='#';

				Q.EnterQueue(b);
				//Q.EnterQueue('#');
			}
		}
		else
		{
			for(int i=0;i<2*t;i++)
			{
				cout<<" ";
			}
		}
	}
}


void main()
{
	BiTree root;
	//用擴展先序遍歷二叉樹
	cout<<"輸入擴展線序遍歷序列："<<endl;
	CreateBiTree(&root);

	//打印輸出二叉樹
	Print(root);



}