搜索二叉树的删除就复杂多了，会有下面四种情况：

1. 要删除结点N左右孩子均为空。
2. 要删除的结点N左孩子位空，右孩子结点不为空。
3. 要删除的结点N右孩子位空，左孩子结点不为空。
4. 要删除的结点N左右孩子结点均不为空。

 对应以上四种情况的解决⽅案：

1. 把N结点的父亲对应孩子指针指向空，直接删除N结点（情况1可以当成2或者3处理，效果是⼀样的）
2. 把N结点的父亲对应孩子指针指向N的右孩子，直接删除N结点
3. 把N结点的父亲对应孩子指针指向N的左孩子，直接删除N结点
4. 无法直接删除N结点，因为N的两个孩子无处安放，只能用替换法删除。找N左子树的值最大结点R(最右结点)或者N右子树的值最小结点R(最左结点)替代N，因为这两个结点中任意⼀个，放到N的位置，都满足⼆叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转而变成删除R结点，R结点符合情况2或情况3，可以直接删除。

注(4)：这里使用找N左子树的值最大结点R(最右结点)

bool Erase(const K& key)
{
	Node* cur = _root;
	Node* prev = nullptr;

	while(cur)
	{ 
		if (key < cur->_key)
		{
			prev = cur;
			cur = cur->_left;
		}
		else if (cur->_key < key)
		{
			prev = cur;
			cur = cur->_right;
		}
		else
		{
			//找到了
			//只有一边或没有子叶
			if (cur->_right == nullptr)
			{
				if (cur == _root)
				{
					_root = cur->_left;
				}
				else
				{
					if (prev->_right == cur)
					{
						prev->_right = cur->_left;
					}
					else
					{
						prev->_left = cur->_left;
					}
				}
				delete cur;

			}
			else if(cur->_left == nullptr)
			{
				if (cur == _root)
				{
					_root = cur->_right;
				}
				else
				{
					if (prev->_right == cur)
					{
						prev->_right = cur->_right;
					}
					else
					{
						prev->_left = cur->_right;
					}
				}
				delete cur;
			}
			else
			{
				//找到了有两个子叶
				Node* treep = cur;
				Node* treec = cur->_right;

				while (treec->_left)
				{
					treep = treec;
					treec = treec->_left;
				}

				cur->_key = treec->_key;


				if (treep->_left == treec)
					treep->_left = treec->_right;
				else
					treep->_right = treec->_right;
				delete treec;
			}
			return true;
		}
	}
	return false;
}