#include<iostream.h>
#include<stdlib.h>
#define max 100
typedef int BinTreeNode[max+1];
class BinTree
{
	BinTreeNode BT;
public:
	void InitBT(BinTreeNode BT);
	void InsertBT(BinTreeNode BT);
    void createBT(BinTreeNode BT);
	void Inorder(BinTreeNode BT,int i);
	void Preorder(BinTreeNode BT,int i);
	void Lastorder(BinTreeNode BT,int i);
	void Levelorder(BinTreeNode BT,int i);
	void menu();
};
void BinTree::Levelorder(BinTreeNode BT,int i)
{
	for(i=1;i<=max;i++)
		if(BT[i])
		cout<<BT[i]<<"   ";
}
void BinTree::Lastorder(BinTreeNode BT,int i)
{
	if(i>max||!BT[i])
		return;
	Lastorder(BT,2*i);
	Lastorder(BT,2*i+1);
	cout<<BT[i]<<"   ";
}
void BinTree::Preorder(BinTreeNode BT,int i)
{
	if(i>max||!BT[i])
		return;
	cout<<BT[i]<<"   ";
	Preorder(BT,2*i);
	Preorder(BT,2*i+1);
}
void BinTree::Inorder(BinTreeNode BT,int i)
{
	if(i>max||!BT[i])
		return;
	Inorder(BT,2*i);
	cout<<BT[i]<<"    ";
	Inorder(BT,2*i+1);
}

void BinTree::createBT(BinTreeNode BT)
{
	int n;
	cout<<"please input the length BinaryTree:"<<endl;
	cin>>n;
	BT[0]=1;
	for(int i=1;i<=n;i++)
		InsertBT(BT);
}

void BinTree::InitBT(BinTreeNode BT)
{
	for(int i=1;i<=max;i++)
		BT[i]=0;
}
void BinTree::InsertBT(BinTreeNode BT)
{
	int k,done=1,e;
	while(done==1)
	{
		cout<<"input the number and data you want to insert  :"<<endl;
		cin>>k>>e;
		if(k<=max&&BT[k/2])
		{
			BT[k]=e;
			done=0;
		}
		else
			cout<<"you put the wrong number .please put it again:"<<endl;
	}
}
void BinTree::menu()
{
	cout<<"  ********************************************************************"<<endl;
	cout<<"  &                歡迎進入二叉樹遍歷演示系統                        &"<<endl;
    cout<<"  &                                                                  &"<<endl;
	cout<<"  &         1.創建二叉樹                   2、前序遍歷二叉樹         &"<<endl;
	cout<<"  &         3.中序遍歷二叉樹　　　　　　　 4.后序遍歷二叉樹　　　　　&"<<endl;
	cout<<"  &         5.層序遍歷二叉樹　　　　　　　 6.退出　　　　　　　　　　&"<<endl;
	cout<<"  &                                                                  &"<<endl;
	cout<<"  &  １－６鍵選擇操作：　　　　　　　　　　　　　　　　　　　　　　　&"<<endl;
	cout<<"  &                                                                  &"<<endl;
	cout<<"  ********************************************************************"<<endl;
}
 

void main()
{
	int i=1;
	BinTreeNode bt;
	BinTree binarytree;
	binarytree.menu();
	binarytree.InitBT(bt);
	int n;
	cin>>n;
	while(n!=6)
	{
		switch(n)
		{
		case 1:
			{
			binarytree.createBT(bt);
			cout<<"您輸入的順序為：";
			binarytree.Levelorder(bt,i);
			}break;
		case 2:
			{
			cout<<"您輸入的順序為：";
			binarytree.Levelorder(bt,i);
			cout<<"前序遍歷順序為：";
			binarytree.Preorder(bt,i);
			}break;
		case 3:
			{
			cout<<"您輸入的順序為：";
			binarytree.Levelorder(bt,i);
			cout<<"中序遍歷順序為：";
			binarytree.Inorder(bt,i);
			}break;
		case 4:
			{
			cout<<"您輸入的順序為：";
			binarytree.Levelorder(bt,i);
			cout<<"后序遍歷順序為：";
			binarytree.Lastorder(bt,i);
			}break;
		case 5:
			{
			cout<<"您輸入的順序為：";
			binarytree.Levelorder(bt,i);
			cout<<"層次遍歷順序為：";
			binarytree.Levelorder(bt,i);
			}break;
		default:cout<<"輸入錯誤！請重新輸入："<<endl;
			break;
		}
		cout<<endl;
		binarytree.menu();
		cin>>n;
	}

}