【C++进阶】二叉搜索树

【C++进阶】二叉搜索树

目录

 二叉搜索树的删除（较复杂）

Gitee代码：二叉搜索树

---

 二叉搜索树的删除（较复杂）

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

		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				// 删除
				if (cur->_left == nullptr)
				{
					if (cur == parent->_left)
					{
						parent->_left = cur->_right;
					}
					else
					{
						parent->_right = cur->_right;
					}

					delete cur;
				}
				else if (cur->_right == nullptr)
				{
					if (cur == parent->_left)
					{
						parent->_left = cur->_left;
					}
					else
					{
						parent->_right = cur->_left;
					}

					delete cur;
				}
				else
				{
					// 找到右树最小节点去替代删除
					Node* minRightParent = cur;
					Node* minRight = cur->_right;
					while (minRight->_left)
					{
						minRightParent = minRight;
						minRight = minRight->_left;
					}
					cur->_key = minRight->_key;

					if (minRight == minRightParent->_left)
						minRightParent->_left = minRight->_right;
					else
						minRightParent->_right = minRight->_right;

					delete minRight;
				}
				return true;
			}
		}
		return false;
	}

（较难）对于2个孩子的节点删除，用替代法删除法

上面代码的删除，如果全删除的话，会发现程序崩溃了——出现空指针

改进===> 

 ===>>>会发现不会崩溃

Gitee代码：二叉搜索树