#ifndef BINARY_SEARCH_TREE_HPP
#define BINARY_SEARCH_TREE_HPP

#include <iostream>
#include <cstdlib>

using namespace std;

template <class TKey, typename TValue>
class BstNode
{
protected:
	TKey key_;								// 关键字
	TValue value_;							// 值

	BstNode<TKey, TValue>* left_child_;		// 左孩子指针
	BstNode<TKey, TValue>* right_child_;	// 右孩子指针

public:
	BstNode() :left_child_(NULL), right_child_(NULL){}

	BstNode(TKey key, TValue value)
		:value_(value),key_(key),left_child_(NULL),right_child_(NULL){}

	BstNode(TKey key, TValue value, BstNode<TKey, TValue>* left_child, BstNode<TKey, TValue>* right_child)
		:value_(value), key_(key), left_child_(left_child), right_child_(right_child) {}

	BstNode<TKey, TValue>*& leftChild() { return this->left_child_; }

	void setLeftChild(BstNode<TKey, TValue>* node) { this->left_child_ = node; }

	BstNode<TKey, TValue>*& rightChild() { return this->right_child_; }

	void setRightChild(BstNode<TKey, TValue>* node) { this->right_child_ = node; }

	virtual TKey key() { return this->key_; }

	virtual void setKey(const TKey& key) { this->key_ = key; }

	virtual TValue value() { return this->value_; }

	virtual void setValue(const TValue& value) { this->value_ = value; }
};

// 二叉搜索树：同一根结点下，左子树数据值小于右子树数据值（递归定义）
template <class TKey, class TValue>
class BinarySearchTree
{
protected:
	BstNode<TKey, TValue>* root_;	// 根结点

	// 子树插入结点（递归）
	bool insertInSubTree_(TKey key, TValue value, BstNode<TKey,TValue>*& subtree_root);

	// 子树删除结点（递归）
	bool removeInSubTree_(BstNode<TKey,TValue>*& subtree_root, TKey key);

	// 子树搜索（递归）
	BstNode<TKey, TValue>* searchInSubTree_(BstNode<TKey,TValue>* subtree_root,TKey key);

	// 子树高度
	int heightOfSubTreeRecursive_(BstNode<TKey,TValue>* subtree_root);

	// 子树清空（递归）
	void clearSubTree_(BstNode<TKey,TValue>*& subtree_root);

	// 子树打印（递归）
	void printSubTreeRecursive_(BstNode<TKey,TValue>* subtree_root,void (*nodePrint)(BstNode<TKey,TValue>*)) const;

	// 子树复制（递归）
	BstNode<TKey, TValue>* copySubTreeRecursive_(const BstNode<TKey,TValue>* src_bst_root);

	// 子树中关键码最小项
	BstNode<TKey, TValue>* minInSubTree_(BstNode<TKey,TValue>* subtree_root) const;

	// 子树中关键码最大项
	BstNode<TKey, TValue>* maxInSubTree_(BstNode<TKey,TValue>* subtree_root) const;

	// 获取结点的中序后继结点（找右子树的最左侧结点）
	BstNode<TKey, TValue>* nextNode_(BstNode<TKey,TValue>* node);

public:
	BinarySearchTree():root_(NULL){}

	BinarySearchTree(TKey key, TValue value) { this->insertInSubTree_(key,value); }

	// 虚析构函数就是用来解决通过父类指针释放子类对象
	virtual ~BinarySearchTree() { delete this->root_; }

	virtual bool insertRecursive(TKey key, TValue value) { return this->insertInSubTree_(key, value, this->root_); }

	virtual bool removeRecursive(const TKey& key) { return this->removeInSubTree_(this->root_,key); }
	
	// 父类的virtual方法不一定要被子类重写。子类可以选择重写该方法，也可以不重写。如果子类不重写这个virtual方法，那么当使用父类的指针或引用来调用这个方法时，会调用父类中的版本。
	/// <summary>
	/// 二叉树搜索给定key值的结点
	/// </summary>
	/// <param name="key">给定的key值</param>
	/// <returns>找到的结点</returns>
	virtual BstNode<TKey, TValue>* search(TKey key) { return this->searchInSubTree_(this->root_,key); }

	/// <summary>
	/// 获取树高
	/// </summary>
	/// <returns>树的高度</returns>
	virtual int height() { return this->heightOfSubTreeRecursive_(this->root_); }

	// 获取最小关键字对应的值
	virtual bool min(TValue& min_value);

	// 获取最大关键字对应的值
	virtual bool max(TValue& max_value);

	// 获取根结点
	BstNode<TKey, TValue>*& root() { return this->root_; }

	// 清空树
	virtual void clear() { this->clearSubTree_(this->root_); }

	// 中序序列打印结点序列
	void print(void (*nodePrint)(BstNode<TKey, TValue>*)) { this->printSubTreeRecursive_(this->root_, nodePrint); }

	// 重载=，赋值函数
	// 1使用 "已存在的对象 A" 对 另外一个"已存在对象 B" 赋值 , B = A ,
	// 2左操作数 B 是 this 指针;
	// 3参数 BinarySearchTree<TKey,TValue>& src_bst 是 右操作数;
	// 4返回 BinarySearchTree<TKey,TValue>& 的原因是 等号 = 操作符是 右结合 的, C = B = A 的情况, 需要返回类对象, 并支持链式操作;
	BinarySearchTree<TKey, TValue>& operator=(const BinarySearchTree<TKey,TValue>& src_bst);
};

#endif // !BINARY_SEARCH_TREE_HPP

template<class TKey, class TValue>
inline bool BinarySearchTree<TKey, TValue>::insertInSubTree_(TKey key, TValue value, BstNode<TKey, TValue>*& subtree_root)
{
	// 空子树插入
	if (subtree_root == NULL)
	{
		subtree_root = new BstNode<TKey, TValue>(key, value);
		if (!subtree_root)
			throw bad_alloc();

		return true;
	}

	// 分治递归
	if (key < subtree_root->key())
		return this->insertInSubTree_(key,value,subtree_root->leftChild());

	if (key > subtree_root->key())
		return this->insertInSubTree_(key,value,subtree_root->rightChild());

	// 返回
	return false;
}

template<class TKey, class TValue>
inline bool BinarySearchTree<TKey, TValue>::removeInSubTree_(BstNode<TKey, TValue>*& subtree_root, TKey key)
{
	// 空子树处理
	if (subtree_root == NULL)
		return false;

	// 执行递归
	if (key < subtree_root->key())
		return this->removeInSubTree_(subtree_root->leftChild(),key);

	if (key > subtree_root->key())
		return this->removeInSubTree_(subtree_root->rightChild(),key);

	// 走过两个if语句之后，就代表着key == subtree_root->key_
	// 接下来处理待删除结点为子树根结点的情况
	if (subtree_root->leftChild() != NULL && subtree_root->rightChild() != NULL)
	{
		// 初始化next_node, 指向根结点中序的下一个结点(在右子树内), 作为替换结点
		BstNode<TKey, TValue>* next_node = this->nextNode_(subtree_root);

		subtree_root->setValue(next_node->value());
		subtree_root->setKey(next_node->key());

		// next_node可能是叶子节点，也可能是非叶节点
		return this->removeInSubTree_(subtree_root->rightChild(),next_node->key());
	}
	else
	{
		BstNode<TKey, TValue>* remove_node = subtree_root;
		if (subtree_root->leftChild() == NULL)
			subtree_root = subtree_root->rightChild();
		else // 左子树不为空
			subtree_root = subtree_root->leftChild();

		delete remove_node;
		remove_node = NULL;

		return true;
	}
}

template<class TKey, class TValue>
inline BstNode<TKey, TValue>* BinarySearchTree<TKey, TValue>::searchInSubTree_(BstNode<TKey, TValue>* subtree_root, TKey key)
{
	// 空子树处理
	if (subtree_root == NULL)
		return NULL;

	// 分治递归
	TKey subtree_root_key = subtree_root->key();

	if (key < subtree_root_key)
		return this->searchInSubTree_(subtree_root->leftChild(), key);
	else if (key > subtree_root_key)
		return this->searchInSubTree_(subtree_root->rightChild(),key);

	return subtree_root;
}

template<class TKey, class TValue>
inline int BinarySearchTree<TKey, TValue>::heightOfSubTreeRecursive_(BstNode<TKey, TValue>* subtree_root)
{
	// 空树处理
	if (!subtree_root)
		return 0;

	// 分治递归
	int left_subtree_height = this->heightOfSubTreeRecursive_(subtree_root->leftChild());
	int right_subtree_height = this->heightOfSubTreeRecursive_(subtree_root->rightChild());
	
	if (left_subtree_height < right_subtree_height)
		return right_subtree_height + 1;
	else
		return left_subtree_height + 1;
}

template<class TKey, class TValue>
inline void BinarySearchTree<TKey, TValue>::clearSubTree_(BstNode<TKey, TValue>*& subtree_root)
{
	// 空树处理
	if (subtree_root == NULL)
		return;

	// 分治递归
	this->clearSubTree_(subtree_root->leftChild());
	this->clearSubTree_(subtree_root->rightChild());

	// 重置根结点
	delete subtree_root;
	subtree_root = NULL;
}

template<class TKey, class TValue>
inline void BinarySearchTree<TKey, TValue>::printSubTreeRecursive_(BstNode<TKey, TValue>* subtree_root, void(*nodePrint)(BstNode<TKey, TValue>*)) const
{
	// 空树处理
	if (subtree_root == NULL)
		return;

	// 分治递归
	nodePrint(subtree_root);

	// subtree_root指向叶子节点
	if (subtree_root->leftChild() == NULL && subtree_root->rightChild() == NULL)
	{
		return;
	}

	cout << "(";

	if (subtree_root->leftChild() != NULL)
		this->printSubTreeRecursive_(subtree_root->leftChild(), nodePrint);
	else
		cout << "nullptr";

	cout << ",";
	
	if (subtree_root->rightChild() != NULL)
		this->printSubTreeRecursive_(subtree_root->rightChild(), nodePrint);
	else
		cout << "nullptr";

	cout << ")";
}

template<class TKey, class TValue>
inline BstNode<TKey, TValue>* BinarySearchTree<TKey, TValue>::copySubTreeRecursive_(const BstNode<TKey, TValue>* src_bst_root)
{
	// 源子树空树处理
	if (src_bst_root == NULL)
		return NULL;

	// 生成新树根结点，堆区申请，可以被函数返回
	BstNode<TKey, TValue>* new_bst_root = new BstNode<TKey, TValue>(src_bst_root->value_,src_bst_root->key_);

	if (new_bst_root == NULL)
		throw bad_alloc();

	// 左右子树分治递归复制
	new_bst_root->setLeftChild(this->copySubTreeRecursive_(src_bst_root->left_child_));
	new_bst_root->setRightChild(this->copySubTreeRecursive_(src_bst_root->right_child_));

	// 返回树根
	return new_bst_root;
}

template<class TKey, class TValue>
inline BstNode<TKey, TValue>* BinarySearchTree<TKey, TValue>::minInSubTree_(BstNode<TKey, TValue>* subtree_root) const
{
	// 空子树处理
	if (subtree_root == NULL)
		return NULL;

	//  一直向左遍历
	BstNode<TKey, TValue>* cur = subtree_root;

	while (cur && cur->leftChild() != NULL)
	{
		cur = cur->leftChild();
	}

	// 返回结果
	return cur;
}

template<class TKey, class TValue>
inline BstNode<TKey, TValue>* BinarySearchTree<TKey, TValue>::maxInSubTree_(BstNode<TKey, TValue>* subtree_root) const
{
	if (subtree_root == NULL)
		return NULL;
	
	BstNode<TKey, TValue>* cur = subtree_root;

	while (cur && cur->rightChild() != NULL)
	{
		cur = cur->rightChild();
	}

	return cur;
}

template<class TKey, class TValue>
inline BstNode<TKey, TValue>* BinarySearchTree<TKey, TValue>::nextNode_(BstNode<TKey, TValue>* node)
{
	// 合法性判断
	if (!node)
		return NULL;

	// 查找结点
	BstNode<TKey, TValue>* cur = node->rightChild();

	while (cur && cur->leftChild() != NULL)
	{
		cur = cur->leftChild();
	}

	// 退出函数
	return cur;
}

template<class TKey, class TValue>
inline bool BinarySearchTree<TKey, TValue>::min(TValue& min_value)
{
	BstNode<TKey, TValue>* node = this->minInSubTree_(this->root_);

	if (!node)
		return false;

	min_value = node->value();
	
	return true;
}

template<class TKey, class TValue>
inline bool BinarySearchTree<TKey, TValue>::max(TValue& max_value)
{
	BstNode<TKey, TValue>* node = this->maxInSubTree_(this->root_);

	if (!node)
		return false;

	max_value = node->value();

	return true;
}

template<class TKey, class TValue>
inline BinarySearchTree<TKey, TValue>& BinarySearchTree<TKey, TValue>::operator=(const BinarySearchTree<TKey, TValue>& src_bst)
{
	// 复制自身处理
	if (&src_bst == this)
		return *this;

	// 复制
	this->root_ = this->copySubTreeRecursive_(src_bst.root_);

	// 退出函数
	return *this;
}