#pragma once

template<class T>
struct BSTNode
{
	BSTNode<T>* _left;
	BSTNode<T>* _right;
	T _value;

	BSTNode(const T& value = T())
		: _left(nullptr)
		, _right(nullptr)
		, _value(value)
	{}
};


// value唯一
template<class T>
class BSTree
{
	typedef BSTNode<T> Node;
public:
	BSTree()
		: _root(nullptr)
	{}

	~BSTree()
	{
		DestroyBST(_root);
	}

	Node* Insert(const T& value)
	{
		// 1. 空树，直接插入并返回
		if (nullptr == _root)
		{
			_root = new Node(value);
			return _root;
		}

		// 2. 非空：
        
		//   a. 找带入元素在BST中的位置,并保存其双亲
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			parent = cur;
			if (value < cur->_value)
				cur = cur->_left;
			else if (value > cur->_value)
				cur = cur->_right;
			else
				return cur;
		}
		//   b. 插入新节点
		cur = new Node(value);
		if (value < parent->_value)
			parent->_left = cur;
		else
			parent->_right = cur;

		return cur;
	}

	bool Erase(const T& value)
	{
		if (nullptr == _root)
			return false;

		// 1. 找待删除节点在BST中的位置，并保存其双亲
		Node* delNode = _root;
		Node* parent = nullptr;
		while (delNode)
		{
			if (delNode->_value == value)
				break;
			else if (value < delNode->_value)
			{
				parent = delNode;
				delNode = delNode->_left;
			}
			else
			{
				parent = delNode;
				delNode = delNode->_right;
			}
		}

		// value不存在
		if (nullptr == delNode)
			return false;

		// 2. 删除delNode
		if (nullptr == delNode->_right)
		{
			// 叶子节点 || 只有左孩子
			if (nullptr == parent)
			{
				// delNode就是根节点
				_root = delNode->_left;
			}
			else
			{
				if (delNode == parent->_left)
					parent->_left = delNode->_left;
				else
					parent->_right = delNode->_left;
			}
		}
		else if (nullptr == delNode->_left)
		{
			// 只有右孩子
			if (nullptr == parent)
			{
				// delNode是根节点
				_root = delNode->_right;
			}
			else
			{
				// delNode只有右孩子
				if (parent->_left == delNode)
					parent->_left = delNode->_right;
				else
					parent->_right = delNode->_right;
			}
		}
		else
		{
			// 左右孩子都存在
			// 1. 找替代节点---并记录其双亲
			parent = delNode;
			Node* firstInOrder = delNode->_right;
			while (firstInOrder->_left)
			{
				parent = firstInOrder;
				firstInOrder = firstInOrder->_left;
			}

			// 2. 将替代节点中的值域赋值给待删除节点
			delNode->_value = firstInOrder->_value;

			// 3. 删除替代节点
			if (firstInOrder == parent->_left)
				parent->_left = firstInOrder->_right;
			else
				parent->_right = firstInOrder->_right;
			delNode = firstInOrder;
		}

		delete delNode;
		return true;
	}

	Node* Find(const T& value)
	{
		Node* cur = _root;
		while (cur)
		{
			if (value == cur->_value)
				return cur;
			else if (value < cur->_value)
				cur = cur->_left;
			else
				cur = cur->_right;
		}

		return nullptr;
	}

	void InOrder()
	{
		InOrder(_root);
		cout << endl;
	}

private:
	void DestroyBST(Node*& root)
	{
		if (root)
		{
			DestroyBST(root->_left);
			DestroyBST(root->_right);
			delete root;
			root = nullptr;
		}
	}

	void InOrder(Node* root)
	{
		if (root)
		{
			InOrder(root->_left);
			cout << root->_value << " ";
			InOrder(root->_right);
		}
	}
private:
	Node* _root;
};