#include<iostream.h>
#include<malloc.h>
struct bitree
{
	char data;
	struct bitree *lchild,*rchild;
};
bitree *s,*root;
bitree *Creat()
{
		int front,rear;
		bitree *p[100];//存儲數據
		char ch;
		root=NULL;
		front=1;
		rear=0;
		cout<<"輸入二叉樹的數據"<<endl;
		cin>>ch;
		while(ch!='!')
		{
			s=NULL;
			if(ch!='!')
			{
				s=(struct bitree*)malloc(sizeof(bitree));
				s->data=ch;
				s->lchild=NULL;
				s->rchild=NULL;
			}
			rear++;
			p[rear]=s;
			if(rear==1)
				root=s;
			else
			{
			if(s&&p[rear])
				if(rear%2==0) p[front]->lchild=s;
				else
					p[front]->rchild=s;
				if(rear%2==1)
					front++;
			}
		cin>>ch;
		}
		return root;
}	
Preorder(bitree *t)
	{
		if(t)
		{
			cout<<t->data<<endl;
			Preorder(t->lchild);
			Preorder(t->rchild);
		}
	}
Inorder(bitree *t)
	{
		if(t)
		{
			Inorder(t->lchild);
			cout<<t->data<<endl;
			Inorder(t->rchild);
		}
	}
Postorder(bitree *t)
	{
		if(t)
		{
			Postorder(t->lchild);
			Postorder(t->rchild);
			cout<<t->data<<endl;
		}

	}
void main()
{
	int k;
	cout<<"輸入1進入程序，其它退出程序"<<endl;
	cin>>k;
	while(k==1)
	{
	bitree *m;
	char n;
	int i,j;
	m=Creat();
	cout<<"輸入I"<<endl;
		cin>>i;
	cout<<"輸入1進行前續輸出，2進行中續，3進行后續,否則輸入錯誤"<<endl;
	s=root;
	if(i==1)
	{
		cout<<"前續輸出"<<endl;
		n=Preorder(s);
	}
	if(i==2)
	{
		cout<<"中續輸出"<<endl;
		n=Inorder(s);
	}
	if(i==3)
	{
		cout<<"后續輸出"<<endl;
		n=Postorder(s);
	}
	if(i>3)
		cout<<"輸入錯誤"<<endl;
	cout<<"繼續輸入k"<<endl;
	cin>>k;
	}
	cout<<"退出程序"<<endl;
	
}