#include<iostream>
using namespace std;
#define NUM 7

typedef struct bitree
{
	int data;
	struct bitree *left;
	struct bitree *right;
}BITREENODE,*PBITREENODE;

PBITREENODE BiTree=NULL;
//聲明函數原型；
void create_btree(int *A,int size);
void preorder(PBITREENODE pnode);
void inorder(PBITREENODE pnode);
void postorder(PBITREENODE pnode);
 
void levelorder(PBITREENODE pnode);
 
int main(void)
{
	int i;
	int A[NUM];
	cout<<"輸入樹的7個測試數據:";
	for(i=0;i<NUM;i++)
		cin>>A[i];
	cout<<endl;
	create_btree(A,NUM);

	cout<<"Tree 的中序遍歷結果:"<<endl;
	inorder(BiTree);
	cout<<endl;
	cout<<"tree 的前序遍歷結果:"<<endl;
	preorder(BiTree);
	cout<<endl;
	cout<<"tree 的后序遍歷結果"<<endl;
	postorder(BiTree);
	cout<<endl;
	cout<<"tree 的按層遍歷結果"<<endl;
	levelorder(BiTree);
	cout<<endl;
	return 0;
}
void create_btree(int *A,int size)
{
	int i;
	PBITREENODE ptr,ptr2;
	for(i=0;i<size;i++)
	{
		if(BiTree==NULL)
		{
			BiTree=new BITREENODE;
			if(BiTree==NULL)
			{
				cout<<"memory alloc fail";
				break;
			}
			BiTree->data=A[i];
			BiTree->left=NULL;
			BiTree->right=NULL;
			continue;
		}
		else
			ptr=BiTree;
		while(1)
		{
			if(A[i]>ptr->data)
			{
				if(ptr->right==NULL)
				{
					ptr2=new BITREENODE;
					if(ptr2==NULL)
					{
						cout<<"memory alloc fail";
						break;
					}
					ptr2->data=A[i];
					ptr2->left=NULL;
					ptr2->right=NULL;
					ptr->right=ptr2;
					break;
				}
				else
					ptr=ptr->right;
			}
			else
			{
				if(ptr->left==NULL)
				{
					ptr2=new BITREENODE;
					if(ptr2==NULL)
					{
						cout<<"memory alloc fail";
						break;
					}
					ptr2->data=A[i];
					ptr2->left=NULL;
					ptr2->right=NULL;
					ptr->left=ptr2;
					break;
				}
				else
					ptr=ptr->left;
			}
		}
	}
}
void postorder(PBITREENODE pnode)
{
	if(pnode!=NULL)
	{
		postorder(pnode->left);
		postorder(pnode->right);
		cout<<" "<<pnode->data;
	}
}
 

void preorder(PBITREENODE pnode)
{
	if(pnode!=NULL)
	{
		preorder(pnode->left);
		cout<<" "<<pnode->data;
		preorder(pnode->right);
	}
}
void inorder(PBITREENODE pnode)
{
	if(pnode!=NULL)
	{
		cout<<" "<<pnode->data;
		inorder(pnode->left);
		inorder(pnode->right);
	}
}
void levelorder(PBITREENODE pnode)
{
	PBITREENODE ptr,Tree[NUM];
	int i,front=-1,rear=0;
	for(i=0;i<NUM;i++)
		Tree[i]=NULL;
	ptr=pnode;
	while(ptr!=NULL)
	{
		cout<<" "<<ptr->data;
		if(ptr->left!=NULL)
			Tree[rear++]=ptr->left;
		if(ptr->right!=NULL)
			Tree[rear++]=ptr->right;
		if(front!=rear)
			ptr=Tree[++front];
	}
}