// BinarySearchTree.h: interface for the BinarySearchTree class.
//
//////////////////////////////////////////////////////////////////////
#include "BinaryTreeNode.h"
#include "BinaryTree1.h"

#if !defined(AFX_BINARYSEARCHTREE_H__1CD2FF9D_73F2_4194_974A_12892DFB325F__INCLUDED_)
#define AFX_BINARYSEARCHTREE_H__1CD2FF9D_73F2_4194_974A_12892DFB325F__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

template <class T>
class BinarySearchTree:public BinaryTree<T> 
{
public:
	BinarySearchTree(){};
	virtual ~BinarySearchTree(){};
	void InsertNode(BinaryTreeNode<T>* root,BinaryTreeNode<T>* newpointer);
	void DeleteNode(BinaryTreeNode<T>* pointer);
	void DeleteNodeEx(BinaryTreeNode<T>* pointer);
};
template <class T>
void BinarySearchTree<T>::InsertNode(BinaryTreeNode<T>* root,BinaryTreeNode<T>* newpointer)
{
	BinaryTreeNode<T>* pointer=NULL;
	//初始化
	if(NULL==root)
	{
		//用指針newpointer初始化二叉搜索樹樹根，賦值實現
		Initialize(newpointer);
		return;
	}
	else pointer=root;
	while(1)
	{
		if(newpointer->value()==pointer->value())
			return ;									//相等則不用插入
		else if(newpointer->value()<pointer->value())	//作為左子樹
		{
			if(pointer->leftchild()==NULL)				
			{
				pointer->left=newpointer;
				return;
			}
			else	pointer=pointer->leftchild();

		}
		else{											//作為右子樹
			if(pointer->rightchild()==NULL)
			{
				pointer->right=newpointer;
				return;
			}
			else	pointer=pointer->rightchild();
		}
	}
}
template <class T>
void BinarySearchTree<T>::DeleteNode(BinaryTreeNode<T>* pointer)
{//二叉搜索樹的刪除
	BinaryTreeNode<T>* temppointer=NULL;	
	if(!pointer)
		return;
	BinaryTreeNode<T>* parent=GetParent(root,pointer);
	//被刪結點無左子樹嗎？
	if(NULL==pointer->leftchild())
	{
		//被刪除結點是根結點嗎？
		if(NULL==parent)
			root=pointer->rightchild();
		else if(parent->leftchild()==pointer)
			parent->left=pointer->rightchild();
		else
			parent->right=pointer->rightchild();
		delete pointer;
		pointer=NULL;
		return;
	}
	else temppointer=pointer->leftchild();
	//在左子樹中找對稱序的最后一個結點
	while(temppointer->rightchild()!=NULL)
		temppointer=temppointer->rightchild();
	//被刪除結點的右子樹作為temppointer的右子樹
	temppointer->right=pointer->rightchild();
	//被刪除結點的左子樹根代替被刪除結點
	if(parent==NULL)
		root=pointer->leftchild();
	else if(parent->leftchild()==pointer)
		parent->left=pointer->leftchild();
	else 
		parent->right=pointer->leftchild();
	delete pointer;
	pointer=NULL;
	return;
}

template <class T>
void BinarySearchTree<T>::DeleteNodeEx(BinaryTreeNode<T>* pointer)
{
	//如果帶刪除節點不存在,返回
	if( pointer == NULL )
		return;
	//保存要替換上來的節點
	BinaryTreeNode<T> * temppointer;
	//保存要替換上來的節點的父節點
	BinaryTreeNode<T> * tempparent = NULL;
	//保存要刪除節點的父節點
	BinaryTreeNode<T> * parent = GetParent(root ,pointer );

	//如果待刪除節點的左子樹為空,就將它的右子樹代替它即可
	if( pointer->leftchild() == NULL )
	{
		//將右子樹連到待刪除節點的父的合適位置
		if( parent == NULL )
			root = pointer->rightchild();
		else if( parent->leftchild() == pointer )
			parent->left = pointer->rightchild();
		else
			parent->right = pointer->rightchild();
		delete pointer;
		pointer=NULL;
		return;
	}

	//當待刪除節點左子樹不為空,就在左子樹中尋找最大節點替換待刪除節點
	temppointer = pointer->leftchild();
	while(temppointer->rightchild() != NULL )
	{
		tempparent = temppointer;
		temppointer = temppointer->rightchild();
	}

	//刪除替換結點
	if(tempparent==NULL)
		pointer->left=temppointer->leftchild();
	else
		tempparent->right=temppointer->leftchild();

	//用替換結點去替代真正的刪除結點
	if(parent==NULL)
		root=temppointer;
	else if( parent->leftchild() == pointer )
		     parent->left=temppointer;
		 else parent->right=temppointer;

	temppointer->left=pointer->leftchild();
	temppointer->right=pointer->rightchild();

	delete pointer;
	pointer=NULL;
	return;
}

#endif // !defined(AFX_BINARYSEARCHTREE_H__1CD2FF9D_73F2_4194_974A_12892DFB325F__INCLUDED_)