#include <iostream>
#include <iomanip>
using namespace std;

//*************************************************************************************
//二叉樹結點類的定義
template<class T>
struct BTNode
{
	T data;
	BTNode <T> * left,*right;
	BTNode(T nodeValue = T(),BTNode<T>* leftNode = NULL,BTNode<T>* rightNode = NULL )
		:data(nodeValue),left(leftNode),right(rightNode){}       //可選擇參數的默認構造函數
};

//*******************************************************************
//基本的二叉樹類
template <class T> class BTree
{

public:
	BTree(BTNode <T> *root );
	~BTree(){MakeEmpty();}
	void MakeEmpty(){destroy(root); root=NULL;}

	void createBTree(BTNode<T> *&root);
	void preOrder(BTNode<T> *&root);
protected:
	BTNode<T> *root;
private:
	void destroy(BTNode<T> *p)
	{
		if(p)
		{
			destroy(p->left);
			destroy(p-right);
			delete p;
		}
	}
};

template <class T> BTree<T>::BTree(BTNode<T> *root =NULL)
{
	root=root;
}
template <class T> void BTree<T>::createBTree(BTNode<T> *&root)
{
	BTNode<T> *p = root;
	BTNode<T> *k=NULL;
	T nodeValue;
	cin>>nodeValue;
	if(nodeValue==-1)
	{
		root=NULL;
	}
	else
	{
		root=new BTNode<T>();
		root->data=nodeValue;
		createBTree(root->left);
		createBTree(root->right);
	}
}
template <class T>void BTree<T>::preOrder(BTNode<T> *&root)
{
	if(root)
	{
		cout<<setw(4)<<root->data;
		preOrder(root->left);
		preOrder(root->right);
	}
}
// void main()
// {
// 	BTree<int> *t=NULL;
// 	BTNode<int> * root=NULL;
// 	t->createBTree(root);
// 	t->preOrder(root);
// 
// }