【C++高阶一】二叉搜索树

发布于：2025-05-27 ⋅ 阅读:(45) ⋅ 点赞:(0)

【C++高阶一】二叉搜索树剖析

1.什么是二叉搜索树

任何一个节点，他的左子树的所有节点都比他小，右子树的所有节点都比他大

在这里插入图片描述

二叉搜索树是有序的，中序遍历这棵二叉搜索树刚好是升序
时间复杂度为O(N)，因为会出现这种极端情况
在这里插入图片描述
二叉搜索树中不能出现值相同的节点

2.二叉搜索树非递归实现

大致框架

template<class K>
struct BSTreeNode //二叉搜索树节点
{
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;

	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};

template<class K>
class BSTree//二叉搜索树
{
	typedef BSTreeNode<K> Node;
public:

private:
	Node* _root = nullptr;
};

2.1插入

插入的值比根大就往右走，比根小就往左走，如果遇见和插入值相同的值就返回false

bool insert(const k& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(key);
		if (parent->_key > key)
		{
			parent->_left = cur;
		}
		else 
		{
			parent->_right = cur;
		}
		return true;
	}

parent保存每一步的父节点，在插入之后起到父子节点连接作用

2.2删除

2.2.1删除分析一

  1. 被删除节点无孩子：
    直接将此节点删除，不用做特殊处理
  2. 被删除节点只有左孩子：
    此节点被删除后，将此节点的左孩子连接到此节点的父亲节点
  3. 被删除节点只有右孩子：
    此节点被删除后，将此节点的右孩子连接到此节点的父亲节点
bool erase(const k& key)
{
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if(cur->_key > key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else//找到了
		{
			if (cur->_left == nullptr)//左孩子为空
			{
				if (cur == _root)
					_root = cur->_right;
				else
				{
					if (cur == parent->_right)
						parent->_right = cur->_right;
					else
						parent->_left = cur->_right;
				}
				delete cur;
			}
			else if (cur->_right == nullptr)//右孩子为空
			{
				if (cur == _root)
					_root = cur->_left;
				else
				{
					if (cur == parent->_right)
						parent->_right = cur->_left
					else
						parent->_left = cur->_left;
				}
				delete cur;
			}
			
			//第四种情况 
			//else{}

		}
	}
	return false；
}

表面只写了两种情况，其实已经把无孩子的情况包括了

2.2.2删除分析二

当被删除的节点存在左右孩子时，我们要使用替换法
被替换的节点一定要满足一个条件:
是左子树的最大值 || 是右子树的最小值
在这里插入图片描述

假设使用右子树中最小的节点来替换，其左孩子为空，但右孩子未知，还需要分情况讨论

else//左右孩子都不为空
{
	//用右子树最小值来替换
	Node* Temp_parent = cur;//临时父节点
	Node* R_subtree_min = cur->_right;//右子树最小值
	while (R_subtree_min->_left)
	{
		Temp_parent = R_subtree_min;
		R_subtree_min = R_subtree_min->_left;
	}

	swap(cur->_key, R_subtree_min->_key);

	if (R_subtree_min == Temp_parent->_left)
	{
		Temp_parent->_left = R_subtree_min->_right;
	}
	else
	{
		Temp_parent->_right = R_subtree_min->_right;
	}

	delete R_subtree_min;
}

2.3查找

bool find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		if (cur->_key > key)
		{
			cur = cur->_left;
		}
		else if (cur->_key < key)
		{
			cur = cur->_right;
		}
		else
		{
			return true;
		}
	}
	return false;
}

3.二叉搜索树递归实现

递归实现全都使用了函数嵌套的方式，是为了使用_root这个定义在类中的成员变量

3.1插入

插入的基本思路一样,但递归到空时构建新节点的链接有三种方式：
1.多传一个参数，记录父节点
2.递归到空节点的上一层，比如if(root->_left==NULL) 开始构建节点
3.传引用
前两个方法和循环写法没什么区别，下面都使用传引用

bool Re_insert(const K& key)
{
	return _Re_insert(_root, key);
}
	
bool _Re_insert(Node*& root, const K& key)
{
	if (root == nullptr)
	{
		root = new Node(key);
		return true;
	}

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

3.2删除

bool Re_erase(const K& key)
{
	return _Re_erase(_root, key);
}
bool _Re_erase(Node*& root, const K& key)
{
	if (root == nullptr)
		return false;

	if (root->_key > key)
	{
		return _Re_erase(root->_left, key);
	}
	else if (root->_key < key)
	{
		return _Re_erase(root->_right, key);
	}
	else//找到了，准备删除
	{
		if (root->_left == nullptr)//左孩子为空
		{
			Node* temp = root;
			root = root->_right;
			delete temp;

			return true;
		}
		else if (root->_right == nullptr)//右孩子为空
		{
			Node* temp = root;
			root = root->_left;
			delete temp;

			return true;
		}
		else//左右孩子都不为空
		{
			//找右子树的最小值
			Node* temp = root->_right;
			while (temp->_left)
			{
				temp = temp->_left;
			}
			swap(root->_key, temp->_key);

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

3.3查找

bool Re_find(const K& key)
{
	return _Re_find(_root, key);
}
private:
bool _Re_find(Node* root,const K& key)
{
	if (root == nullptr)
		return false;

	if (root->_key > kry)
	{
		return _Re_find(root->_left, key);
	}
	else if (root->_key < kry)
	{
		return _Re_find(root->_right, key);
	}
	else
	{
		return true;
	}
}

4.完整代码

template<class K>
struct BSTreeNode //二叉搜索树节点
{
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;

	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};

template<class K>
class BSTree//二叉搜索树
{
	typedef BSTreeNode<K> Node;
public:
	bool insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(key);
		if (parent->_key > key)
		{
			parent->_left = cur;
		}
		else 
		{
			parent->_right = cur;
		}
		return true;
	}

	bool erase(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if(cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else//找到了,准备删除
			{
				if (cur->_left == nullptr)//左孩子为空
				{
					if (cur == _root)
						_root = cur->_right;
					else
					{
						if (cur == parent->_right)
							parent->_right = cur->_right;
						else
							parent->_left = cur->_right;
					}
					delete cur;
					
				}
				else if (cur->_right == nullptr)//右孩子为空
				{
					if (cur == _root)
						_root = cur->_left;
					else
					{
						if (cur == parent->_right)
							parent->_right = cur->_left
						else
							parent->_left = cur->_left;
					}
					delete cur;
					
				}
				else//左右孩子都不为空
				{
					//用右子树最小值来替换
					Node* Temp_parent = cur;//临时父节点
					Node* R_subtree_min = cur->_right;//右子树最小值
					while (R_subtree_min->_left)
					{
						Temp_parent = R_subtree_min;
						R_subtree_min = R_subtree_min->_left;
					}

					swap(cur->_key, R_subtree_min->_key);

					if (R_subtree_min == Temp_parent->_left)
					{
						Temp_parent->_left = R_subtree_min->_right;
					}
					else
					{
						Temp_parent->_right = R_subtree_min->_right;
					}

					delete R_subtree_min;
				}
				return true;
			}
		}
		return false;
	}

	bool find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

	bool Re_insert(const K& key)
	{
		return _Re_insert(_root, key);
	}

	bool Re_erase(const K& key)
	{
		return _Re_erase(_root, key);
	}

	bool Re_find(const K& key)
	{
		return _Re_find(_root, key);
	}
private:
	bool _Re_insert(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}

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

	bool _Re_erase(Node*& root, const K& key)
	{
		if (root == nullptr)
			return false;

		if (root->_key > key)
		{
			return _Re_erase(root->_left, key);
		}
		else if (root->_key < key)
		{
			return _Re_erase(root->_right, key);
		}
		else//找到了，准备删除
		{
			if (root->_left == nullptr)//左孩子为空
			{
				Node* temp = root;
				root = root->_right;
				delete temp;

				return true;
			}
			else if (root->_right == nullptr)//右孩子为空
			{
				Node* temp = root;
				root = root->_left;
				delete temp;

				return true;
			}
			else//左右孩子都不为空
			{
				//找右子树的最小值
				Node* temp = root->_right;
				while (temp->_left)
				{
					temp = temp->_left;
				}
				swap(root->_key, temp->_key);

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

	bool _Re_find(Node* root,const K& key)
	{
		if (root == nullptr)
			return false;

		if (root->_key > kry)
		{
			return _Re_find(root->_left, key);
		}
		else if (root->_key < kry)
		{
			return _Re_find(root->_right, key);
		}
		else
		{
			return true;
		}
	}
private:
	Node* _root = nullptr;
};

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布