#include <iostream.h>
#include "P170.cpp"
#include "Stack.h"
const MaxN=30;
template <class Type> class BST;							//二叉搜索樹的前視聲明

template <class Type> class BstNode : public BinTreeNode<Type> {			//二叉搜索樹結點類
friend class BST;
public:
   BstNode ( const Type d=0, BstNode *L=NULL, BstNode *R =NULL)			//構造函數
      : data (d), leftChild (L), rightChild (R) { };
   ~BstNode ( ) { }
   friend class BST<Type>;
protected:
   Type data;										//數據域(用作關鍵碼)
   BstNode<Type> *leftChild, *rightChild;						//左子女和右子女鏈域
};

template <class Type> class BST : BinaryTree <Type> {					//二叉搜索樹類定義
public:
	BST ( ) :root(NULL){};								//構造函數
   BST ( Type value ) ;
   BST (const BST<Type> & T) ;//構造函數
   ~BST ( ) { MakeEmpty (  ); }							//析構函數
   const BST & operator = ( const BST & Value );
   void MakeEmpty( ) { destroy (root);  root=NULL; }
   void PrintTree ( ) const { PrintTree ( root ); }
   int Find ( const Type & x ) const { return (Find ( x, root )!=NULL) ; }	//搜索元素
   Type Min() { return Min(root)->data;};										//求最小
   Type Max() { return Max(root)->data;};										//求最大
   int Insert ( const Type & x ) { return Insert ( x, root ); }				//插入新元素
   int Remove (const Type & x ) { return Remove ( x, root ); }				//刪除含x的結點
   BstNode<Type> *Split ( Type i, BST<Type> &B, Type &x, BST<Type> &C );
   void OpticBST ( int p[ ], int q[ ], Type a[ ], int n );
   friend class BSTIterator ;//中序游標類
   
private:											//在關鍵碼i處分解二叉搜索樹
   BstNode<Type> *root;								//二叉搜索樹的根指針
   Type RefValue;										//數據輸入停止的標志, 用于輸入
   BstNode<Type> *lastfound;								//最近搜索到的結點的指針
//   void MakeEmpty ( BstNode<Type> * ptr );					//置空
   int Insert ( const Type & x, BstNode<Type> * & ptr );			//插入
   int Remove ( const Type & x, BstNode<Type> * & ptr );			//刪除
   void PrintTree ( BstNode<Type> * ptr ) const;					//打印
   BstNode<Type> *Copy (const BstNode<Type> * ptr );				//復制
   BstNode<Type> *Find (const Type & x, BstNode<Type> * ptr ) const;	//搜索
   BstNode<Type> *Min ( BstNode<Type> * ptr ) const;				//求最小
   BstNode<Type> *Max ( BstNode<Type> * ptr ) const;				//求最大 
};
/*
template <class Type> 
BstNode<Type> * BST<Type>::Find (const Type & x, BstNode<Type> * ptr ) const {
//私有函數：在以ptr為根的二叉搜索樹中搜索含x的結點。若找到，則函數返回該結點的地址，否則函數返回
//NULL值。
   if ( ptr == NULL ) return NULL;
   else if ( x < ptr->data ) return Find ( x, ptr->leftChild );			//到左子樹中繼續搜索
	 else if ( x > ptr->data ) return Find( x, ptr->rightChild );			//到右子樹中繼續搜索
	    else return ptr;								//搜索成功
}
*/
template <class Type> BstNode<Type> *BST<Type>::Find (const Type & x, BstNode<Type> * ptr ) const {
//私有函數: 說明與程序7.14相同
   if ( ptr != NULL ) {									//樹空返回
	 BstNode<Type> * temp = ptr;							//從根開始搜索
	 while ( temp != NULL ) {								//==NULL表示搜索失敗
	    if ( temp->data == x ) return temp;					//搜索成功
	    if ( temp->data < x ) temp = temp->rightChild;				//否則，繼續搜索右子樹
	    else temp = temp->leftChild;						//否則，繼續搜索左子樹
	 }
   }
   return NULL;
};
template <class Type> int BST<Type>::
Insert (const Type & x, BstNode<Type> * & ptr) {
//私有函數：在以ptr為根的二叉搜索樹中插入所含值為x的結點。若在樹中已經有含x的結點，則不插入。
   if ( ptr == NULL )	{							//新結點作為葉結點插入
	 ptr = new BstNode<Type> (x);						//創建新結點
	 if ( ptr == NULL ) return 0; else return 1;
   }
   else if ( x < ptr->data ) return Insert ( x, ptr->leftChild );			//小于根的關鍵碼, 向左子樹插入
	 else if ( x > ptr->data ) return Insert ( x, ptr->rightChild );		//大于, 向右子樹插入
   return 1;
							//除上述情況外, 就是x已在樹中的情形, 不再插入
}



template <class Type>BST<Type>::BST ( Type value ) {
//輸入一個元素序列, 建立一棵二叉搜索樹
   Type x;  root = NULL;  RefValue = value;			//置空樹
   cin >> x;									//輸入數據
   while ( x != RefValue )
   {						//RefValue是一個輸入結束標志
      Insert ( x, root );  cin >> x;					//插入，再輸入數據
   }
}

template <class Type>
void BST<Type>::PrintTree ( BstNode<Type> * ptr ) const					//打印
{
	if (ptr!=NULL)
	{
		cout<<ptr->data;
		cout<<"(";
		PrintTree(ptr->leftChild);
		cout<<",";
		PrintTree(ptr->rightChild);
		cout<<")";
	}
}


template <class Type> int BST<Type>::Remove (const Type &x, BstNode<Type> * &ptr) {
//私有函數：在以ptr為根的二叉搜索樹中刪除含x的結點。若刪除成功則新根通過ptr返回。
   BstNode<Type> * temp;
   if ( ptr != NULL )
	if ( x < ptr->data ) return Remove ( x, ptr->leftChild );				//在左子樹中執行刪除
	else if ( x > ptr->data )  return Remove ( x, ptr->rightChild );			//在右子樹中執行刪除
	   else if ( ptr->leftChild != NULL && ptr->rightChild != NULL )	{
						// ptr指示關鍵碼為x的結點，它有兩個子女
		   temp = Min ( ptr->rightChild );					//在ptr的右子樹中搜尋最小結點
		   ptr->data = temp->data;						//用該結點數據代替根結點數據
		   return Remove ( ptr->data, ptr->rightChild );				//在右子樹中刪除該結點
		 }
		 else {				// ptr指示關鍵碼為x的結點，它只有一個或零個子女
			  temp = ptr;
			  if ( ptr->leftChild == NULL ) ptr = ptr->rightChild;		//只有右子女
			  else if ( ptr->rightChild == NULL ) ptr = ptr->leftChild;	//只有左子女
		      delete temp;
		      return 1;
		    }
   else return 0;
}
template <class Type> class InorderIterator	{	    			//中序游標類定義
public:
   InorderIterator ( BST<Type> & Tree ) : ref (Tree) { Init ( ); }
   int Init ( );									//初始化
   int operator ! ( );								//求反
   Type operator ( ) ( );								//取棧頂元素值
   int operator ++ ( );								// BST按前序進行遍歷
private:
   BST<Type> & ref;								//二叉搜索樹對象
   Stack < BstNode<Type> * > itrStack;					//迭代工作棧
};

template <class Type> int InorderIterator<Type>::Init ( ) {			//初始化操作
   itrStack.MakeEmpty ( );								//置迭代工作棧為空
   if ( ref.root != NULL ) itrStack.Push ( ref.root );				//若二叉搜索樹不空則根指針進棧
   return ! itrStack.IsEmpty ( );							//若棧空則返回0，否則返回1
}

template <class Type> int InorderIterator<Type>::operator ! ( ) {
   return ! itrStack.IsEmpty ( );							//若棧空則返回0，否則返回1
}

template <class Type> Type InorderIterator<Type>::operator ( ) ( ) {	//返回當前結點的數據值
   Node<Type> * current = itrStack.GetTop ( );				//取棧頂結點為當前結點
   return current->data;								//返回當前結點的關鍵碼
}

template <class Type> int InorderIterator<Type>::operator ++ ( ) {
//按二叉搜索樹結點的前序序列進棧。還可以向前走則函數返回1, 否則返回0。
   BstNode<Type> * current = itrStack.GetTop ( );				//取存在棧頂上的結點
   BstNode<Type> * next = current->leftChild;				//左子女
   if ( next != NULL ) { itrStack.Push ( next );  return 1; }			//左子女非空, 進棧(向左子樹遍歷)
   while ( ! itrStack.IsEmpty ( ) ) {						//否則, 若棧非空
      current = itrStack.Pop ( );   next = current->rightChild;		//退棧, 取其右子女
      if ( next != NULL ) { itrStack.Push ( next );  return 1; }		//右子女非空, 進棧
   }
   return 0;
}

/*template <class Type>
BST<Type>::BST (const BST<Type> & T) : root (NULL) {
//構造函數：根據參數初始化樹T
   InorderIterator<Type> itr ( Type );						//聲明中序游標類對象
   for ( itr.init ( ); ! itr; itr++) Insert ( itr ( ) );				//按前序順序插入
}*/

template <class Type>
BstNode<Type> * BST<Type>::Min ( BstNode<Type> * ptr ) const				//求最小
{
  BstNode<Type> * temp1,*temp2;
  temp1=ptr;
  if (ptr!=NULL)
  {
    if (ptr->leftChild!=NULL)
    {
	temp2=Min(ptr->leftChild);
	if (temp1->data>temp2->data) temp1=temp2;
    }
    if (ptr->rightChild!=NULL)
    {
	temp2=Min(ptr->rightChild);
	if (temp1->data>temp2->data) temp1=temp2;
    }
  }
  return temp1;
}

template <class Type>
BstNode<Type> * BST<Type>::Max ( BstNode<Type> * ptr ) const				//求最小
{
  BstNode<Type> * temp1,*temp2;
  temp1=ptr;
  if (ptr!=NULL)
  {
    if (ptr->leftChild!=NULL)
    {
	temp2=Max(ptr->leftChild);
	if (temp1->data<temp2->data) temp1=temp2;
    }
    if (ptr->rightChild!=NULL)
    {
	temp2=Max(ptr->rightChild);
	if (temp1->data<temp2->data) temp1=temp2;
    }
  }
  return temp1;
}


template <class Type> void BST<Type>::OpticBST ( int p[ ], int q[ ], Type a[ ], int n ) {
//給定n個不同的數據 a[1] < a[2] < … < a[n], 以及它們具有的權值p[j], 1 ( j ( n, 另外落在它們之間外部
//結點上的權值分別為 q[i], 0 ( i ( n。本算法計算a[i+1], ……, a[j]的最優二叉搜索樹T[i][j]的代價C[i][j],
//T[i][j]的根R[i][j]和權W[i][j]。
   int R[MaxN+1][MaxN+1];
   int C[MaxN+1][MaxN+1];
   int W[MaxN+1][MaxN+1];
   for ( int i=0; i<n; i++) 
   {
	 W[i][i] = q[i];  C[i][i] = R[i][i] = 0;		//初始化
	 W[i][i+1] = W[i][i] + p[i+1] + q[i+1];		//構造只有一個內部結點, 兩個外部結點的最優二叉搜索樹
	 R[i][i+1] = i+1;					//這些樹的根在i+1
	 C[i][i+1] = W[i][i+1];				//這些樹的總帶權路徑長度(代價)
   }
   W[n][n] = q[n];  R[n][n] = C[n][n] = 0;
   for ( int m=2; m<=n; m++ )				//構造具有m個內部結點的最優二叉搜索樹
	 for ( i=0; i<=n-m; i++ ) 
	 {
	   int j = i + m;   W[i][j] = W[i][j-1] + p[j] + q[j];  //在前一棵樹基礎上再加一內部結點和一外部結點
	   int min = C[i+1][j],  u = i+1;			//假定i+1為根, 計算代價
	   for ( int k=i+2; k<=j; k++ )
   		if ( C[i][k-1] + C[k][j] < min ) 
		{ min = C[i][k-1] + C[k][j];  u = k; }
									//輪流以i+2,…,j為根, 選代價最小的送min, 其根為u
		C[i][j] = W[i][j] + min;  R[i][j] = u;
	 }
    Stack < int > nodeStack;
	MakeEmpty();
	nodeStack.Push(0);
	nodeStack.Push(n);
	while (!nodeStack.IsEmpty()) 
	{
		int j=nodeStack.Pop();
		int i=nodeStack.Pop();
		Insert(a[R[i][j]]);
		if ((i+1)<R[i][j])
		{
			nodeStack.Push(i);
			nodeStack.Push(R[i][j]-1);
		};
		if ((R[i][j])<j)
		{
			nodeStack.Push(R[i][j]);
			nodeStack.Push(j);
		};
	}
}