#ifndef BT_H_
#define BT_H_

//Concept BNode的要求,必須具有leftChild和rightChild節點域;

#include <algorithm>
#include <functional>
#include <list>
#include <string>


template <typename T>
struct BNode
{
	BNode();
	BNode(const T& elem);
	bool IsLeaf()
	{
		return leftChild == 0 && rightChild == 0;
	}
	int Height()
	{
		return ::Height(this);
	}

	BNode* leftChild;
	BNode* rightChild;
	T data;
};
template <typename T>
BNode<T>::BNode()
:leftChild(0), rightChild(0), data(T())
{
}

template <typename T>
BNode<T>::BNode(const T& elem)
:leftChild(0), rightChild(0), data(elem)
{
}

//刪除以root為根的樹;
template<class BNode>
void DestroyNode(BNode* root)
{
	if (root == 0)
		return;
	DestroyNode(root ->leftChild);
	DestroyNode(root ->rightChild);
	delete root;
}

template <class BNode>
int Height(BNode* node)
{
	if (node ->leftChild == 0 && node ->rightChild == 0)
		return 0;
	else
		return std::max(Height(node ->leftChild), Height(node ->rightChild)) + 1;
}

template <class BNode, class Functor>
void InOrderTravel(BNode* node, Functor f)
{
	if (node != 0)
	{
		InOrderTravel(node ->leftChild, f);
		f(node);
		InOrderTravel(node ->rightChild, f);
	}
}

template <class BNode, class Functor>
void PreOrderTravel(BNode* node, Functor f)
{
	if (node != 0)
	{
		f(node);
		PreOrderTravel(node ->leftChild, f);
		PreOrderTravel(node ->rightChild, f);
	}
}

template <class BNode, class Functor>
void PostOrderTravel(BNode node, Functor f)
{
	if (node != 0)
	{
		PostOrderTravel(node ->leftChild, f);
		PostOrderTravel(node ->rightChild, f);
		f(node);
	}
}

template <class BNode, class Functor>
void LevelOrderTravel(BNode* node, Functor f)
{
	std::list<BNode<T>*> list;

	while (node != 0)
	{
		f(node);

		if (node ->leftChild != 0)
			list.push_back(node ->leftChild);
		if (node ->rightChild != 0)
			list.push_back(node ->rightChild);

		if (list.empty())
			return;

		node = list.front();
		list.pop_front();
	}
}

template <typename T, class Node = BNode<T> >
class BinarySearchTree
{
public:
	BinarySearchTree();
	BinarySearchTree(const T a[], int length);
	~BinarySearchTree();

	void Insert(const T& elem);
	void Delete(const T& elem);
	T Exists(const T& elem);

	template <class Functor>
	void PostOrderTravel(Functor f);
	template <class Functor>
	void InOrderTravel(Functor f);
	template <class Functor>
	void PreOrderTravel(Functor f);
	template <class Functor>
	void LevelOrderTravel(Functor f);
	
private:
	Node* root;
private:
	virtual void Insert(Node* node);
};

template <typename T, class Node>
BinarySearchTree<T, Node>::BinarySearchTree()
:root(0)
{
}

template <typename T, class Node>
BinarySearchTree<T, Node>::BinarySearchTree(const T a[], int length)
{
	for (int i = 0; i < length; ++i)
	{
		Insert(a[i]);
	}
}
template <typename T, class Node>
BinarySearchTree<T, Node>::~BinarySearchTree()
{
	::DestroyNode(root);
}

template <typename T, class Node>
void BinarySearchTree<T, Node>::Delete(const T& elem)
{
	//temp保存欲刪除節點, parent為欲刪除節點之父節點;
	BNode<T>* temp = root;
	BNode<T>* parent = root;

	while (temp != 0)
	{
		if (elem < temp ->data)
		{
			parent = temp;
			temp = temp ->leftChild;
		}
		else if (elem > temp ->data)
		{
			parent = temp;
			temp = temp ->rightChild;
		}
		else
		{	//找到節點;

			//處理刪除節點具有雙子樹的情況,可以取右子樹的最小元填補或者左子樹的最大元填補;
			//這里取左子樹的最大元;
			if (temp ->leftChild != 0 && temp ->rightChild != 0)
			{
				BNode<T>* node = temp ->leftChild;
				BNode<T>* p    = temp;

				while (node ->rightChild != 0)
				{
					p = node;
					node = node ->rightChild;
				}

				temp ->data = node ->data;
				temp = node;
				parent = p;
			}

			//處理刪除節點具有單子樹的情況;
			//sub保存子樹指針;
			BNode<T>* sub;

			if (temp ->leftChild != 0)
				sub = temp ->leftChild;
			else
				sub = temp ->rightChild;

			//刪除節點為根的情況;
			if (temp == root)
				root = sub;
			else
			{
				if (temp == parent ->leftChild)
					parent ->leftChild = sub;
				else
					parent ->rightChild = sub;
				delete temp;
				return;
			}
		}
	}
}


template <typename T, class Node>
void BinarySearchTree<T, Node>::Insert(const T& elem)
{
	Insert(new Node(elem));
}

template <typename T, class Node>
void BinarySearchTree<T, Node>::Insert(Node* node)
{
	if (root == 0)
	{
		root = node;
		return;
	}

	BNode<T>* temp = root;
	BNode<T>* location = 0;

	while (temp != 0)
	{
		location = temp;

		if (node ->data > temp ->data)
		{
			if (temp ->rightChild == 0)
			{
				temp ->rightChild = node;
				return;
			}
			temp = temp ->rightChild;

		}
		else
		{
			if (temp ->leftChild == 0)
			{
				temp ->leftChild = node;;
				return;
			}
			temp = temp ->leftChild;
		}
	}
}
template <class T, class Node>
T BinarySearchTree<T, Node>::Exists(const T& elem)
{
	if (root == 0)
		return T();

	BNode<T>* temp = root;

	while (temp != 0)
	{
		if (elem == temp ->data)
			return temp ->data;

		if (elem > temp ->data)
		{
			temp = temp ->rightChild;
		}
		else
		{
			temp = temp ->leftChild;
		}
	}
	return T();
}


template <typename T, class Node>
template<class Functor>
void BinarySearchTree<T, Node>::InOrderTravel(Functor f)
{
	::InOrderTravel(root, f);
}

template<typename T, class Node>
template<class Functor>
void BinarySearchTree<T, Node>::PreOrderTravel(Functor f)
{
	::PreOrderTravel(root, f);
}

template<typename T, class Node>
template<class Functor>
void BinarySearchTree<T, Node>::PostOrderTravel(Functor f)
{
	::PostOrderTravel(root, f);
}

template<typename T, class Node>
template<class Functor>
void BinarySearchTree<T, Node>::LevelOrderTravel(Functor f)
{
	::LevelOrderTravel(root, f);
}

#endif