今天你学C++了吗？——二叉搜索树

发布于：2025-03-23 ⋅ 阅读:(21) ⋅ 点赞:(0)

♥♥♥~~~~~~欢迎光临知星小度博客空间~~~~~~♥♥♥

♥♥♥零星地变得优秀~也能拼凑出星河~♥♥♥

♥♥♥我们一起努力成为更好的自己~♥♥♥

♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥

♥♥♥如果有什么问题可以评论区留言或者私信我哦~♥♥♥

✨✨✨✨✨✨ 个人主页✨✨✨✨✨✨

这篇博客，我们将开始一个不太一样的数据结构——二叉搜索，树准备好了吗~我们发车去探索C++的奥秘啦~🚗🚗🚗🚗🚗🚗

目录

什么是二叉搜索树？

二叉搜索树的效率问题

如何定义一个二叉搜索树？

二叉搜索树的插入

插入过程

代码实现

测试

二叉搜索树的中序遍历打印

二叉搜索树的查找

查找过程

代码实现

测试

二叉搜索树的删除

删除过程

代码实现

测试

二叉搜索树的析构

什么是二叉搜索树？

二叉搜索树是一种特殊的树形数据结构，它看起来像一棵普通的树，但每个节点都有一些特定的规则：

  1. 根节点：这是树的起点，所有的节点都是从这里开始生长的（当然，如果树是空的，那就没有根节点了）。

  2. 左子树和右子树：每个节点都可以有左子树和右子树。就像人的左手和右手一样，左子树在节点的左边，右子树在节点的右边。

  3. 排序规则：

    • 如果左子树存在，那么左子树上的所有节点的值都比根节点的值要小或者相等（但通常在标准的二叉搜索树中，我们约定左子树上的值都严格小于根节点的值）。
    • 如果右子树存在，那么右子树上的所有节点的值都比根节点的值要大或者相等（同样地，在标准的二叉搜索树中，我们约定右子树上的值都严格大于根节点的值）。

  4. 递归规则：这个规则不仅适用于根节点，还适用于根节点的所有子节点，以及子节点的子节点，以此类推。也就是说，每一棵左子树和右子树也都要满足二叉搜索树的定义。

  5. 相等的值：对于二叉搜索树来说，是否允许插入相等的值取决于具体的实现。有些实现允许，有些则不允许。

现在，让我们来看看一些常见的容器，它们底层就是用了二叉搜索树来实现：

  • map和set：这两个容器不允许插入相等的值。也就是说，如果你试图在map中插入一个已经存在的键值对，或者在set中插入一个已经存在的值，那么插入操作会失败或者覆盖原来的值（取决于具体的实现）。

  • multimap和multiset：这两个容器则允许插入相等的值。也就是说，你可以在同一个multimap中有多个相同的键，也可以在同一个multiset中有多个相同的值。

比如下面这棵树就是二叉搜索树：

同时，我们也可以发现二叉搜索树中序遍历的结果是有序的，这里是升序~这也就是二叉搜索树的奇妙之处~

二叉搜索树的效率问题

       在最优情况下，二叉搜索树呈现为完全二叉树（或接近完全二叉树）的形态，此时其高度为 log₂N，时间复杂度也就是二叉树的高度log₂N，这使得搜索、插入和删除操作都能达到较高的效率。

       但是，在最差情况下，二叉搜索树可能会退化为单支树（或类似单支的形态），此时其高度达到 N，导致这些操作的时间复杂度激增到 O(N)

因此，综合来看，二叉搜索树在增删查改方面的平均时间复杂度可能并不理想。为了满足我们对高效数据存储和搜索的需求，我们需要进一步探索二叉搜索树的变形，如平衡二叉搜索树中的 AVL 树和红黑树，这些平衡树能够在保持 O(log₂N) 级别查找效率的同时，有效避免树的高度过高（在后面的博客中，我们会进行讲解）

另外值得一提的是，我们以前说到的二分查找算法虽然也能实现 O(log₂N) 级别的查找效率，但它存在两大局限性：首先，二分查找需要数据存储在支持下标随机访问的结构中，并且数据必须是有序的；其次，由于数据存储在固定位置，插入和删除操作通常需要移动大量数据，导致效率极低。

这就凸显了平衡二叉搜索树的价值所在。它们不仅保持了二分查找的高效查找效率，还通过动态调整树的结构来确保插入和删除操作的高效性，因此，平衡二叉搜索树在实际应用中具有更广泛的适用性~

如何定义一个二叉搜索树？

知道了二叉搜索树的概念以及它的效率问题，接下来我们来看看一个怎么定义一个二叉搜索树呢？

结合前面数据结构的经验，定义一个二叉搜索树我们首先需要定义它的结点，一个个结点才可以组成我们想要的二叉搜索树~

根据二叉搜索树的概念，我们可以知道二叉搜索树的结点应该保存三个数据：

1、当前结点保存的数据

2、当前结点的左子树地址

3、当前结点的右子树地址

知道了这样一个概念，我们定义一个二叉搜索树的结点就手到擒来了~

template<class T>
struct BSTreeNode//定义一个树结点
{
	T _key;
	BSTreeNode<T>* _left;
	BSTreeNode<T>* _right;
}

这里我们还使用了模板参数定义一个泛型模板结构体BSTreeNode，专为构建二叉搜索树（BST）的节点而设计。通过模板参数T，该结构体能够灵活地存储各种数据类型。每个BSTreeNode节点包含一个键值（_key），其类型为T，以及两个指针（_left和_right），分别指向其左子节点和右子节点。

通过前面C++的学习，我们知道struct关键字也是在定义一个类，所以我们这里也可以写一个我们想要的构造函数~

template<class T>
struct BSTreeNode//定义一个树结点
{
	T _key;
	BSTreeNode<T>* _left;
	BSTreeNode<T>* _right;

	BSTreeNode(const T& key)//构造
		:_key(key),
		_left(nullptr),
		_right(nullptr)
	{

	}
}

这样一个完整的结点定义就完成了~使用一个个的结点将他们联系起来，我们就可以实现一个二叉搜索树~

我们这里还需要给一个二叉搜索树的操作实现，私有成员为我们的根节点~接下来的结点就可以一个个链接起来了~

//二叉搜索树的实现
template<class T>
class BSTree
{
	typedef BSTreeNode<T> Node;
private:
	//根节点
	Node* _root = nullptr;
public:
	
};

二叉搜索树的插入

对于二叉搜索树的插入，我们需要进行一下情况讨论~

插入过程

  1. 树为空的情况：
    • 如果树是空的（即没有节点），那么直接创建一个新的节点，并将其赋值给 root 指针。此时，这个新节点就是整棵树的根节点。
  2. 树不空的情况：
    • 如果树不为空，那么根据二叉搜索树的性质，从根节点开始比较要插入的值与当前节点的值：
      • 如果插入的值比当前节点的值大，那么应该向右子树移动（即递归地检查当前节点的右子节点）。
      • 如果插入的值比当前节点的值小，那么应该向左子树移动（即递归地检查当前节点的左子节点）。
    • 重复这个过程，直到找到一个空位置（即没有左子节点也没有右子节点的节点位置），然后将新节点插入到这个空位置上。
  3. 支持插入相等值的情况：
    • 如果二叉搜索树的设计允许插入值相等的节点，那么当插入的值与当前节点的值相等时，可以选择向右子树移动或向左子树移动来寻找空位置插入新节点。
    • 重要的是，无论选择向左还是向右移动，要保持逻辑一致性。也就是说，对于相等的值，不应该有时选择向右移动，有时又选择向左移动。这通常通过设计算法时明确指定策略来实现，比如总是选择向右移动或者总是选择向左移动。

代码实现

我们这里实现一个不支持插入相等数据的二叉搜索树~

//二叉搜索树的实现
template<class T>
class BSTree
{
	typedef BSTreeNode<T> Node;
private:
	//根节点
	Node* _root = nullptr;
public:
	bool insert(const T& key)
	{
		//判断数是否为空
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		Node* parent = nullptr;
		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
				//如果相等就不进行插入
			{
				return false;
			}
		}
		//cur 已经走到为空
		cur = new Node(key);
		//与自己的父节点进行比较
		if (key > parent->_key)
		{
			parent->_right = cur;
		}
		else if (key < parent->key)
		{
			parent->_left = cur;
		}
		return true;
	}
};

测试

接下来，对我们上面的代码进行测试

通过测试我们也就可以看到，完成了二叉搜索树的插入操作~

二叉搜索树的中序遍历打印

前面我们提到了二叉搜索树中序遍历结果是有序的，这里我们就写一段代码进行中序遍历二叉搜索树，看看是不是我们想要的效果~这里我们使用递归打印来进行实现~

void _InPrint(Node* root)
{
	if (root == nullptr)
	{
		return;
	}
	_InPrint(root->_left);
	cout << root->_key << " ";
	_InPrint(root->_right);
}

这里需要一个参数root，我们知道根节点是我们的私有成员，我们也不希望外部访问我们的根节点，所以我们这里还需要使用一个函数进行包装一下~

void InPrint()
{
	_InPrint(_root);
	cout << endl;
}
void _InPrint(Node* root)
{
	if (root == nullptr)
	{
		return;
	}
	_InPrint(root->_left);
	cout << root->_key << " ";
	_InPrint(root->_right);
}

果不其然，结果就是我们以前推测的结果~这也就进一步验证二叉搜索树中序遍历结果是有序的~

二叉搜索树的查找

我们应该怎么进行查找呢？别急，我们一起来看看~

查找过程

  1. 从根开始比较：
    • 查找操作从树的根节点开始，将待查找的值 x 与根节点的值进行比较。
  2. 根据比较结果决定搜索方向：
    • 如果 x 大于根节点的值，则继续在根节点的右子树中查找 x。
    • 如果 x 小于根节点的值，则继续在根节点的左子树中查找 x。
    • 这个过程会递归地进行，直到找到值等于 x 的节点，或者到达一个空节点（意味着树中没有值等于 x 的节点）。
  3. 查找次数与树的高度有关：
    • 在最坏情况下，查找操作可能需要遍历树的高度次数的节点（从根到叶节点的最长路径）。
    • 如果遍历到空节点还没有找到 x，则说明树中不存在值等于 x 的节点。
  4. 处理相等值的情况：
    • 如果二叉搜索树不支持插入相等的值，那么一旦找到值等于 x 的节点，就可以立即返回该节点。
    • 如果二叉搜索树支持插入相等的值，那么树中可能有多个值等于 x 的节点。在这种情况下，通常要求查找中序遍历中的第一个（或根据具体需求可能是最后一个）值等于 x 的节点。（中序遍历会按照升序访问树中的所有节点，因此，在中序遍历中遇到的第一个值等于 x 的节点将是所有值等于 x 的节点中最左边的一个）

代码实现

Node* Find(const T& x)
{
	if (_root == nullptr)
	{
		return nullptr;
	}
	Node* cur = _root;
	//遍历查找
	while (cur)
	{
		if (x < cur->_key)
			//如果比当前节点数小，说明在当前节点的左子树
		{
			cur = cur->_left;
		}
		else if (x > cur->_key)
			//如果比当前节点数大，说明在当前节点的右子树
		{
			cur = cur->_right;
		}
		else
			//如果相等就找到了
		{
			return cur;
		}
	}
	//走到空也没有找到
	return nullptr;
}

测试

二叉搜索树的删除

删除过程

  1. 查找元素：
    • 首先，在二叉搜索树中查找要删除的元素。
    • 如果元素不存在于树中，则返回false，表示删除操作失败。
  2. 元素存在时的处理：
    • 如果元素存在于树中，则根据要删除的节点N的子节点情况，采取不同的删除策略。
  3. 四种子节点情况：
    • 情况1：节点N没有左子节点也没有右子节点（叶子节点）。
    • 情况2：节点N有右子节点但没有左子节点。
    • 情况3：节点N有左子节点但没有右子节点。
    • 情况4：节点N既有左子节点也有右子节点。
  4. 对应的解决方案：
    • 情况1：可以直接删除节点N，将其父节点的对应子节点指针设为null。这种情况也可以视为情况2或情况3的特例，效果相同。
    • 情况2：将节点N的父节点的对应子节点指针指向N的右子节点，然后删除N。
    • 情况3：将节点N的父节点的对应子节点指针指向N的左子节点，然后删除N。
    • 情况4：不能直接删除节点N，因为N的两个子节点无法直接安置。此时，需要找到N的左子树中的最大值节点R（即最右节点）或N的右子树中的最小值节点R（即最左节点），用R的值替换N的值，然后将问题转化为删除R节点（此时R节点符合情况2或情况3），可以直接删除。
  5. 替换法的详细解释：
    • 在情况4中，由于直接删除N会破坏二叉搜索树的性质，因此需要找到N的一个“替代者”。
    • 这个替代者可以是N左子树中的最大值节点（即左子树中最右边的节点），也可以是N右子树中的最小值节点（即右子树中最左边的节点）。
    • 这两个节点中的任何一个，放到N的位置，都能保持二叉搜索树的性质不变。
    • 替换操作实际上是交换N和R的值，然后删除R节点（此时R节点变成了叶子节点、只有右子节点或只有左子节点的情况，可以直接删除）。

通过这个过程，可以在保持二叉搜索树性质的前提下，有效地删除树中的任意节点~我们这里需要特别注意的是情况4使用替换方法这一种巧妙方式~

代码实现

代码1：

bool erase(const T& key)
{
	//处理根节点为空的情况
	if (_root == nullptr)
	{
		exit(1);
	}
	//遍历查找元素
	Node* cur = _root;
	Node* parent = _root;
	while (cur)
	{
		if (key < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			break;
		}
	}
	//如果找到空，说明没有相应结点
	if (cur == nullptr)
		return false;
	//分情况处理
	//1、节点cur没有左子节点也没有右子节点
	if (cur->_left == nullptr && cur->_right == nullptr)
	{
		//相应的父节点的子节点置为空
		if (cur->_key > parent->_key)
		{
			parent->_right = nullptr;
		}
		else if (cur->_key < parent->_key)
		{
			parent->_left = nullptr;
		}
		delete cur;
		return true;
	}
	//2、节点cur有右子节点但没有左子节点
	else if (cur->_left == nullptr)
	{
		if (cur == _root)
		{
			_root = cur->_right;
		}
		if (cur->_key > parent->_key)
		{
			parent->_right = cur->_right;
		}
		else if (cur->_key < parent->_key)
		{
			parent->_left = cur->_right;
		}
		delete cur;
		return true;
	}
	//3、节点cur没有右子节点但有左子节点
	else if (cur->_right == nullptr)
	{
		if (cur == _root)
		{
			_root = cur->_left;
		}
		if (cur->_key > parent->_key)
		{
			parent->_right = cur->_left;
		}
		else if (cur->_key < parent->_key)
		{
			parent->_left = cur->_left;
		}
		delete cur;
		return true;
	}
	//4、节点cur既有左子节点也有右子节点
	//替换法
	else
	{
		//找左子树的最大结点——往左子树右边找
		Node* Lmax = cur->_left;
		Node* replaceParent = cur;
		while (Lmax->_right)
		{
			replaceParent = Lmax;
			Lmax = Lmax->_right;
		}
		swap(cur->_key, Lmax -> _key);//交换数据

		if (replaceParent->_left == Lmax)
			replaceParent->_left = Lmax->_left;
		else
			replaceParent->_right = Lmax->_left;

		delete Lmax;//Lmax与cur进行了交换
		return true;
	}
}

事实上，情况一已经包含在了情况二和情况三中，我们也可以不写情况一的代码~

我们也可以在while循环里面进行操作~我们这里就把代码进行优化~

代码2：

bool erase(const T& key)
{
	//处理根节点就为空的情况
	if (_root == nullptr)
	{
		return false;
	}
	//遍历查找元素
	Node* cur = _root;
	Node* parent = _root;
	while (cur)
	{
		if (key < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			//while循环里面进行删除
			//1、节点cur有右子节点但没有左子节点
			if (cur->_left == nullptr)
			{
				if (cur == _root)
				{
					_root = cur->_right;
				}
				else if (cur == parent->_left)
				{
					parent->_left = cur->_right;
				}
				else if (cur == parent->_right)
				{
					parent->_right = cur->_right;
				}
				delete cur;
			}
			//2、节点cur有左子节点但没有右子节点
			else if (cur->_right == nullptr)
			{
				if (cur == _root)
				{
					_root = cur->_left;
				}
				else if (cur == parent->_left)
				{
					parent->_left = cur->_left;
				}
				else if (cur == parent->_right)
				{
					parent->_right = cur->_left;
				}
				delete cur;
				
			}
			//3.节点cur有左右子节点
			else
			{
				//这里我们找找右边节点的最小值进行替换
				Node* replaceParent = cur;
				Node* Rmin = cur->_right;//找右边节点的最小值
				while (Rmin->_left)
				{
					replaceParent = Rmin;
					Rmin = Rmin->_left;
				}
				swap(Rmin->_key, cur->_key);

				if (replaceParent->_left == Rmin)//Rmin结点就是最小的，所以当前结点肯定没有左结点
					//需要处理Rmin节点的右结点
				{
					replaceParent->_left = Rmin->_right;
				}
				else if (replaceParent->_right == Rmin)
				{
					replaceParent->_right = Rmin->_right;
				}
				delete Rmin;	
			}
			return true;
		}
	}
	//如果找到空都没有找到进行返回，说明没有相应结点
	return false;
}

测试

代码1测试：

代码2测试：

两段代码都达到了我们想要的效果，我们可以根据自己习惯来进行选择~

二叉搜索树的析构

二叉搜索树涉及到了内存分配，所以我们最好自己显示写一份析构函数~

//析构函数
~BSTree()
{
	Destory(_root);
	_root = nullptr;
}
void Destory(Node* root)
{
	if (root == nullptr)
	{
		return;
	}
	else
	{
		//递归释放
		Destory(root->_left);
		Destory(root->_right);
		delete root;
	}
}

♥♥♥本篇博客内容结束，期待与各位优秀程序员交流，有什么问题请私信♥♥♥

♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥

✨✨✨✨✨✨个人主页✨✨✨✨✨✨

网站公告

今日签到

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

热门文章

最新发布