二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树（英语：ordered binary tree），排序二叉树（英语：sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

• 任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

• 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

• 任意节点的左、右子树也分别为二叉查找树；

• 没有键值相等的节点。

#pragma once

template
struct BSTreeNode
{
	K _key;
	V _value;
	BSTreeNode* _left;
	BSTreeNode* _right;

	BSTreeNode(const K& key, const V& value)
		:_key(key)
		,_value(value)
		,_left(NULL)
		,_right(NULL)
	{}
};

template
class BSTree
{
	typedef BSTreeNode Node;
public:
	BSTree()
		:_root(NULL)
	{}

	bool Insert(const K& key, const V& value)
	{
		if (NULL == _root)//若为空树
		{
			_root = new Node(key, value);
			return true;
		}

		Node* parent = NULL;
		Node* cur = _root;

		//确定插入节点的位置
		while (cur)
		{
			if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else//已经存在key
			{
				return false;
			}
		}

		//插入节点
		if (key > parent->_key)
			parent->_right = new Node(key, value);
		else
			parent->_left = new Node(key, value);
	}

	//Insert递归写法
	bool InsertR(const K& key, const V& value)
	{
		return _InsertR(_root, key, value);
	}

	bool _InsertR(Node*& root, const K& key, const V& value)
	{
		if (NULL == root)
		{
			root = new Node(key, value);
			return true;
		}

		if (key > root->_key)
			return _InsertR(root->_right, key, value);
		else if (key < root->_key)
			return _InsertR(root->_left, key, value);
		else
			return false;
	}

	Node* Find(const K& key)
	{
		Node* cur = _root;

		while (cur)
		{
			if (key > cur->_key)
				cur = cur->_right;
			else if (key < cur->_key)
				cur = cur->_left;
			else
				return cur;
		}

		return NULL;
	}

	//Find递归写法
	Node* FindR(const K& key)
	{
		return _FindR(_root, key);
	}

	Node* _FindR(Node* root, const K& key)
	{
		if (NULL == root)
			return NULL;

		if (key > root->_key)
			return _FindR(root->_right, key);
		else if (key < root->_key)
			return _FindR(root->_left, key);
		else
			return root;
	}

	bool Remove(const K& key)
	{
		Node* parent = NULL;
		Node* cur = _root;

		//确定删除节点的位置
		while (cur)
		{
			if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				break;
			}
		}

		if (NULL == cur)//没有该节点
		{
			return false;
		}

		Node* del;
		if (NULL == cur->_left)//删除节点的左孩子为空
		{
			del = cur;

			//删除的节点为根节点
			if (NULL == parent)
			{
				_root = _root->_right;
			}
			else
			{
				if (cur == parent->_left)
					parent->_left = cur->_right;
				else
					parent->_right = cur->_right;
			}
		}
		else if (NULL == cur->_right)//删除节点的右孩子为空
		{
			del = cur;

			if (NULL == parent)
			{
				_root = _root->_left;
			}
			else
			{
				if (cur == parent->_left)
					parent->_left = cur->_right;
				else
					parent->_right = cur->_left;
			}
		}
		else//删除节点的左右孩子都不为空，找右子树最左节点代替该节点删除
		{
			parent = cur;

			Node* leftmost = cur->_right;
			while (leftmost->_left)
			{
				parent = leftmost;
				leftmost = leftmost->_left;
			}

			del = leftmost;

			cur->_key = leftmost->_key;
			cur->_value = leftmost->_value;

			if (leftmost == parent->_left)
				parent->_left = leftmost->_right;
			else
				parent->_right = leftmost->_right;
		}

		return true;
	}

	//Remove递归写法
	bool RemoveR(const K& key)
	{
		return _RemoveR(_root, key);
	}
	
	bool _RemoveR(Node*& root, const K& key)
	{
		if (NULL == root)
			return false;
		
		if (key > root->_key)
		{
			return _RemoveR(root->_right, key);
		}
		else if (key < root->_key)
		{
			return _RemoveR(root->_left, key);
		}
		else
		{
			Node* del = root;

			if (NULL == root->_left)
			{
				root = root->_right;
			}
			else if (NULL == root->_right)
			{
				root = root->_left;
			}
			else
			{
				Node* leftmost = root->_right;
				while (leftmost->_left)
				{
					leftmost = leftmost->_left;
				}

				swap(root->_key, leftmost->_key);
				swap(root->_value, leftmost->_value);

				return _RemoveR(root->_right, key);
			}

			delete del;
		}

		return true;
	}

	//中序遍历递归写法
	void InOrder()
	{
		_InOrder(_root);
	}

	void _InOrder(Node* root)
	{
		if (NULL == root)
			return;

		_InOrder(root->_left);
		cout<_key<<" ";
		_InOrder(root->_right);
	}

protected:
	Node* _root;
};


void Test()
{
	BSTree t;
	int a[] = {5, 3, 4, 1, 7, 8, 2, 6, 0, 9};
	for (size_t i = 0; i < sizeof(a)/sizeof(a[0]);++i)
	{
		t.InsertR(a[i], i);
	}

	cout<_key<_key<_key<