#include<iostream.h>
#include<stdlib.h>

typedef struct BSTreeNode
{
	int data;
	struct BSTreeNode *leftChild;
	struct BSTreeNode *rightChild;
}BSTreeNode;

class BSTree
{
	public:
		BSTree(void);
		void Display(void);//顯示這個樹
		void Insert(int data);//在樹中插入一個值
		Delete(int data);//在樹中刪除一個值
		BSTreeNode* Find(int data);//在樹中查找一個值
		~BSTree();
	private:
		BSTreeNode* buildTree(BSTreeNode* head,int number);//建立一個樹
		BSTreeNode* search(BSTreeNode* head ,int data);//查找
		BSTreeNode* BSTree::searchParent(BSTreeNode* head,BSTreeNode* p);//查找出p的父親節點的指針
		BSTreeNode* BSTree::searchMinRight(BSTreeNode* head);//找到右子樹中最小的節點
		void showTree(BSTreeNode* head);//顯示
		void destroyTree(BSTreeNode* head);//刪除
		BSTreeNode *head;
};

//建立一個二叉排序樹
BSTree::BSTree()
{
   cout<<"Build the BSTree  (end with -1): "<<endl;
   head=NULL;
   int number;
   cin>>number;
   while(number!=-1)
   {
		head=buildTree(head,number);
		cin>>number;  
   }
}

//建立
BSTreeNode* BSTree::buildTree(BSTreeNode* head,int number)
{
	BSTreeNode *p;    
	p=new BSTreeNode;
    p->data=number;
	p->leftChild=p->rightChild=NULL;
	if(head==NULL)
	{
		return p;
	}
	else
	{
       if(p->data<head->data)
		   head->leftChild=buildTree(head->leftChild,number);
	   else
		   head->rightChild=buildTree(head->rightChild,number);
	   return head;
	}
}

//插入一個結點
void BSTree::Insert(int data)
{
	head=buildTree(head,data);
}

//查找一個結點
BSTreeNode* BSTree::Find(int data)
{
	return search(head,data);
}

BSTreeNode* BSTree::search(BSTreeNode* head ,int data)
{  
	if(head==NULL)
		return NULL;
	if(head->data==data)
		return head;
	else 
	{
		if(data<head->data)
			return search(head->leftChild,data);
		else
			return search(head->rightChild,data);
	}
}

//刪除一個結點
BSTree::Delete(int data)
{
	BSTreeNode *p;
	p=NULL;
    p=search(head,data);
	if(p==NULL)
	{
		cout<<"Not find."<<endl;
	}
	else
	{
    if(p==head)
	{
		head=NULL;
	}
	else
	{ 
		BSTreeNode* parent;
		parent=searchParent(head,p);
		if(p->leftChild==NULL&&p->rightChild==NULL)//葉子節點
		{
			if(parent->leftChild==p)
			{
				parent->leftChild=NULL;
			}
			else
			{
				parent->rightChild=NULL;

			}
		}
        else//非葉子節點
		{
           if(p->rightChild==NULL)//該節點沒有右孩子
			{
				if(parent->leftChild==p)
				{
					parent->leftChild=p->leftChild;
				}
				 else
				{
					 parent->rightChild=p->leftChild;
				}
			}
			else//該點有左右孩子
			{
				BSTreeNode *rightMinSon,* secondParent;//secondParent為右子樹中的最小節點的父親
				rightMinSon=searchMinRight(p->rightChild);
				secondParent=searchParent(p->rightChild,rightMinSon);
				secondParent->leftChild=rightMinSon->rightChild;
				if(p->rightChild==rightMinSon)//右子樹中的最小節點的父親為p
				{
					p->rightChild=rightMinSon->rightChild;
				}
				p->data=rightMinSon->data;
			} 
		}
	}
	}
}

BSTreeNode* BSTree::searchParent(BSTreeNode* head,BSTreeNode* p)
{
	if(head->leftChild==p||head->rightChild==p||head==p||head==NULL)
		return head;
    else
	{
		if(p->data<head->data)
			return searchParent(head->leftChild,p);
		else
			return searchParent(head->rightChild,p);
	}
}

BSTreeNode* BSTree::searchMinRight(BSTreeNode* head)//找到右子樹中最小的節點
{
	if(head->leftChild==NULL||head==NULL)
	{
		return head;
	}
	else
	{
		return searchMinRight(head->leftChild);
	}
}

//顯示二叉排序樹
void BSTree::Display(void)
{
	showTree(head);
	cout<<endl;
}

void BSTree::showTree(BSTreeNode* head)
{
	if(head!=NULL)
	{
		showTree(head->leftChild);
		cout<<head->data<<' ';
		showTree(head->rightChild);
	}
}

//刪除整棵二叉排序樹
BSTree::~BSTree()
{
	cout<<"Deleted the Whole Tree!"<<endl;
	destroyTree(head);
}

void BSTree::destroyTree(BSTreeNode* head)
{
	if(head!=NULL)
	{
		destroyTree(head->leftChild);
		destroyTree(head->rightChild);
		delete head;
	}

}

//showmessage
void print()
{
	cout<<endl
	<<"1.Display "
    <<"2.Insert "
	<<"3.Find "
	<<"4.Delete"<<endl;
}

/*
template<class Type> class BSBSTreeNode<Type>::public BinBSTreeNode<Type>{
//二叉排序樹結點類的定義
	friend class BSTree<Type>;
	public:
		BSBSTreeNode():leftChild(NULL),rightChild(NULL){}//構造函數
		BSBSTreeNode(const Type d):data(d),leftChild(NULL),rightChild(NULL){}
		//構造函數
		~BSBSTreeNode(){}
		void displayTree(void)
        void showTree(BinBSTreeNode* head);
	protected:
		Type data;
		BSBSTreeNode<Type>* leftChild,* rightChild;
};

template<class Type> class BSTree<Type>::public BinaryTree<Type>
{
	public:
		BSTree()(void);//構造函數
		~BSTree();//析構函數
		BSBSTreeNode<Type>* Find(const Type &k) const
			{return Find(k,root);}//查找
		Type Min();
		Type Max();
		void Insert(const Type &x)
			{Insert(x,root);}
		void Delete(const Type &k)
			{Delete(k,root);}
	private:
		BSBSTreeNode<Type>* root;
		BSBSTreeNode<Type>* Find(const Type &k,BSBSTreeNode<Type>* p)const;
		void Insert(const Type &x,BSBSTreeNode<Type>* &p);
		void Delete(const Type &k,BSBSTreeNode<Type>* &p);
		BSBSTreeNode<Type>* head;
}*/

/*template<class Type>BSBSTreeNode<Type>*BSTree<Type>::          //遞歸
Find(const Type &k,BSBSTreeNode<Type>*p)const{
	if(p==NULL)
		return NULL;
	else if(k<p->data)
		return Find(k,p->leftChild);
	   else if(k>p->data)
		   return Find(k,p->rightChild);
	      else return p;
}

template<class Type>					非遞歸
BSBSTreeNode<Type> * BSTree<Type>::
Find(const Type &k,BSBSTreeNode<Type>*p)const{
	BSBSTreeNode<Type>* temp=p;
	if(p!=NULL){
		while(temp!=NULL){
			if(temp->data==k)return temp;
			if(temp->data<k)
				temp=temp->rightChild;
			else temp=temp->leftChild;}
	}
		return temp;
}

template<class Type> void<Type>BSTree<Type>::
Insert(const Type &k,BSBSTreeNode<Type>* &p){
	if(p==NULL) 
		p=new BSBSTreeNode<Type>(k);
	else if(k<p->data)
		 Insert(k,p->leftChild);
	else if(k>p->data)
		 Insert(k,p->rightChild);
	else
	{
		cout<<"There has node k"<<end;
		exit(1);
	}
}

template<class Type> void<Type> BSTree<Type>::
Delete(const Type &k,BSBSTreeNode<Type>* &p){
	BSBSTreeNode<Type>* temp;
	if(p!=NULL)
	   if(k<p->data)
		 Delete(k,p->leftChild);
	else if(k>p->data)
		 Delete(k,p->rightChild);
	else if(p->leftChild!=NULL&&p->rightChild!=NULL)
	{
		temp=Min(p->rightChild);
		p->data=temp->data;
		Delete(p->data,temp);
	}
	else
	{
		temp=p;
	    if(p->leftChild==NULL)
			p=p->rightChild;
		else
			p=p->leftChild;
		delete temp;
	}
}

template<class Type>
void<Type>BSTree<Type>::displayTree(void)
{

showTree(Head);
cout<<endl;
}
template<class Type>
void<Type> BSTree<Type>::showTree(BSBSTreeNode* Head)
{

if(Head!=NULL)
{
showTree(Head->left ) ;

    cout<<Head->key<<' ' ;

showTree(Head->right) ;

}

template<class Type>
Type<Type>BSTree<Type>::
Min(BSBSTreeNode<Type>*& p){
	if(p->leftChild!=NULL)
		p=p->leftChild;
	return p->data;
}
template<class Type>
Type<Type>BSTree<Type>::
Max(BSBSTreeNode<Type>*& p){
	if(p->rightChild!=NULL)
		p=p->rightChild;
	return p->data;
}
*/