#include<iostream.h>
#include<windows.h>
#include<conio.h>

template <class T> class ThBSTree;

template <class T>
class ThBSTreeNode
{
	friend class ThBSTree<T>;
	private:
		T element;
		int lTag,rTag;
		ThBSTreeNode<T>* left;
		ThBSTreeNode<T>* right;
		
	public:
		ThBSTreeNode();
		ThBSTreeNode(const T& elem);
		ThBSTreeNode(const T& ele,ThBSTreeNode* l,int leftTag,ThBSTreeNode* r,int rightTag);
		T value() const;
		ThBSTreeNode<T>* leftchild() const;
		ThBSTreeNode<T>* rightchild() const;
		
		void setvalue(const T& val);
};

template <class T>
ThBSTreeNode<T>::ThBSTreeNode(const T& elem)
{
	element=elem;
	left=right=NULL;
	lTag=rTag=0;
}

template <class T>
ThBSTreeNode<T>::ThBSTreeNode(const T& ele,ThBSTreeNode<T>* l,int leftTag,ThBSTreeNode<T>* r,int rightTag)
{
	element=ele;
	left=l;
	lTag=leftTag;
	right=r;
	rTag=rightTag;
}

template <class T>
T ThBSTreeNode<T>::value() const
{
	return element;
}

template <class T>
ThBSTreeNode<T>* ThBSTreeNode<T>::leftchild() const
{
	return left;
}


template <class T>
ThBSTreeNode<T>* ThBSTreeNode<T>::rightchild() const
{
	return right;
}

template <class T>
void ThBSTreeNode<T>::setvalue(const T& val)
{
	element=val;
}


template <class T>
class ThBSTree
{
	protected:
		ThBSTreeNode<T>* root;
	public:
		ThBSTree(){root=NULL;};
		~ThBSTree(){DeleteThBSTree(root);};
		bool isempty() const
		{
			if(root==NULL)
				return true;
			else
				return false;
		};
		ThBSTreeNode<T>* getroot(){return root;};
		ThBSTreeNode<T>* getparent(ThBSTreeNode<T> *current);

		ThBSTreeNode<T>* findvalue(T elem);
		void AddNode(ThBSTreeNode<T>* p);
		void InsertNode(ThBSTreeNode<T>*p,ThBSTreeNode<T>*newpointer);
		void DeleteValue(T elem);
		void DeleteNode(ThBSTreeNode<T> *p);
		void CreatTree(const T& elem,ThBSTree<T> & lefttree,ThBSTree<T> & righttree);
		ThBSTreeNode<T>* Pre(ThBSTreeNode<T>*p);
		ThBSTreeNode<T>* Next(ThBSTreeNode<T>*p);

		void Inprint();
		void Preprint();

		void DeleteThBSTree(ThBSTreeNode<T>* root);
		
};

template <class T>
ThBSTreeNode<T>* ThBSTree<T>::findvalue(T elem)
{
	ThBSTreeNode<T> * pointer;
	if(root==NULL)
		return NULL;
	else
		pointer=root;
	while(pointer->left!=NULL)
		pointer=pointer->left;
	if(pointer->element>elem)
		return NULL;
	else if(pointer->element==elem)
		return pointer;
	while(Next(pointer)!=NULL&&Next(pointer)->element<elem)
		pointer=Next(pointer);
	pointer=Next(pointer);
	if(pointer==NULL)
		return NULL;
	else if(pointer->element==elem)
		return pointer;
	else 
		return NULL;
}

template <class T>
void ThBSTree<T>::DeleteValue(T elem)
{
	ThBSTreeNode<T>*p;
	while((p=findvalue(elem))!=NULL)
		DeleteNode(p);
}

template <class T>
void ThBSTree<T>::DeleteThBSTree(ThBSTreeNode<T> *root)
{
	if(root!=NULL)
	{
		if(root->lTag==0)
			DeleteThBSTree(root->left);
		if(root->rTag==0)
			DeleteThBSTree(root->right);
		delete root;
	}
}

template <class T>
ThBSTreeNode<T>* ThBSTree<T>::getparent(ThBSTreeNode<T>* current)
{
	ThBSTreeNode<T>* r=root;
	if(current==r)
		return NULL;
	while(1)
	{
		if(r->lTag==0&&r->left!=NULL)
		{
			if(r->left==current)
				return r;
		}
		if(r->rTag==0&&r->right!=NULL)
		{
			if(r->right==current)
				return r;
		}
		if(r->lTag==0&&r->element>current->element)
		{
			r=r->left;continue;
		}
		if(r->rTag==0&&r->element<current->element)
		{
			r=r->right;continue;
		}
	}
}

template <class T>
void ThBSTree<T>::AddNode(ThBSTreeNode<T>* p)
{
	ThBSTreeNode<T>* temp=root;
	if(root==NULL)
		root=p;
	else
	{
		if(p->element==temp->element)
		{
			InsertNode(temp,p);
		}
		else if(p->element>temp->element)
		{
			while(1)
			{
				ThBSTreeNode<T> * tempnext;
				if(temp->right==NULL)
					tempnext=NULL;
				else if(temp->rTag==1)
					tempnext=temp->right;
				else
				{
					tempnext=temp->right;
					while(tempnext->lTag==0)
						tempnext=tempnext->left;
				}
				if(tempnext==NULL||p->element<=tempnext->element)
				{
					InsertNode(temp,p);
					break;
				}
				temp=tempnext;
			}
		}
		else
		{
			while(1)
			{
				ThBSTreeNode<T> * tempbefore;
				if(temp->left==NULL)
					tempbefore=NULL;
				else if(temp->lTag==1)
					tempbefore=temp->left;
				else
				{
					tempbefore=temp->left;
					while(tempbefore->rTag==0)
						tempbefore=tempbefore->right;
				}
				if(tempbefore==NULL)
				{
					temp->left=p;
					temp->lTag=p->lTag=0;
					p->right=temp;
					p->rTag=1;
					break;
				}
				else if(p->element>=tempbefore->element)
				{
					InsertNode(tempbefore,p);
					break;
				}
				temp=tempbefore;
			}
		}
	}
}

template <class T>
void ThBSTree<T>::InsertNode(ThBSTreeNode<T> *p,ThBSTreeNode<T> *newpointer)
{
	ThBSTreeNode<T> *temppointer=NULL;
	if(p->right==NULL)
		temppointer=NULL;
	else if(p->rTag==1)
		temppointer=p->right;
	else
	{
		temppointer=p->right;
		while(temppointer->lTag==0)
			temppointer=temppointer->left;
	}
	if((temppointer!=NULL) && (temppointer->lTag==1))
		temppointer->left=newpointer;               
	newpointer->rTag=p->rTag;
	newpointer->right=p->rightchild();
	p->rTag=0;
	p->right=newpointer;
	newpointer->lTag=1;
	newpointer->left=p;
}

template <class T>
ThBSTreeNode<T>* ThBSTree<T>::Pre(ThBSTreeNode<T>*pointer)
{
	ThBSTreeNode<T>* temppointer=NULL;
	if(pointer->left==NULL)
		temppointer=NULL;
	else if(pointer->lTag==1)
		temppointer=pointer->left;
	else
	{
		temppointer=pointer->left;
		while(temppointer->rTag==0)
			temppointer=temppointer->right;
	}
	return temppointer;
}


template <class T>
ThBSTreeNode<T>* ThBSTree<T>::Next(ThBSTreeNode<T>*pointer)
{
	ThBSTreeNode<T>* temppointer=NULL;
	if(pointer->right==NULL)
		temppointer=NULL;
	else if(pointer->rTag==1)
		temppointer=pointer->right;
	else
	{
		temppointer=pointer->right;
		while(temppointer->lTag==0)
			temppointer=temppointer->left;
	}
	return temppointer;
}

template <class T>
void ThBSTree<T>::Inprint()
{
	ThBSTreeNode<T> * pointer;
	int i=0;
	if(root==NULL)
		return;
	else
		pointer=root;
	while(pointer->left!=NULL)
	{
		pointer=pointer->left;
		i++;
	}
	while(1)
	{
		for(int j=0;j<i;j++)
			cout<<"   ";
		cout<<pointer->element<<endl;
		if(pointer->right==NULL)
			return;
		if(pointer->rTag==1)
		{
			ThBSTreeNode<T> * temp=pointer->right;
			if(temp->lTag==1)
				i--;
			else
			{
				temp=temp->left;
				i--;
				while(temp->rTag==0)
				{
					temp=temp->right;
					i--;
				}
			}
			pointer=pointer->right;
		}
		else
		{
			pointer=pointer->right;
			i++;
			while(pointer->lTag==0)
			{
				pointer=pointer->left;
				i++;
			}
		}
	}
}

template <class T>
void ThBSTree<T>::Preprint()
{
	ThBSTreeNode<T> *p;
	int i=0;
	if(root==NULL)
		return;
	else
		p=root;
	ThBSTreeNode<T> * temp=p;
	while(p)
	{
		for(int j=0;j<i;j++)
			cout<<"   ";
		cout<<p->element<<endl;
		if(p->left!=NULL && p->lTag==0)
		{
			p=p->left;
			i++;
		}
		else
		{
			while(p->rTag==1)
			{
				temp=p->right;
				if(temp->lTag==1)
					i--;
				else
				{
					temp=temp->left;
					i--;
					while(temp->rTag==0)
					{
						temp=temp->right;
						i--;
					}
				}
				p=p->right;
			}
			p=p->right;
			i++;
		}
		
	}
}

template <class T>
void ThBSTree<T>::DeleteNode(ThBSTreeNode<T> *p)
{
	if(p==NULL)
		return;
	ThBSTreeNode<T> * temppointer,* temppointerpre,* temppointernext;
	ThBSTreeNode<T> * tempparent=NULL;
	ThBSTreeNode<T> * parent=getparent(p);
	if(p->left==NULL||p->lTag==1)//若欲刪結點的左子樹為空，就用它的右子樹代替它
	{
		if(parent==NULL)
		{
			root=p->right;
			temppointer=Next(p);
			if(temppointer!=NULL)
			{
				temppointer->left=NULL;
				temppointer->lTag=0;
			}
		}
		else if(parent->left==p)
		{
			if(p->rTag==0)
				parent->left=p->right;
			else
			{
				parent->left=NULL;
				parent->lTag=1;
			}
			temppointernext=Next(p);
			temppointerpre=Pre(p);
			if(temppointerpre!=NULL && temppointerpre->rTag==1)
			{
				temppointerpre->right=temppointernext;
				if(temppointernext==NULL)
					temppointerpre->rTag=0;
			}
			if(temppointernext!=NULL && temppointernext->lTag==1)
			{
				temppointernext->left=temppointerpre;
				if(temppointerpre==NULL)
					temppointernext->lTag=0;
			}
		}
		else
		{
			if(p->rTag==0)
				parent->right=p->right;
			else
			{
				parent->right=NULL;
				parent->rTag=1;
			}
			temppointernext=Next(p);
			temppointerpre=Pre(p);
			if(temppointerpre!=NULL && temppointerpre->rTag==1)
			{
				temppointerpre->right=temppointernext;
				if(temppointernext==NULL)
					temppointerpre->rTag=0;
			}
			if(temppointernext!=NULL && temppointernext->lTag==1)
			{
				temppointernext->left=temppointerpre;
				if(temppointerpre==NULL)
					temppointernext->lTag=0;
			}
		}
		delete p;
		p=NULL;
		return;
	}
	//當欲刪結點的左子樹不為空的情況，在左子樹尋找最大結點替換欲刪結點
	//注意可能有n個相等的最大結點，那么就把它們作為一個整體
	//samehead指向它們中的第一個，temppointer指向最后一個
	temppointer=p->left;
	ThBSTreeNode<T> * samehead=temppointer;
	while(temppointer->right!=NULL&&temppointer->rTag==0)
		temppointer=temppointer->right;
	while(samehead->element!=temppointer->element)
		samehead=samehead->right;
	tempparent=getparent(samehead);
	
	if(tempparent==p)
	{
		p->left=samehead->left;
		p->lTag=samehead->lTag;
	}
	else
	{
		if(samehead->lTag==0)
			tempparent->right=samehead->left;
		else
		{
			tempparent->rTag=1;
			tempparent->right=temppointer->right;
		}
	}
	if(parent==NULL)
		root=samehead;
	else if(parent->left=p)
		parent->left=samehead;
	else
		parent->right=samehead;
	
	temppointernext=Next(p);
	temppointerpre=Pre(samehead);
	if(temppointerpre!=NULL && temppointerpre->rTag==1)
	{
		temppointerpre->right=samehead;
		if(samehead==NULL)
			temppointerpre->rTag=0;
	}
	if(temppointernext!=NULL && temppointernext->lTag==1)
	{
		temppointernext->left=temppointer;
		if(temppointer==NULL)
			temppointernext->lTag=0;
	}
	samehead->left=p->left;
	samehead->lTag=p->lTag;
	temppointer->right=p->right;
	temppointer->rTag=p->rTag;
	delete p;
	p=NULL;
	return;
}

#define tree ThBSTree<int>

void MyInsertNode(tree & mytree);
void MyDeleteNode(tree & mytree);
void MyPreOrderPrint(tree & mytree);
void MyInOrderPrint(tree & mytree);

void main()
{
	tree mytree;
	char press;
	while(press!='q')
	{
		system("cls");
		cout<<"\t\tThreaded Binary Search Tree"<<endl;
		cout<<"\t----------------------------------------"<<endl;
		cout<<"\t\t\t(a)添加新結點"<<endl;
		cout<<"\t\t\t(b)刪除指定結點"<<endl;
		cout<<"\t\t\t(c)中序周游ThBST"<<endl;
		cout<<"\t\t\t(d)前序周游ThBST"<<endl;
		cout<<"\t\t\t(q)退出"<<endl;
		press=getch();
		switch(press)
		{
		case 'a':
			MyInsertNode(mytree);break;
		case 'b':
			MyDeleteNode(mytree);break;
		case 'c':
			MyInOrderPrint(mytree);break;
		case 'd':
			MyPreOrderPrint(mytree);break;
		case 'q':                   
			break;
		default:
			break;
		}
	}
}

void MyInsertNode(tree & mytree)
{
	system("cls");
	cout<<"\t\tThreaded Binary Search Tree"<<endl;
	cout<<"\t----------------------------------------"<<endl;
	cout<<"\t\t\t添加新結點"<<endl<<endl<<endl<<endl;
	cout<<"請輸入欲插入的結點值：";
	int value;
	cin>>value;
	mytree.AddNode(new ThBSTreeNode<int>(value));
}

void MyDeleteNode(tree & mytree)
{
	system("cls");
	cout<<"\t\tThreaded Binary Search Tree"<<endl;
	cout<<"\t----------------------------------------"<<endl;
	cout<<"\t\t\t刪除指定結點"<<endl<<endl<<endl<<endl;
	if(mytree.isempty())
	{
		cout<<"該樹為空樹，請先輸入結點再刪除"<<endl;
		cout<<"任意健繼續..."<<endl;
		getch();
	}
	else
	{
		int value;
		cout<<"請輸入欲刪除的結點值：";
		cin>>value;
		if(mytree.findvalue(value)==NULL)
		{
			cout<<"不存在該值的結點！"<<endl;
			cout<<"任意健繼續..."<<endl;
			getch();
		}
		else
		{
			mytree.DeleteValue(value);
			cout<<"刪除成功！"<<endl;
			cout<<"任意健繼續..."<<endl;
			getch();
		}
	}
}

void MyInOrderPrint(tree & mytree)
{
	system("cls");
	cout<<"\t\tThreaded Binary Search Tree"<<endl;
	cout<<"\t----------------------------------------"<<endl;
	cout<<"\t\t\t中序周游ThBST"<<endl<<endl<<endl<<endl;
	if(mytree.isempty())
	{
		cout<<"該樹為空樹，不能打印"<<endl;
		cout<<"任意健繼續..."<<endl;
		getch();
	}
	else
	{
		mytree.Inprint();
		cout<<"任意健繼續..."<<endl;
		getch();
	}
}

void MyPreOrderPrint(tree & mytree)
{
	system("cls");
	cout<<"\t\tThreaded Binary Search Tree"<<endl;
	cout<<"\t----------------------------------------"<<endl;
	cout<<"\t\t\t前序周游ThBST"<<endl<<endl<<endl<<endl;
	if(mytree.isempty())
	{
		cout<<"該樹為空樹，不能打印"<<endl;
		cout<<"任意健繼續..."<<endl;
		getch();
	}
	else
	{
		mytree.Preprint();
		cout<<"任意健繼續..."<<endl;
		getch();
	}
}