【C++：搜索二叉树】二叉搜索树从理论到实战完全解读：原理、两种场景下的实现

艾莉丝努力练剑

发布于 2025-11-16 20:25:07

1370

文章被收录于专栏：C / C++C / C++

C++的两个参考文老朋友（非官方文档）：cplusplus 官方文档（同步更新）：cppreference

前言

从二叉搜索树到map和set的使用、AVL树实现、红黑树、封装红黑树实现mymap和myset都是一个整体，也就是说，接下来我们要学习的就是平衡搜索二叉树相关的内容啦。AVL树和红黑树很难，而且不像前面的初阶stl有之前C语言的基础，这是一个非常重要的章节，本章节我们的重点就是介绍map、set的使用和底层，但是在那之前我们要先接触一个数据结构——就是今天我们要介绍的搜索二叉树，有了一定的基础，我们再去接触后面的内容才会更好理解一点。

1 ~> 理解二叉搜索树

1.1 二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树——

（1）若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值；（2）若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值；（3）它的左右子树也分别为二叉搜索树；（4）二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义，后续艾莉丝会介绍的map/set/multimap/multiset系列容器底层就是二叉搜索树，其中map/set不支持插入相等值，multimap/multiset支持插入相等值。

如下图所示就是两个搜索二叉树——

1.2 博主手记：核心特性

1.2.1 多元化的结构：灵活的数据结构

BST支持动态数据集合的高效操作，适合频繁插入、删除和查找的场景。

1.2.2 天然的搜索优势：擅长搜索的数据结构

利用二叉树的分支特性，BST在平均情况下能实现O(logn)的搜索效率。

2 ~> 二叉搜索树性能分析

2.1 时间复杂度分析

最优情况下，二叉搜索树为完全二叉树（或者接近完全二叉树），其高度为：logN； 最差情况下，二叉搜索树退化为单支树（或者类似单支），其高度为：N； 所以综合而言二叉搜索树增删查改时间复杂度为：O(N)。

那么这样的效率显然是无法满足我们需求的，因此后面艾莉丝会介绍二叉搜索树的变形——平衡二叉搜索树AVL树和红黑树，才能适用于我们在内存中存储和搜索数据。

2.2 二分查找的局限性

另外需要说明的是，二分查找也可以实现O(logN)级别的查找效率，但是二分查找有两大缺陷——

（1）需要存储在支持下标随机访问的结构中，并且有序；（2）插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。

（1）数据越有序，插入结果越坏——高度高、递归深、效率低，如右图所示； （2）插入越无序的数据，左右会平衡一点，结果反而越好，如左图所示

2.3 博主手记：性能优化要点

3 ~> 实现二叉搜索树的定义

3.1 命名规范

二叉搜索树常简写为BST，提高代码可读性（SBT不好听），二叉搜索树也叫搜索二叉树。

3.2 定义节点

template<class K>
struct BSTreeNode {
    BSTreeNode<K>* _left;
    BSTreeNode<K>* _right;
    K _key;
    
    BSTreeNode(const K& key)
        : _left(nullptr), _right(nullptr), _key(key)
    {}
};

3.3 实践：完整的类定义

提供插入、查找、删除等基本操作的接口设计。

4 ~> 二叉树搜索的插入操作详解

4.1 插入算法流程

从根节点开始，根据键值大小选择左子树或右子树，直到找到空位置插入新节点。

插入分成以下三种情况——

（1）树为空，则直接新增结点，赋值给root指针；（2）树不空，按二叉搜索树性质，插入值比当前结点大就往右走，插入值比当前结点小就往左走，找到空位置，插入新结点；（3）如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点（要注意保持逻辑一致性，插入相等的值不要一会往右走，一会又往左走）。

4.2 代码实践

4.2.1 代码演示

我们定义这样一个数组——

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

艾莉丝的代码演示如下——

// 不允许相等的值输入
template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node; // 节点名字有点长，可以typedef一下，因为要大量用到节点
public:
	// 不允许相等的值插入
	// 也可以允许相等的值插入，这样就要继续插入下去，但是要统一一下插入到左边还是右边，这样更好一点
	bool Insert(const K& key) // 实现插入  
	{
		if (_root == nullptr) // 根节点为空
		{
			_root = new Node(key); // 直接在根节点new一个
			return true;
		}

		Node* parent = nullptr; // 要给一个父节点的指针，因为链式结构要插入要完成链接
		Node* cur = _root;
		while (cur) // 查找到空就截止
		{
			if (cur->_key < key) // 比cur大就往右走
			{
				parent = cur; // cur要往下走，要给parent
				cur = cur->_right;
			}
			else if (cur->_key > key) // 比cur小就往左走
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false; // 相等就return false
			}
		}

		cur = new Node(key); // 新节点能不能直接给这个cur？不能，cur是个局部变量，除了作用域就销毁了
		// cur这个时候为空，接下来要继续链接，要再比较一次，链接到左边还是右边
		if (parent->_key < key)
		{
			parent->_right = cur; // 比parent大，插入在右边
		}
		else
		{
			parent->_left = cur;  // 比parent小，插入在左边
		}

		return true;
	}

这里艾莉丝写的是不允许相等的值输入条件下的写法。

4.2.2 测试用例设计

我们在Test.cpp文件里面包一下头文件，给一个数组，再定义出一棵树，因为数组也是支持范围for的，这里我们用范围for把数据插入进去。

4.2.3 C++递归的麻烦之处

C++递归很麻烦，这里要传根，但是根是私有的。

在类里面的递归基本上要这样玩，尤其是树的递归，因为树的递归起始条件一般是根，都要套一层（内部/外部），套一层，因为外部拿不到根，内部是可以拿到根的，这种方式是最推荐的拿根方式，当然也可以get root，但是更推荐用上面这种方法。

调的是不需要传根的，再去调用这个子函数，把根传过去，这样外面就不需要传了，也不需要提供get root，不过get root调用的时候也方便。

4.3 InOrder：中序遍历验证

利用BST的中序遍历必然有序的特性验证插入正确性。

要写成这样套一层的结构，原因上面已经提到了，这里不再赘述。

写成中序遍历的好处——

（1）中序遍历：最简单的递归；（2）中序遍历有序，并且数据都在，并且能够很好地验证功能。

4.4 运行演示

运行一下——

成功插入进去了，并且因为是中序遍历，结果是有序的。

4.5 博主手记：实现要点

4.6 平衡性考虑：平衡和旋转

平衡和旋转这一块非常复杂，仅凭三言两语是说不清楚的，我们后面会详细介绍。

5 ~> 查找操作实现

5.1 查找算法

利用BST的排序特性，通过比较键值快速定位目标节点。

（1）从根开始比较，查找x，x比根的值大则往右边走查找，x比根值小则往左边走查找；（2）最多查找高度次，走到到空，还没找到，这个值不存在；（3）如果不支持插入相等的值，找到x即可返回；（4）如果支持插入相等的值，意味着有多个x存在，一般要求查找中序的第一个x。如下图，查找3，要找到1的右孩子的那个3返回。

5.2 代码实践

查找的代码也可以递归写，这里艾莉丝没有用递归写——

5.3 测试用例设计

我们就查找一下1这个数据——

5.4 运行

运行一下——

6 ~> 删除操作深度解析

6.1 删除前的定位：要先查找一下

首先需要找到待删除节点及其父节点。

6.1.1 查找元素存在分四种情况

首先查找元素是否在二又搜索树中，如果不存在，则返回false。

如果查找元素存在则分以下四种情况需要分别处理一下（假设要删除的结点为N）：

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

6.1.2 对应以上四种情况的解决方案

（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，可以直接删除。

6.2 示例分析

接下来我们通过具体例子来看看各种删除情况——

6.3 实践：代码实现

6.3.1 节点定位：查找要删除的节点

实现高效的节点查找逻辑——

查找过程图示：

假设要删除key = 6，如下图所示——

查找路径： cur = 8, 6 < 8 → 向左 cur = 3, 6 > 3 → 向右 cur = 6, 6 == 6 → 找到！ 此时： parent = 节点3 cur = 节点6

6.3.2 左子树为空的情况

6.3.3 右子树为空的情况

6.3.4 左右子树都存在的情况

6.3.5 完整的Erase实现

	// 搜索二叉树这个部分，删除是很麻烦的，先找到再删除，找到不难，但是删除很难
	// 面试如果考，一定不会考插入、查找，肯定会考删除
	bool Erase(const K& key)
	{
		Node* parent = nullptr; // 记录当前节点的父节点
		Node* cur = _root;      // 从根节点开始搜索
		// 1、查找要删除的节点
		while (cur)
		{
			if (cur->_key < key)      // 目标key比当前节点大，向右子树搜索
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key) // 目标key比当前节点小，向左子树搜索
			{
				parent = cur;
				cur = cur->_left;
			}
			else // 找到要删除的节点cur——要干掉的节点
			{
				// 情况1：要删除的节点左子树为空（只有右子树或没有子树）
				// 左为空
				if (cur->_left == nullptr) // 父亲节点的左指向我的右
				{
					//if (cur == parent->_left) // 13没删掉
					if (cur == _root) // 如果要删除的是根节点,（改变根节点）让孩子自己变成根
					{
						_root = cur->_right; // 上面是左为空，所以让父亲指向我的右
						// 让右孩子成为新的根
					}
					else
					{
						// 判断cur是父节点的左孩子还是右孩子
						if (cur == parent->_left) // 父亲节点的左指向我的右，父节点的左指针指向cur的右孩子
						{
							parent->_left = cur->_right; 
						}
						else					  // 父亲节点的右指向我的左
						{
							parent->_right = cur->_right; // 父节点的右指针指向cur的右孩子
						}
					}

					delete cur; // 删除cur，释放节点内存
					return true; // 找到了，删除成功
				}
				// 情况2：要删除的节点右子树为空（只有左子树）
				// 右为空
				else if (cur->_right == nullptr) // 父亲节点的右指向我的左
				{
					if (cur == _root) // 如果要删除的是根节点，（改变根节点）让孩子自己变成根
					{
						_root = cur->_left; // 上面是右为空，所以让父亲指向我的左
						// 让左孩子成为新的根
					}
					else
					{
						if (cur == parent->_left) 
						{
							parent->_left = cur->_left; // 父节点的左指针指向cur的左孩子
						}
						else
						{
							parent->_right = cur->_left; // 父节点的右指针指向cur的左孩子
						}
					}

					delete cur;  // 释放节点内存
					return true; // 删除成功
				}
				// 情况3：要删除的节点左右子树都不为空（最复杂的情况！！！）
				else // 左右均不为空
				{
					// 策略：用右子树的最小节点（中序后继）来替代当前节点
					// 找cur右子树的最小节点替代
					Node* replaceParent = cur; // 替代节点的父节点，replace节点的parent，没有这个就不好删
					Node* replace = cur->_right; // 从右子树开始找

					// 在右子树中一直向左找，找到最小的节点（最左节点）
					while (replace->_left) // 找最左节点，不为空就继续，等于空就找到了
					{
						replaceParent = replace; // 把replace给过去，每次都给
						replace = replace->_left; // 左不为空，就不断往左边找
					}

					// 用替代节点的值覆盖要删除节点的值
					cur->_key = replace->_key; // 不需要交换，替代的本质是把replace节点的值传过去

					//  需要判断一下
					// 删除替代节点（替代节点要么是叶子节点，要么只有右子树）
					if (replaceParent->_left == replace) // 如果左指向replace
						replaceParent->_left = replace->_right; 
						// 连接替代节点的右子树,让左指向replace的右
						
					else // 如果右指向replace
						replaceParent->_right = replace->_right; 
						// 连接替代节点的右子树，让右指向replace的右

					delete replace; // 释放替代节点内存，彻底删除replace
					return true;    // 删除成功
				}
			}
		}

		return false; // 没找到删除的节点，直接return false
	}

6.4 测试用例设计

这里是删8是会出问题的！我们要改一改。

6.4.1 替代节点的父节点就是当前节点：replace的parent就是cur

6.4.2 需要判断一下：连接判断逻辑

改变根节点，让这个孩子自己变成根——

6.5 访问for重新删

需要全部再删一次，重复删不会报错。

6.6 运行

运行一下——

成功删掉了，功能顺利验证。

6.7 博主手记：实现技巧

7 ~> 二叉搜索树的完整代码示例与实践演示

SearchBinaryTree.h：

#pragma once
#include<iostream>
using namespace std;

// 这里名字简写不雅观，就像车牌号，浙江的浙B、海南的琼B，有点尴尬😅

// // 定义节点 
//template<class K>
////struct SearchBinaryTreeNode // 名字太长
////struct SBTreeNode // 简写，简写一般可以考虑用首字母，但是这个简写有些不雅观
// // 那这个地方我们可以稍微调整一下，因为它可以叫二叉搜索树也可以叫搜索二叉树
//struct BSTreeNode // 叫二叉搜索树，这样就不会太尴尬了
//{
//
//};
//
// // 名字太长了，上面再定义节点，名字太长
//template<class K>
////class SearchBinaryTree // 简写一般可以考虑用首字母
////class SBTree           // 但是这个简写有些不雅观，写个数据结构出来人家以为在骂人那不行
//class BSTree			   // 叫二叉搜索树，这样就不会太尴尬了
//{
//
//}; 

// 接下来正式开始定义

template<class K>
struct BSTreeNode
{
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key; // K就是key

	// 构造，构造完节点就没问题了
	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{ }
};

// 不允许相等的值输入
template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node; // 节点名字有点长，可以typedef一下，因为要大量用到节点
public:
	// 不允许相等的值插入
	// 也可以允许相等的值插入，这样就要继续插入下去，但是要统一一下插入到左边还是右边，这样更好一点
	bool Insert(const K& key) // 实现插入  
	{
		if (_root == nullptr) // 根节点为空
		{
			_root = new Node(key); // 直接在根节点new一个
			return true;
		}

		Node* parent = nullptr; // 要给一个父节点的指针，因为链式结构要插入要完成链接
		Node* cur = _root;
		while (cur) // 查找到空就截止
		{
			if (cur->_key < key) // 比cur大就往右走
			{
				parent = cur; // cur要往下走，要给parent
				cur = cur->_right;
			}
			else if (cur->_key > key) // 比cur小就往左走
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false; // 相等就return false
			}
		}

		cur = new Node(key); // 新节点能不能直接给这个cur？不能，cur是个局部变量，除了作用域就销毁了
		// cur这个时候为空，接下来要继续链接，要再比较一次，链接到左边还是右边
		if (parent->_key < key)
		{
			parent->_right = cur; // 比parent大，插入在右边
		}
		else
		{
			parent->_left = cur;  // 比parent小，插入在左边
		}

		return true;
	}

	// 查找——也可以递归写，但是没有递归更好
	bool Find(const K& key)
	{
		Node* cur = _root; // 把根节点给cur，比它小往左边走，比它大往右边走
		while (cur)
		{
			if (cur->_key < key)
			{
				// 查找也不需要parent
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				// 查找也不需要parent
				cur = cur->_left;
			}
			else
			{
				return true; // 相等就找到了,return true
			}
		}

		return false; // 找不到就return false
	}

	// 搜索二叉树这个部分，删除是很麻烦的，先找到再删除，找到不难，但是删除很难
	// 面试如果考，一定不会考插入、查找，肯定会考删除
	bool Erase(const K& key)
	{
		Node* parent = nullptr; // 记录当前节点的父节点
		Node* cur = _root;      // 从根节点开始搜索
		// 1、查找要删除的节点
		while (cur)
		{
			if (cur->_key < key)      // 目标key比当前节点大，向右子树搜索
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key) // 目标key比当前节点小，向左子树搜索
			{
				parent = cur;
				cur = cur->_left;
			}
			else // 找到要删除的节点cur——要干掉的节点
			{
				// 情况1：要删除的节点左子树为空（只有右子树或没有子树）
				// 左为空
				if (cur->_left == nullptr) // 父亲节点的左指向我的右
				{
					//if (cur == parent->_left) // 13没删掉
					if (cur == _root) // 如果要删除的是根节点,（改变根节点）让孩子自己变成根
					{
						_root = cur->_right; // 上面是左为空，所以让父亲指向我的右
						// 让右孩子成为新的根
					}
					else
					{
						// 判断cur是父节点的左孩子还是右孩子
						if (cur == parent->_left) // 父亲节点的左指向我的右，父节点的左指针指向cur的右孩子
						{
							parent->_left = cur->_right; 
						}
						else					  // 父亲节点的右指向我的左
						{
							parent->_right = cur->_right; // 父节点的右指针指向cur的右孩子
						}
					}

					delete cur; // 删除cur，释放节点内存
					return true; // 找到了，删除成功
				}
				// 情况2：要删除的节点右子树为空（只有左子树）
				// 右为空
				else if (cur->_right == nullptr) // 父亲节点的右指向我的左
				{
					if (cur == _root) // 如果要删除的是根节点，（改变根节点）让孩子自己变成根
					{
						_root = cur->_left; // 上面是右为空，所以让父亲指向我的左
						// 让左孩子成为新的根
					}
					else
					{
						if (cur == parent->_left) 
						{
							parent->_left = cur->_left; // 父节点的左指针指向cur的左孩子
						}
						else
						{
							parent->_right = cur->_left; // 父节点的右指针指向cur的左孩子
						}
					}

					delete cur;  // 释放节点内存
					return true; // 删除成功
				}
				// 情况3：要删除的节点左右子树都不为空（最复杂的情况！！！）
				else // 左右均不为空
				{
					// 策略：用右子树的最小节点（中序后继）来替代当前节点
					// 找cur右子树的最小节点替代
					//Node* replaceParent = nullptr; // 如果左边直接是空，那么cur直接是父亲节点
					Node* replaceParent = cur; // 替代节点的父节点，replace节点的parent，没有这个就不好删
					Node* replace = cur->_right; // 从右子树开始找

					// 在右子树中一直向左找，找到最小的节点（最左节点）
					while (replace->_left) // 找最左节点，不为空就继续，等于空就找到了
					{
						replaceParent = replace; // 把replace给过去，每次都给
						replace = replace->_left; // 左不为空，就不断往左边找
					}

					// 用替代节点的值覆盖要删除节点的值
					cur->_key = replace->_key; // 不需要交换，替代的本质是把replace节点的值传过去

					//  需要判断一下
					// 删除替代节点（替代节点要么是叶子节点，要么只有右子树）
					if (replaceParent->_left == replace) // 如果左指向replace
						replaceParent->_left = replace->_right; 
						// 连接替代节点的右子树,让左指向replace的右
						
					else // 如果右指向replace
						replaceParent->_right = replace->_right; 
						// 连接替代节点的右子树，让右指向replace的右

					delete replace; // 释放替代节点内存，彻底删除replace
					return true;    // 删除成功
				}
			}
		}

		return false; // 没找到删除的节点，直接return false
	}

	// 在类里面的递归基本上要这样玩，尤其是树的递归，因为树的递归起始条件一般是根，都要套一层（内部/外部）
	void InOrder() // 套一层，因为外部拿不到根，内部是可以拿到根的，这种方式是最推荐的拿根方式
	{
		// 调的是不需要传根的，但是再去调用这个子函数，把根传过去
		// 这样外面就不需要传了，也不需要提供get root，不过get root调用的时候也方便
		_InOrder(_root); // 树的起始条件
		cout << endl; // 打印完了最好在这里换个行
	}

private:
	// 中序遍历：最简单的递归
	// 写出一个中序遍历出来，中序遍历有序，并且数据都在，能够验证功能
	void _InOrder(Node* root) // 套一层，把它变成一个子函数
	{
		if (root == nullptr)
			return;

		_InOrder(root->_left); // 先递归访问左子树，传左子树的根
		cout << root->_key << " "; // 再看这个地方的值
		_InOrder(root->_right); // 再递归访问右子树，传右子树的根
	}

private:
	Node* _root = nullptr; // 默认构造时让根节点初始化一下就可以了
};

Test.cpp：

#define  _CRT_SECURE_NO_WARNINGS  1
#include"SearchBinaryTree.h"

int main()
{
	int a[] = { 8,3,1,10,1,6,4,7,14,13 }; // 给一个数组
	BSTree<int> t; // 定义一棵树
	for (auto e : a) // 数组也支持访问for
	{
		t.Insert(e); // 把数据插入进去
	}

	t.InOrder(); // C++递归很麻烦，这里要传根，但是根是私有的
	// 打印结果：1 3 4 6 7 8 10 13 14（成功，并且是有序的——中序遍历）
	// 这样基本上说明插入是没问题的

	t.Find(1);
	t.InOrder();

	t.Erase(3); // 没啥问题
	t.Erase(8);
	t.InOrder();

	t.Erase(1); // 没啥问题
	t.InOrder();

	t.Erase(10); // 左为空
	t.InOrder();

	for (auto e : a) // 需要全部再删一次，重复删不会报错
	{
		t.Insert(e);
	}

	return 0;
}

运行演示

8 ~> 二叉搜索树key和key / value使用场景

8.1 key搜索场景

只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断key在不在。key的搜索场景实现的二又树搜索树支持增删查，但是不支持修改，修改key破坏搜索树结构了。

场景1：小区无人值守车库，小区车库买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌在不在系统中，在则抬杆，不在则提示非本小区车辆，无法进入。

场景2：检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不在则波浪线标红提示。

8.2 key / value使用场景

每一个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中（结点）除了需要存储key还要存储对应的value，增/删/查还是以key为关键字走二叉搜索树的规则进行比较，可以快速查找到key对应的value。key/value的搜索场景实现的二叉树搜索树支持修改，但是不支持修改key，修改key破坏搜索树性质了，可以修改value。

场景1：简单中英互译字典，树的结构中（结点）存储key(英文）和vlaue（中文），搜索时输入英文，则同时查找到了英文对应的中文。

场景2：商场无人值守车库，入口进场时扫描车牌，记录车牌和入场时间，出口离场时，扫描车牌，查找入场时间，用当前时间-入场时间计算出停车时长，计算出停车费用，缴费后抬杆，车辆离场——

场景3：统计一篇文章中单词出现的次数，读取一个单词，查找单词是否存在，不存在这个说明第一次出现，( 单词 , 1），单词存在，则++单词对应的次数。

8.3 实践：key / value代码实现

key / value场景下的代码实现如下所示——

// Alice：key / value场景
namespace key_value
{
	// 开始定义
	template<class K,class V>
	struct BSTreeNode
	{
		BSTreeNode<K,V>* _left;
		BSTreeNode<K,V>* _right;
		K _key; // K就是key
		V _value;
		

		// 构造，构造完节点就没问题了
		BSTreeNode(const K& key,const V& value)
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
			,_value(value)
		{
		}
	};

	// 不允许相等的值输入
	template<class K,class V>
	class BSTree
	{
		typedef BSTreeNode<K,V> Node; // 节点名字有点长，可以typedef一下，因为要大量用到节点
	public:
		// 不允许相等的值插入
		// 也可以允许相等的值插入，这样就要继续插入下去，但是要统一一下插入到左边还是右边，这样更好一点
		bool Insert(const K& key,const V& value) // 实现插入  
		{
			if (_root == nullptr) // 根节点为空
			{
				_root = new Node(key,value); // 直接在根节点new一个
				return true;
			}

			Node* parent = nullptr; // 要给一个父节点的指针，因为链式结构要插入要完成链接
			Node* cur = _root;
			while (cur) // 查找到空就截止
			{
				if (cur->_key < key) // 比cur大就往右走
				{
					parent = cur; // cur要往下走，要给parent
					cur = cur->_right;
				}
				else if (cur->_key > key) // 比cur小就往左走
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false; // 相等就return false
				}
			}

			cur = new Node(key, value);// 新节点能不能直接给这个cur？不能，cur是个局部变量，除了作用域就销毁了
			// cur这个时候为空，接下来要继续链接，要再比较一次，链接到左边还是右边
			if (parent->_key < key)
			{
				parent->_right = cur; // 比parent大，插入在右边
			}
			else
			{
				parent->_left = cur;  // 比parent小，插入在左边
			}

			return true;
		}

		// 查找——也可以递归写，但是没有递归更好
		Node* Find(const K& key)
		{
			Node* cur = _root; // 把根节点给cur，比它小往左边走，比它大往右边走
			while (cur)
			{
				if (cur->_key < key)
				{
					// 查找也不需要parent
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					// 查找也不需要parent
					cur = cur->_left;
				}
				else
				{
					return cur; // 相等就找到了,return cur
				}
			}

			return nullptr; // 找不到就return nullptr
		}

		// 搜索二叉树这个部分，删除是很麻烦的，先找到再删除，找到不难，但是删除很难
		// 面试如果考，一定不会考插入、查找，肯定会考删除
		bool Erase(const K& key)
		{
			Node* parent = nullptr; // 记录当前节点的父节点
			Node* cur = _root;      // 从根节点开始搜索
			// 1、查找要删除的节点
			while (cur)
			{
				if (cur->_key < key)      // 目标key比当前节点大，向右子树搜索
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key) // 目标key比当前节点小，向左子树搜索
				{
					parent = cur;
					cur = cur->_left;
				}
				else // 找到要删除的节点cur——要干掉的节点
				{
					// 情况1：要删除的节点左子树为空（只有右子树或没有子树）
					// 左为空
					if (cur->_left == nullptr) // 父亲节点的左指向我的右
					{
						//if (cur == parent->_left) // 13没删掉
						if (cur == _root) // 如果要删除的是根节点,（改变根节点）让孩子自己变成根
						{
							_root = cur->_right; // 上面是左为空，所以让父亲指向我的右
							// 让右孩子成为新的根
						}
						else
						{
							// 判断cur是父节点的左孩子还是右孩子
							if (cur == parent->_left) // 父亲节点的左指向我的右，父节点的左指针指向cur的右孩子
							{
								parent->_left = cur->_right;
							}
							else					  // 父亲节点的右指向我的左
							{
								parent->_right = cur->_right; // 父节点的右指针指向cur的右孩子
							}
						}

						delete cur; // 删除cur，释放节点内存
						return true; // 找到了，删除成功
					}
					// 情况2：要删除的节点右子树为空（只有左子树）
					// 右为空
					else if (cur->_right == nullptr) // 父亲节点的右指向我的左
					{
						if (cur == _root) // 如果要删除的是根节点，（改变根节点）让孩子自己变成根
						{
							_root = cur->_left; // 上面是右为空，所以让父亲指向我的左
							// 让左孩子成为新的根
						}
						else
						{
							if (cur == parent->_left)
							{
								parent->_left = cur->_left; // 父节点的左指针指向cur的左孩子
							}
							else
							{
								parent->_right = cur->_left; // 父节点的右指针指向cur的左孩子
							}
						}

						delete cur;  // 释放节点内存
						return true; // 删除成功
					}
					// 情况3：要删除的节点左右子树都不为空（最复杂的情况！！！）
					else // 左右均不为空
					{
						// 策略：用右子树的最小节点（中序后继）来替代当前节点
						// 找cur右子树的最小节点替代
						//Node* replaceParent = nullptr; // 如果左边直接是空，那么cur直接是父亲节点
						Node* replaceParent = cur; // 替代节点的父节点，replace节点的parent，没有这个就不好删
						Node* replace = cur->_right; // 从右子树开始找

						// 在右子树中一直向左找，找到最小的节点（最左节点）
						while (replace->_left) // 找最左节点，不为空就继续，等于空就找到了
						{
							replaceParent = replace; // 把replace给过去，每次都给
							replace = replace->_left; // 左不为空，就不断往左边找
						}

						// 用替代节点的值覆盖要删除节点的值
						cur->_key = replace->_key; // 不需要交换，替代的本质是把replace节点的值传过去
						cur->_value = replace->_value;

						//  需要判断一下
						// 删除替代节点（替代节点要么是叶子节点，要么只有右子树）
						if (replaceParent->_left == replace) // 如果左指向replace
							replaceParent->_left = replace->_right;
						// 连接替代节点的右子树,让左指向replace的右

						else // 如果右指向replace
							replaceParent->_right = replace->_right;
						// 连接替代节点的右子树，让右指向replace的右

						delete replace; // 释放替代节点内存，彻底删除replace
						return true;    // 删除成功
					}
				}
			}

			return false; // 没找到删除的节点，直接return false
		}

		// 在类里面的递归基本上要这样玩，尤其是树的递归，因为树的递归起始条件一般是根，都要套一层（内部/外部）
		void InOrder() // 套一层，因为外部拿不到根，内部是可以拿到根的，这种方式是最推荐的拿根方式
		{
			// 调的是不需要传根的，但是再去调用这个子函数，把根传过去
			// 这样外面就不需要传了，也不需要提供get root，不过get root调用的时候也方便
			_InOrder(_root); // 树的起始条件
			cout << endl; // 打印完了最好在这里换个行
		}

	private:
		// 中序遍历：最简单的递归
		// 写出一个中序遍历出来，中序遍历有序，并且数据都在，能够验证功能
		void _InOrder(Node* root) // 套一层，把它变成一个子函数
		{
			if (root == nullptr)
				return;

			_InOrder(root->_left); // 先递归访问左子树，传左子树的根
			cout << root->_key << " "; // 再看这个地方的值
			_InOrder(root->_right); // 再递归访问右子树，传右子树的根
		}

	private:
		Node* _root = nullptr; // 默认构造时让根节点初始化一下就可以了
	};
}

8.4 设计测试用例

8.4.1 测试用例一

8.4.2 测试用例二

8.5 运行演示

8.5.1 测试用例一运行演示

运行一下——

8.5.2 测试用例二运行演示

运行一下——

8.5.3 取消运行

^Z：Ctrl + Z + Enter（回车），就能取消运行。

8.6 博主手记

结尾

往期回顾：

【C++：多态】C++多态实现深度剖析：从抽象类约束到虚函数表机制

结语：都看到这里啦！那请大佬不要忘记给博主来个“一键四连”哦！

🗡博主在这里放了一只小狗，大家看完了摸摸小狗放松一下吧！🗡 ૮₍ ˶ ˊ ᴥ ˋ˶₎ა

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-11-12，如有侵权请联系 cloudcommunity@tencent.com 删除

搜索

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度