#include < iostream.h >
#include < fstream.h >
#include < iomanip.h >
#include < stdlib.h >
#include "C_Queue.h"
#include "BinTree.h" //BinaryTree成員函數定義
template<class Type> void BinaryTree < Type >::destroy( BinaryTreeNode < Type > *current )
{//私有函數：若current不空，則刪除根為current 的子樹
	if(current!=NULL)
	{
		destroy(current->leftchild);
		destroy(current->rightchild);
        delete current;
	}
}

template<class Type> BinaryTreeNode < Type > *BinaryTree<Type>::Parent( BinaryTreeNode < Type > *start , BinaryTreeNode < Type > *current )
{//私有函數：從start 開始，搜索current的雙親結點。若找到，則函數返回雙親結點的地址，否則返回NULL
     if( start == NULL ) return NULL;
	 if( start -> leftchild == current || start -> rightchild == current ) return start;
	 BinaryTreeNode < Type > *p;
	 if( ( p = Parent ( start -> leftchild , current ) ) != NULL )   return P;
	 else return Parent ( start -> rightchild , current );
}

template < class Type > void BinaryTree< Type > :: Traverse1( const  BinaryTreeNode < Type > *current ) const
{//前序遍歷
	if(current!=NULL&&current->data!=RefValue)//相應的改變
	{
		cout<<current->data<<" ";
        Traverse1(current->leftchild);
		Traverse1(current->rightchild);
	}
}

template<class Type> void BinaryTree<Type>::Traverse1(BinaryTreeNode<Type>*current,ostream&out) const
{//前序遍歷
	if(current!=NULL&&current->data!=RefValue)//相應的改變
	{
		out<<current->data<<" ";
        Traverse1(current->leftchild,out);
		Traverse1(current->rightchild,out);
	}
}

template<class Type> void BinaryTree<Type>::Traverse2( const BinaryTreeNode<Type>*current) const
{//中序遍歷
	if(current!=NULL&&current->data!=RefValue)//相應的改變
	{
        Traverse1(current->leftchild);
		cout<<current->data<<" ";
		Traverse1(current->rightchild);
	}
}

template<class Type> void BinaryTree < Type >::Traverse2( BinaryTreeNode < Type > *current, ostream &out) const
{//中序遍歷
	if(current!=NULL&&current->data!=RefValue)//相應的改變
	{
        Traverse2(current->leftchild,out);
		out<<current->data<<" ";
		Traverse2(current->rightchild,out);
	}
}


template <class Type> istream & operator >>(istream & in, BinaryTree <Type> &Tree ) 
{//輸入重載	
	Type item;
	in>>item;
	while (item !=Tree.RefValue)
	{
		Tree.Insert(item);
		in>>item;
	}
	return in;
}

template <class Type> ostream & operator << ( ostream & out, BinaryTree<Type> &Tree )
{
//	out<<"前序遍歷 ：";
	Tree.Traverse1(Tree.root,out);
	out<<0<<" \n";
//	out<<"中序遍歷 ：";
	Tree.Traverse2(Tree.root,out);
	out<<0<<" \n";
    return out;
}

template<class Type> void BinaryTree<Type>:: Insert ( const Type&item,BinaryTreeNode<Type> * & current)
{//私有函數：在以current為根的二叉樹中插入所含值為item 的結點。若樹中已經有含item的結點則不插入
	if(current==NULL)
	{
		current=new BinaryTreeNode <Type>(item);
		if(current==NULL) {cerr<<"out of space /n";exit(1);}
	}
	else if(item<current->data)Insert(item,current->leftchild);//小于根的關鍵碼，向左子樹上插
	else if(item>current->data)Insert(item,current->rightchild);//大于根的關鍵碼，向右子樹上插
}

template<class Type> void BinaryTree<Type>:: Insert1 ( const Type&item,BinaryTreeNode<Type> * & current)
{//私有函數：在以current為根的二叉樹中插入所含值為item 的結點。若樹中已經有含item的結點則不插入
	if(current==NULL)
	{
		current=new BinaryTreeNode <Type>(item);
		if(current==NULL) {cerr<<"out of space /n";exit(1);}
	}
	else current ->data = item;
}

template<class Type> void BinaryTree<Type>::Remove(const Type&item,BinaryTreeNode<Type> * & current)
{
    BinaryTreeNode<Type>* temp;
	if(current!=NULL)
		if(item<current->data)Remove(item,current->leftchild);//在左子樹上刪除
		else if(item>current->data)Remove(item,current->rightchild);//在右子樹上刪除
		else if(current->leftchild!=NULL&&current->rightchild!=NULL)
		{//若有兩個子女
			temp=Min(current->rightchild);//在其右子樹上找最小結點
			current->data=temp->data;//用該結點的數據代替根結點的數據
			Remove(current->data,temp);//在右子樹上刪除該結點
		}
		else //只有一個子女
		{
			temp=current;
			if( current->leftchild==NULL )current=current->rightchild;
			else  if( current->rightchild==NULL ) current = current -> leftchild;
			temp -> SetData( RefValue );
		}
}

template<class Type> BinaryTreeNode<Type>*BinaryTree<Type>::Min(BinaryTreeNode<Type>* current)const//在其右子樹上找最小結點
{
	while(current!=NULL&&current->leftchild!=NULL) {current=current->leftchild;}//鑒于所建的樹自身的特點，其右子樹上最小結點在其左子樹的左子樹上，直至左葉結點處
	return current;
}

/******************************************************************************************************************************************************/

template < class Type > void BinaryTree< Type > :: Print( const  BinaryTreeNode < Type > *current ,int &i  ) const
{//凹入表輸出
	int j = i;
	if( current !=NULL && current -> data != RefValue )//相應的改變
	{
		cout <<setw( i+3 )<< current->data <<" \n";
        Print(current->leftchild , j+=3 );
		Print(current->rightchild , i+=3  );
	}
}

template <class Type> int equal ( BinaryTreeNode < Type > * a , BinaryTreeNode < Type > *b)
{//具體判斷函數
	if ( a == NULL && b == NULL ) return 1;
	if ( a != NULL && b != NULL && a->data == b->data 
		&& equal ( a->leftchild, b->leftchild )
		&& equal ( a->rightchild, b->rightchild )) return 1;
	return 0;
}

template <class Type> bool operator ==( BinaryTree<Type> &ta ,BinaryTree<Type> &tb )
{//判斷兩棵樹是否相等
    if ( equal( ta.root ,tb.root ) ) return true;
	else return false;
}

template<class Type> void BinaryTree<Type>::LevelOrder(  BinaryTreeNode < Type > *current ) const
{//層次輸出
	Queue < BinaryTreeNode < Type > * > Qu ( 30 );
   	BinaryTreeNode < Type > *p;
	if ( current != NULL )
	{//不空
		p = current ;Qu.EnQueue ( current );//入隊
		while ( !Qu.IsEmpty() )
		{//隊不空
			current = Qu.DeQueue( ); cout <<current->data<<" ";//節點出隊，訪問節點數據
			
			if ( current->leftchild !=NULL ) { Qu.EnQueue( current->leftchild ) ;   }//左孩子不空，入隊
			if ( current->rightchild !=NULL) { Qu.EnQueue( current->rightchild ) ;   }//右孩子不空，入隊
		}
	}
	current=p;
}

template<class Type> int BinaryTree<Type>:: Size(const BinaryTreeNode<Type> * t)const
{//計算t為根的二叉樹結點的個數
	if(t==NULL)return 0;
	else return 1+Size(t->leftchild)+Size(t->rightchild);
}

void PartionAndInsert( int *PreA , Da *IoA ,int  startp ,int starti ,int  end , BinaryTreeNode < int > * &current,BinaryTree < int > &tr )
{// 分子樹并將對應的節點插入新樹
	int j = startp;
	for ( int i = 0 ;i <= end ;i++ )
		if ( PreA[j] == IoA[i].data )
		{//前序遍歷第一個節點是子樹的根，在中序中的位置，左邊是它的左子樹，右邊是它的右子樹。
			if ( IoA[i].active != 1) 
			{
				tr.Insert1(  IoA[i].data,current);
				IoA[i].llen=i-starti;IoA[i].active = 1;
				if ( IoA[end].active == 1 )IoA[i].rlen=end-i-1;
				else IoA[i].rlen=end-i;
				if (  IoA[i].llen == 1 && IoA[i-1].active != 1) { IoA[i-1].active=1;	current ->leftchild = new BinaryTreeNode < int > ;tr.Insert1( IoA[i-1].data,current->leftchild);}//左子樹僅有一個節點則插入根左孩子節點
				else PartionAndInsert( PreA , IoA ,++startp,starti, i , current->leftchild,tr );//否則構造左子樹
				if (  IoA[i].rlen == 1 && IoA[i+1].active != 1 ){ IoA[i+1].active=1; current->rightchild = new BinaryTreeNode< int >;tr.Insert1( IoA[i+1].data,current->rightchild);}////右子樹僅有一個節點則插入根右孩子節點
				else PartionAndInsert( PreA , IoA ,++i ,i, end, current->rightchild,tr );//開始位置后置1（i++），否則構造右子樹
			}
			else  { j++;i =0;}
		}		
}

void ReConstruct ( BinaryTree < int >  &tr)
{
    const int arrysize  =  tr.Size( tr.GetRoot() );//樹的結點個數
	int arsze = arrysize-1;
	int *PreA = new int [arrysize];//存儲前序遍歷結果
	Da *IoA = new Da [arrysize];//存儲中序遍歷結果
	ifstream fin;
    fin.open("datafile.txt",ios::nocreate);
	if ( !fin ) { cerr<<"The datafile cannot be opened!\n";exit(1);}
    for ( int i = 0; i < arrysize ; i++  ){fin >>PreA[i]; }//讀入前序遍歷結果
	fin.ignore(2,'0');cout<<endl;
	for ( i = 0; i<arrysize; i++ ){fin>>IoA[i].data;IoA[i].active = 0;}//讀入中序遍歷結果
	fin.close();
	int start = 0;
	BinaryTree < int > newtree (0) ;//構造新樹newtree
	PartionAndInsert( PreA , IoA , start , start ,arsze, newtree.root,newtree );//分子樹，并插入節點。
	cout<<"\n\n\n   >********************************************<\n  newtree凹入表輸出：\n";
    i = 0 ;
    newtree.Print (newtree.GetRoot() , i );//凹入表輸出
	cout<<"\n\n   newtree前序遍歷 ：";
	newtree.Traverse1(newtree.GetRoot());
	cout<<"\n   newtree層次遍歷 ：";
    newtree.LevelOrder( newtree.GetRoot() );//層次輸出
	cout<<endl;
	if ( tr == newtree ) cout << "\n   newtree and tree   Equal! \nSuccessful! Reconstruct a BinaryTree  \n ";//判斷兩棵樹相等證明還原出原來的樹
	else cout << "\n   newtree and tree   Not Equal ! \n ";
	
}