#include "iostream"
using namespace std;

template <class Type> class BinaryTree;								//二叉樹類BinaryTree的向前說明
template <class Type> class BinaryNode                                //二叉樹結點類
{
	friend class BinaryTree < Type >;
private:
	BinaryNode <Type> *left, *right ;                              //結點的左右兒子的地址
    Type data;                                                          //結點的數據信息
	int S;                                                       
public:
	BinaryNode ( ) : left (NULL), right (NULL) { }					//二叉樹結點的構造函數
	BinaryNode (Type item, BinaryNode <Type> *L = NULL, BinaryNode <Type> *R = NULL)
	: data (item) , left (L), right (R) { }
	Type GetData () const {return data;}                              //得到二叉樹的結點數據值
    BinaryNode <Type> * GetLeft () const {return left;}              //得到二叉樹結點的左兒子地址
	BinaryNode <Type> * GetRight () const {return right;}           //得到二叉樹結點的右兒子地址
	void SetData (const Type & item) {data = item;}                  //設置二叉樹結點的數據值	
	void SetLeft (BinaryNode <Type> *L) {left =L;}              //設置二叉樹結點的左兒子地址
	void SetRight (BinaryNode <Type> *R) {right = R;}             //設置二叉樹結點的左兒子地址
	int FloorNum (const BinaryNode <Type> *T ) const ;                 //必須是完全二叉樹的結點
    int Size (const BinaryNode <Type> *T ) const;                      //得到二叉樹的結點數
	int Height (const BinaryNode <Type> *T) const;					//得到二叉樹的高度
	void PrintPreOrder() const ;									//按前序打印二叉樹的結點的數據值
	void PrintPostOrder() const ;									//按后序打印二叉樹的結點的數據值
	void PrintInOrder() const ;										//按中序打印二叉樹的結點的數據值
	BinaryNode < Type > * Duplicate () const ;						//復制二叉樹中的所有結點
};

template<class Type>
void BinaryNode <Type>:: PrintPreOrder() const 
{
	cout <<" Data is in PreOrder" << data << "." << endl;
	if (left != NULL) left -> PrintPreOrder();
	if (right != NULL) right -> PrintPreOrder() ;
}

template<class Type>
void BinaryNode <Type>::PrintInOrder() const 
{	
	if (left != NULL) left -> PrintInOrder();
	cout << "Data is in InOrder" << data << "." << endl;
	if (right != NULL) right -> PrintInOrder() ;
}

template <class Type>
void BinaryNode <Type> :: PrintPostOrder() const 
{
	if (left != NULL) left -> PrinPostOrder();
	if (right != NULL) right -> PrintPostOrder() ;
	cout << "Data is in PostOrder" << data << "." << endl;
}

template <class Type>
Type Max(const Type u, const Type v) 
{
	if (u > v) return u;
	else return v;
}

template <class Type>
int BinaryNode <Type> :: Height(const BinaryNode <Type> *T) const
{
	if (T == NULL) return 0;
	else return 1 + Max(Height(T -> left), Height(T -> right));
}

template <class Type>
int BinaryNode<Type> :: Size(const BinaryNode<Type> *T) const
{
	if (T == NULL) return 0;
	else return 1 + Size(T -> left) + Size(T -> right);
}

template<class Type>
int BinaryNode<Type> :: FloorNum(const BinaryNode <Type>* T) const 
{
	int floor = 0;
	int i = T -> S;
	while(i>0)
	{
		i = i / 2;
		floor++;
	}
    return ++floor;
}

template <class Type> class BinaryTree               
{
private:                                    
	BinaryNode <Type> *root;
	BinaryTree(const BinaryTree<Type> &T);
	void DelTree(BinaryNode <Type> * T);
	void PreOrderNumber(int &n, BinaryNode<Type> *p);
	void InOrderNumber(int &n, BinaryNode<Type> *p);
	void PostOrderNumber(int &n, BinaryNode<Type> *p);
	void ChildNumber(BinaryNode<Type> *p);
public:
	BinaryTree ( ) : root (NULL) {}						//構造空二叉樹
	BinaryTree (const Type & value) { root = new BinaryNode< Type > ( value );}
	~BinaryTree() {DelTree (root);}
	bool IsEmpty() const {return root == NULL;}         //二叉樹為空，返回非0，否則為0
	const BinaryNode <Type> * Getroot ( ) const {return root;}  
	void MakeEmpty() {Deltree( root ); root = NULL;}    //使二叉樹為空        
	const BinaryTree <Type> & operator = (const BinaryTree <Type> &T);
	void PrintInSequence();                                         
	void PrintChild( );                                             
	void PrintPreOrderNumber();                                    
	void PrintInOrderNumber();                                     
	void PrintPostOrderNumber();                                   

};

template < class Type >
void BinaryTree<Type> :: DelTree (BinaryNode <Type> *T)
{
	if (T != NULL)
	{
		DelTree(T -> left);
		DelTree (T -> right);
		delete [] T;
	}
}

template <class Type>
void BinaryTree<Type> :: PrintInSequence()       
{
	if (IsEmpty()) 
	{
		cout<<"The BinaryTree is Empty!"<<endl;
		return;
	}
	else
	{
		Queue<BinaryNode<Type> *>P;
		int Seq=0;
		Queue<int> SequenceNumber;
		P.EnQueue(root);
        Seq ++;
		SequenceNumber.EnQueue(1);
		while (!P.IsEmpty())
		{
			cout <<"Data is:"<<P.Front() -> data<<endl;
			cout <<"Level number is:"<<SequenceNumber.Front()<<endl;
			if (P.Front() -> left != NULL)
			{
				P.EnQueue(P.Front() -> left);
				SequenceNumber.EnQueue(1 + SequenceNumber.Front());
			}
			if (P.Front()-> right != NULL)
			{
				P.EnQueue(P.Front() -> right);
				SequenceNumber.EnQueue(1 + SequenceNumber.Front()) ;
			}
			P.Front() -> Sequence = Seq;
			P.DeQueue();
			SequenceNumber.DeQueue();
		}
	}
	
}

template<class Type>
void BinaryTree<Type> :: PrintPreOrderNumber()
{
    if (IsEmpty()) 
	{
		cout <<"Tree is Empty!"<<endl;
		return;
	}
	else
	{
		int n = 1;
		PreOrderNumber(n, root);
	}
}

template<class Type>
void BinaryTree<Type> :: PreOrderNumber(int &n, BinaryNode<Type> *p)
{
	cout <<"Data is :"<<p -> data<<endl;
	cout <<"The Number in PreOrder is:"<<n<<endl;
	n++;
	if (p -> left != NULL) PreOrderNumber(n, p ->left);
	if (p -> right != NULL) PreOrderNumber(n, p -> right);
}

template<class Type>
void BinaryTree<Type> :: PrintInOrderNumber()
{
    if (IsEmpty()) 
	{
		cout <<"Tree is Empty!"<<endl;
		return;
	}
	else
	{
		int n = 1;
		InOrderNumber(n, root);
	}
}

template<class Type>
void BinaryTree<Type> :: InOrderNumber(int &n , BinaryNode<Type> *p)
{
	if (p -> left != NULL) InOrderNumber(n, p ->left);
    cout <<"Data is :"<<p -> data<< endl;
	cout <<"The Number in InOrder is:"<<n<< endl;
	n++;
	if (p -> right != NULL) InOrderNumber(n, p -> right);
}

template<class Type>
void BinaryTree<Type> :: PrintPostOrderNumber()
{
    if (IsEmpty()) 
	{
		cout <<"Tree is Empty!"<<endl;
		return;
	}
	else
	{
		int num = 1;
		PostOrderNumber(num, root);
	}
}

template<class Type>
void BinaryTree<Type> :: PostOrderNumber(int &num, BinaryNode<Type> *p)
{
	if (p -> left != NULL) PostOrderNumber(num, p -> left);
  	if (p -> right != NULL) PostOrderNumber(num, p -> right);
    cout <<"Data is :"<<p -> data<<endl;
	cout <<"The Number in PostOrder is: "<<num<<endl;
	num++;
}

template <class Type>
void BinaryTree<Type> :: PrintChild( )
{
	if (IsEmpty()) 
	{
		cout <<"Tree is empty!"<<endl;
		return;
	}
	else
	{
        ChildNumber(root);
	}
}

template <class Type>
void BinaryTree<Type> :: ChildNumber(BinaryNode<Type> *P)
{
	cout <<"Data is:" <<P -> data<<endl;
	cout <<"ChildNumber is:";
	cout <<P -> Size(P) - 1<<endl;
	if (P -> left != NULL) ChildNumber(P -> left);
	if (P -> right != NULL) ChildNumber(P -> right);
}

int main ()
{
	return 0;
}