【C++】18.二叉搜索树-EW帮帮网

由于map和set的底层是红黑树，同时后面要讲的AVL树(高度平衡二叉搜索树)，为了方便理解，我们先来讲解二叉搜索树，因为红黑树和AVL树都是在二叉搜索树的前提下实现的

在之前的C语言数据结构章节中，我们讲过二叉树，这次就来认识一下二叉搜索树

1. 二叉搜索树的概念

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

• 若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值

• 若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值

• 它的左右子树也分别为二叉搜索树

• 二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义，后续我们学习map/set/multimap/multiset系列容器底层就是二叉搜索树，其中map/set不支持插入相等值，multimap/multiset支持插入相等值

2. 二叉搜索树的性能分析

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其高度为： log2 N

最差情况下，二叉搜索树退化为单支树(或者类似单支)，其高度为： N

所以综合而言二叉搜索树增删查改时间复杂度为： O(N)

那么这样的效率显然是无法满足我们需求的，我们后续章节需要继续讲解二叉搜索树的变形，平衡二叉搜索树AVL树和红黑树，才能适用于我们在内存中存储和搜索数据。

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

1. 需要存储在支持下标随机访问的结构中，并且有序。

2. 插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。

这里也就体现出了平衡二叉搜索树的价值

3. 二叉搜索树的实现

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

	K _key;
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
};

template<class K>
class BSTree
{
	//typedef BSTreeNode<K> Node;
	using Node = BSTreeNode<K>;
public:
private:
	Node* _root = nullptr;
};

首先我们要管理每个节点的数据以及它的左右孩子，所以我们先封装一个树节点类，用来管理节点的数据和左右孩子，其次我们要把每个树节点统一管理，所以还需要再封装一个树类，用来管理所有节点。

BSTreeNode:

这里我们模板参数使用K（表示key的意思），模板参数并不是只能是T

和之前list一样，只需要写构造，原因如下：

I. 节点类的核心需求

二叉搜索树的节点通常需要强制初始化关键值（如节点的值 val），并将子节点指针（left 和 right）初始化为空。
通过定义带参数的构造函数，可以确保：

值必须显式初始化：节点必须有值，不能存在未初始化的节点。
子节点指针默认置空：左右子节点指针默认初始化为 nullptr，避免野指针问题。

II. C++ 构造函数规则

默认构造函数：如果用户没有定义任何构造函数，编译器会生成一个默认构造函数。但如果用户定义了带参数的构造函数，编译器不再生成默认构造函数。此时若尝试无参创建对象会报错，符合“节点必须有值”的逻辑。
拷贝构造函数：若未显式定义，编译器会生成一个浅拷贝构造函数。对于树节点来说，浅拷贝通常是危险的（可能导致重复释放同一内存），但二叉搜索树的操作一般通过指针传递节点，不涉及拷贝节点对象本身，因此可以暂时忽略拷贝构造函数的需求。若需要更严格的控制，可显式删除拷贝构造函数。

III. 为什么其他构造函数可以不写？

默认构造函数：
已通过带参构造函数禁用，确保节点必须有初始值。
拷贝构造函数：
树节点通常通过指针操作，不需要拷贝节点对象。若需要复制整棵树（深拷贝），应在树结构中实现，而非节点类中。
移动构造函数：
对于简单的值类型（如 int 和指针），默认生成的移动操作已足够。
析构函数：
节点类的子节点指针是“原始指针”，但二叉搜索树的释放通常由树结构统一管理（如递归删除子树），因此节点类可以不显式定义析构函数。

BSTree:

我们先将BSTreeNode<K>类型typedef一下（类型太长了不好写），但是我们这里使用using，在现阶段using和typedef功能是一样的，具体差异后面章节会讲，不过using取别名的用法有点不一样；由于我们要管理树，将所有节点联系起来，所以我们可以提供一个指向根节点的指针_root作为成员变量，方便我们管理

3.1 二叉搜索树的插入

插入的具体过程如下：

1. 树为空，则直接新增结点，赋值给root指针

2. 树不空，按二叉搜索树性质，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位置，插入新结点。

3. 如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑一致性，插入相等的值不要一会往右走，一会往左走）

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

以这组数据为例来画图演示一下：

插入不相等的值

插入相等的值

代码实现：

代码实现分别可以用递归和非递归两种方法来实现，这里我们采用非递归，递归太深的情况会栈溢出，同时我们这里默认不允许插入相等的值。

第一步：处理空树的特殊情况

若树为空（_root == nullptr），直接创建根节点并初始化值为 key，返回 true 表示插入成功。
```
if (_root == nullptr) {
    _root = new Node(key);
    return true;
}
```

第二步：查找插入位置

初始化指针：
- parent 记录当前节点的父节点（初始为 nullptr）。
- cur 从根节点 _root 开始遍历。
```
Node* parent = nullptr;
Node* cur = _root;
```

循环遍历树：

若 key 大于当前节点的值，向右子树移动。
若 key 小于当前节点的值，向左子树移动。
若遇到重复值（key 已存在），返回 false 表示插入失败。

while (cur) {
    if (cur->_key < key) {
        parent = cur;
        cur = cur->_right;
    } else if (cur->_key > key) {
        parent = cur;
        cur = cur->_left;
    } else {
        return false; // 重复值，插入失败
    }
}

第三步：创建新节点并链接到父节点

创建新节点：
循环结束后，cur 指向 nullptr，此时 parent 是待插入位置的父节点。创建新节点 cur。
```
cur = new Node(key);
```

确定插入方向：
根据 key 与父节点值的比较结果，将新节点链接为父节点的左子节点或右子节点。

if (parent->_key < key) {
    parent->_right = cur; // 插入右子树
} else {
    parent->_left = cur;  // 插入左子树
}

代码如下：

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->_right;
		}
		else if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}

	cur = new Node(key);
	if (parent->_key < key)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	return true;
}

如果想要允许插入相等的值，只需要在第二步插入位置时，判断条件修改一下为cur->_key <= key或者cur->_key >= key，然后去掉else语句——遇到重复值（key 已存在），返回 false 表示插入失败。

3.2 打印测试

这里我们采用中序遍历的方式，将数据打印出来

void InOrder(Node* root)
{
	if (root == nullptr) return;

	InOrder(root->_left);
	cout << root->_key << " ";
	InOrder(root->_right);
}

使用上面图示数据模拟：

void Test()
{
	int a[] = { 8,3,1,10,6,4,7,14,13 };
	BSTree<int> t;
	for (auto x : a)
	{
		t.Insert(x);
	}
	t.InOrder(_root);
}

显然这么写是错的，编译一下可以看到

我们知道_root是私有成员变量，在类外我们是访问不了的，但是我们中序遍历需要传根节点指针，那应该怎么办呢？

我们可以实现一个类外可以访问的访问根节点的成员函数GetRoot()，但是这么写不太好，我们可以这么写

public:
	void InOrder()
	{
		_InOrder(_root);
        cout << endl;
	}
private:
	void _InOrder(Node* root)
	{
		if (root == nullptr) return;

		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}

我们直接将中序遍历私有，然后在公有下把中序遍历封装在另一个函数中，这样我们就可以在类外无参的使用中序遍历

运行结果：

3.3 二叉搜索树的查找

1. 从根开始比较，查找x，x比根的值大则往右边走查找，x比根值小则往左边走查找。

2. 最多查找高度次，走到空，还没找到，这个值不存在。

3. 如果不支持插入相等的值，找到x即可返回

4. 如果支持插入相等的值，意味着有多个x存在，一般要求查找中序的第一个x。如下图，查找3，要找到1的右孩子的那个3返回

代码实现：

查找非常简单，和插入的思路一样

bool Find(const K& key)
{
	Node* cur = _root;

	while (cur)
	{
		if (cur->_key < key)
		{
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			cur = cur->_left;
		}
		else
		{
			return true;//找到了
		}
	}
	//没找到
	return false;
}

3.4 二叉搜索树的删除

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

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

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

代码实现：

第1步. 查找待删除节点

初始化指针：
parent 记录当前节点的父节点（初始为 nullptr），cur 从根节点 _root 开始遍历。

遍历搜索：
根据 key 与当前节点值的比较，向左或向右子树移动，直到找到目标节点或遍历结束。

while (cur) {
    if (cur->_key < key) { ... }    // 向右子树移动
    else if (cur->_key > key) { ... } // 向左子树移动
    else { ... }                      // 找到目标节点，进入删除逻辑
}

未找到处理：
若遍历结束未找到 key，返回 false 表示删除失败。

第2步. 根据子节点情况删除节点

(1) 左子节点为空（或右子节点为空）

直接替换：
- 若左子节点为空，用右子节点 cur->_right 替代当前节点。
- 若右子节点为空，用左子节点 cur->_left 替代当前节点。
处理根节点：
若删除的是根节点（cur == _root），直接更新 _root 为对应的子节点。

链接父节点：
根据 cur 是父节点的左/右子节点，更新父节点的指针指向 cur 的子节点。

// 左子节点为空的情况
if (cur->_left == nullptr) {
    if (cur == _root) {
        _root = cur->_right; // 更新根节点
    } else {
        if (parent->_right == cur) {
            parent->_right = cur->_right;
        } else {
            parent->_left = cur->_right;
        }
    }
    delete cur;
}

(2) 左右子节点均存在

替换法删除：
- 找到右子树的最小节点：从 cur->_right 出发，循环找到最左侧节点 replace（即右子树的最小节点）。
- 替换值：将 replace->_key 赋值给 cur->_key。
- 删除替换节点：
  - 若 replace 是其父节点的左子节点，将父节点的左指针指向 replace 的右子节点。
  - 若 replace 是其父节点的右子节点（即右子树没有左子节点），将父节点的右指针指向 replace 的右子节点。
  - 删除 replace 节点。
```
else {
    // 找右子树的最小节点
    Node* replaceParent = cur;
    Node* replace = cur->_right;
    while (replace->_left) {
        replaceParent = replace;
        replace = replace->_left;
    }
    // 替换值
    cur->_key = replace->_key;
    // 删除替换节点
    if (replace == replaceParent->_left) {
        replaceParent->_left = replace->_right;
    } else {
        replaceParent->_right = replace->_right;
    }
    delete replace;
}
```

第3步. 返回结果

删除成功：
在找到并删除节点后，立即返回 true。
删除失败：
若循环结束未找到节点，返回 false。

总结步骤

查找目标节点：遍历树找到待删除节点。
处理删除逻辑：
- 单子节点：直接用子节点替换，更新父节点或根节点指针。
- 双子节点：替换法删除（右子树最小节点），调整指针关系。
释放内存：删除节点并返回操作结果。

代码如下：

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 == _root)
				{
					_root = cur->_right;
				}
				else
				{
					if (parent->_right == cur)
					{
						// 此时cur->_key > parent->_key
						parent->_right = cur->_right;
					}
					else //parent->_left == cur
					{
						// 此时cur->_key < parent->_key
						parent->_left = cur->_right;
					}
				}

				delete cur;
			}
			else if (cur->_right == nullptr) // 右孩子为空
			{
				if (cur == _root)
				{
					_root = cur->_left;
				}
				else
				{
					if (parent->_right == cur)
					{
						// 此时cur->_key > parent->_key
						parent->_right = cur->_left;
					}
					else //parent->_left == cur
					{
						// 此时cur->_key < parent->_key
						parent->_left = cur->_left;
					}
				}

				delete cur;
			}
			else // 两个孩子都不为空
			{
				// 替换法删除节点——右子树最小节点替换
				Node* replaceParent = cur;// 要考虑删除根节点时，不能置为nullptr
				Node* replace = cur->_right;
				while (replace->_left)
				{
					replaceParent = replace;
					replace = replace->_left;
				}

				cur->_key = replace->_key;

				if (replace == replaceParent->_left)
				{
					replaceParent->_left = replace->_right;
				}
				else //replace == replaceParent->_right
				{
					// 此时第一个右孩子就是右子树最小节点
					replaceParent->_right = replace->_right;
				}

				delete replace;
			}
			//成功删除
			return true;
		}
	}
	//没找到，删除失败
	return false;
}

4. 二叉搜索树key和key/value使用场景

4.1 key搜索场景：

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

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

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

4.2 key/value搜索场景：

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

I. 键（Key）与值（Value）的定义

键（Key）
键是用于唯一标识数据的标识符。它类似于字典中的“词条”，用于快速查找、插入或删除对应的值。
- 特性：唯一性（在同一个容器中，键不能重复）、可比较性（必须支持比较或哈希操作）。
- 示例：学号、身份证号、用户名等。
值（Value）
值是与键关联的实际数据。它可以是任意类型，存储具体的业务信息。
- 特性：允许重复、无特殊约束（除非业务需要）。
- 示例：学生成绩、用户详细信息、缓存的数据等。

II. 键与值的核心差异

特性	键（Key）	值（Value）
唯一性	必须唯一	可以重复
作用	快速定位数据	存储实际数据
约束	必须可比较或可哈希	无特殊约束（类型灵活）
修改性	通常不可修改（需删除后重新插入）	可直接修改

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

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

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

代码实现：

我们只需要在之前二叉搜索树的增删查代码的基础上简单修改即可，增加一个模板参数V，此时我们节点中存储的数据就是键值对<key, value>，所以在树节点类中需要新增一个V类型的成员变量，同时构造函数中也需要增加一个V类型的形参

Insert: 只需增加一个V类型的形参，因为在插入新的树节点时，要new一个<key, value>类型的树节点，其余操作不需要改变

Find：只需要查找键，修改返回值，我们返回树节点，就可以通过树节点得到里面的值

Erase：不需要修改

namespace key_value
{
	template<class K, class V>
	struct BSTreeNode
	{
		BSTreeNode(const K& key, const V& value)
			:_key(key)
			,_value(value)
			, _left(nullptr)
			, _right(nullptr)
		{}
		// 不写默认构造函数、拷贝构造函数等
		// 编译器会自动禁用默认构造函数（因为用户已定义其他构造函数）
		// 若需要禁用拷贝，可显式删除

		K _key;
		V _value;
		BSTreeNode<K, V>* _left;
		BSTreeNode<K, V>* _right;
	};

	template<class K, class V>
	class BSTree
	{
		//typedef BSTreeNode<K> Node;
		using Node = BSTreeNode<K, V>;
	public:
		bool Insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				return true;
			}

			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
				{
					return false; //重复值插入失败
				}
			}

			cur = new Node(key, value);
			if (parent->_key < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			return true;
		}

		Node* Find(const K& key)
		{
			Node* cur = _root;

			while (cur)
			{
				if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else
				{
					return cur;//找到了
				}
			}
			//没找到
			return nullptr;
		}

		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 == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_right == cur)
							{
								// 此时cur->_key > parent->_key
								parent->_right = cur->_right;
							}
							else //parent->_left == cur
							{
								// 此时cur->_key < parent->_key
								parent->_left = cur->_right;
							}
						}

						delete cur;
					}
					else if (cur->_right == nullptr) // 右孩子为空
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_right == cur)
							{
								// 此时cur->_key > parent->_key
								parent->_right = cur->_left;
							}
							else //parent->_left == cur
							{
								// 此时cur->_key < parent->_key
								parent->_left = cur->_left;
							}
						}

						delete cur;
					}
					else // 两个孩子都不为空
					{
						// 替换法删除节点——右子树最小节点替换
						Node* replaceParent = cur;// 要考虑删除根节点时，不能置为nullptr
						Node* replace = cur->_right;
						while (replace->_left)
						{
							replaceParent = replace;
							replace = replace->_left;
						}

						cur->_key = replace->_key;

						if (replace == replaceParent->_left)
						{
							replaceParent->_left = replace->_right;
						}
						else //replace == replaceParent->_right
						{
							// 此时第一个右孩子就是右子树最小节点
							replaceParent->_right = replace->_right;
						}

						delete replace;
					}
					//成功删除
					return true;
				}
			}
			//没找到，删除失败
			return false;
		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
	private:
		void _InOrder(Node* root)
		{
			if (root == nullptr) return;

			_InOrder(root->_left);
			cout << root->_key << ":" << root->_value << endl;
			_InOrder(root->_right);
		}
	private:
		Node* _root = nullptr;
	};

}

我们这里还要显式实现一下拷贝构造和析构，因为这里需要深拷贝资源，且在析构时要把每个new出来的树节点都要释放掉。

拷贝构造:

通过调用 Copy(t._root)，复制原树 t 的根节点，并将新树的根节点 _root 指向复制后的根节点。

因为拷贝构造没有返回值，独立函数 Copy 将递归逻辑封装为一个“黑盒”，只需关注输入（原树的根节点）和输出（新树的根节点），同时：

Copy 函数通常设为私有，因为它是类内部的实现细节，外部无需知道如何复制一棵树。
隐藏实现细节，避免用户误用，同时提高类的封装性。

    BSTree(const BSTree& t)
    {
	    _root = Copy(t._root);
    }
private:
	Node* Copy(Node* root)
	{
		if (root == nullptr) return nullptr;

		Node* newNode = new Node(root->_key, root->_value);
		newNode->_left = Copy(root->_left);
		newNode->_right = Copy(root->_right);
		return newNode;
	}

构造函数：

当我们自己显式定义了拷贝构造函数时，编译器就不会自动生成默认的无参构造函数

这样的话我们的根节点_root就不能实现初始化了，所以我们这里可以手动实现，也可以强制编译器生成默认构造

手动实现：

BSTree() {}

强制编译器生成：

BSTree() = default;//C++11起

赋值重载：

BSTree& operator=(BSTree tmp)
{
	swap(tmp._root, _root);
	return *this;
}

这里直接使用现代写法来实现

析构函数：

    ~BSTree()
    {
	    Destroy(_root);
	    _root = nullptr;
    }
private:
	void Destroy(Node* root)
	{
		if (root == nullptr) return;

		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
	}

这里和拷贝构造一样，封装一个Destroy()函数，递归销毁每个树节点

模拟测试一下场景1：

void test1()
{
	BSTree<string, string> dict;
	dict.Insert("left", "左边");
	dict.Insert("right", "右边");
	dict.Insert("insert", "插入");
	dict.Insert("string", "字符串");
	string str;
	while (cin >> str)
	{
		auto ret = dict.Find(str);
		if (ret)
		{
			cout << "->" << ret->_value << endl;
		}
		else
		{
			cout << "无此单词，请重新输入" << endl;
		}
	}
}

运行结果：

模拟测试一下场景3：

void test2()
{
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
	BSTree<string, int> countTree;
	for (const auto& str : arr)
	{
		// 先查找水果在不在搜索树中
		// 1、不在，说明水果第一次出现，则插入<水果, 1>
		// 2、在，则查找到的结点中水果对应的次数++
		//BSTreeNode<string, int>* ret = countTree.Find(str);
		auto ret = countTree.Find(str);
		if (ret == NULL)
		{
			countTree.Insert(str, 1);
		}
		else
		{
			ret->_value++;
		}
	}
	countTree.InOrder();
}

运行结果：

代码：

namespace key
{
	template<class K>
	struct BSTreeNode
	{
		BSTreeNode(const K& key)
			:_key(key)
			, _left(nullptr)
			, _right(nullptr)
		{}
		// 不写默认构造函数、拷贝构造函数等
		// 编译器会自动禁用默认构造函数（因为用户已定义其他构造函数）
		// 若需要禁用拷贝，可显式删除：
		// BSTreeNode(const BSTreeNode<K>&) = delete;
		// BSTreeNode& operator=(const BSTreeNode<K>&) = delete;

		K _key;
		BSTreeNode<K>* _left;
		BSTreeNode<K>* _right;
	};

	template<class K>
	class BSTree
	{
		//typedef BSTreeNode<K> Node;
		using Node = BSTreeNode<K>;
	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->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false; //重复值插入失败
				}
			}

			cur = new Node(key);
			if (parent->_key < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			return true;
		}

		bool Find(const K& key)
		{
			Node* cur = _root;

			while (cur)
			{
				if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else
				{
					return true;//找到了
				}
			}
			//没找到
			return false;
		}

		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 == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_right == cur)
							{
								// 此时cur->_key > parent->_key
								parent->_right = cur->_right;
							}
							else //parent->_left == cur
							{
								// 此时cur->_key < parent->_key
								parent->_left = cur->_right;
							}
						}

						delete cur;
					}
					else if (cur->_right == nullptr) // 右孩子为空
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_right == cur)
							{
								// 此时cur->_key > parent->_key
								parent->_right = cur->_left;
							}
							else //parent->_left == cur
							{
								// 此时cur->_key < parent->_key
								parent->_left = cur->_left;
							}
						}

						delete cur;
					}
					else // 两个孩子都不为空
					{
						// 替换法删除节点——右子树最小节点替换
						Node* replaceParent = cur;// 要考虑删除根节点时，不能置为nullptr
						Node* replace = cur->_right;
						while (replace->_left)
						{
							replaceParent = replace;
							replace = replace->_left;
						}

						cur->_key = replace->_key;

						if (replace == replaceParent->_left)
						{
							replaceParent->_left = replace->_right;
						}
						else //replace == replaceParent->_right
						{
							// 此时第一个右孩子就是右子树最小节点
							replaceParent->_right = replace->_right;
						}

						delete replace;
					}
					//成功删除
					return true;
				}
			}
			//没找到，删除失败
			return false;
		}

		void InOrder()
		{
			_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;
	};
	void Test()
	{
		int a[] = { 8,3,1,10,6,4,7,14,13 };
		BSTree<int> t;
		for (auto x : a)
		{
			t.Insert(x);
		}
		t.InOrder();
		for (auto x : a)
		{
			t.Erase(x);
			t.InOrder();
		}

	}
}


namespace key_value
{
	template<class K, class V>
	struct BSTreeNode
	{
		BSTreeNode(const K& key, const V& value)
			:_key(key)
			,_value(value)
			, _left(nullptr)
			, _right(nullptr)
		{}
		// 不写默认构造函数、拷贝构造函数等
		// 编译器会自动禁用默认构造函数（因为用户已定义其他构造函数）
		// 若需要禁用拷贝，可显式删除

		K _key;
		V _value;
		BSTreeNode<K, V>* _left;
		BSTreeNode<K, V>* _right;
	};

	template<class K, class V>
	class BSTree
	{
		//typedef BSTreeNode<K> Node;
		using Node = BSTreeNode<K, V>;
	public:
		//BSTree() {}
		BSTree() = default;//C++11起

		BSTree(const BSTree& t)
		{
			_root = Copy(t._root);
		}

		BSTree& operator=(BSTree tmp)
		{
			swap(tmp._root, _root);
			return *this;
		}

		~BSTree()
		{
			Destroy(_root);
			_root = nullptr;
		}

		bool Insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				return true;
			}

			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
				{
					return false; //重复值插入失败
				}
			}

			cur = new Node(key, value);
			if (parent->_key < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			return true;
		}

		Node* Find(const K& key)
		{
			Node* cur = _root;

			while (cur)
			{
				if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else
				{
					return cur;//找到了
				}
			}
			//没找到
			return nullptr;
		}

		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 == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_right == cur)
							{
								// 此时cur->_key > parent->_key
								parent->_right = cur->_right;
							}
							else //parent->_left == cur
							{
								// 此时cur->_key < parent->_key
								parent->_left = cur->_right;
							}
						}

						delete cur;
					}
					else if (cur->_right == nullptr) // 右孩子为空
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_right == cur)
							{
								// 此时cur->_key > parent->_key
								parent->_right = cur->_left;
							}
							else //parent->_left == cur
							{
								// 此时cur->_key < parent->_key
								parent->_left = cur->_left;
							}
						}

						delete cur;
					}
					else // 两个孩子都不为空
					{
						// 替换法删除节点——右子树最小节点替换
						Node* replaceParent = cur;// 要考虑删除根节点时，不能置为nullptr
						Node* replace = cur->_right;
						while (replace->_left)
						{
							replaceParent = replace;
							replace = replace->_left;
						}

						cur->_key = replace->_key;

						if (replace == replaceParent->_left)
						{
							replaceParent->_left = replace->_right;
						}
						else //replace == replaceParent->_right
						{
							// 此时第一个右孩子就是右子树最小节点
							replaceParent->_right = replace->_right;
						}

						delete replace;
					}
					//成功删除
					return true;
				}
			}
			//没找到，删除失败
			return false;
		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
	private:
		void Destroy(Node* root)
		{
			if (root == nullptr) return;

			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
		}

		Node* Copy(Node* root)
		{
			if (root == nullptr) return nullptr;

			Node* newNode = new Node(root->_key, root->_value);
			newNode->_left = Copy(root->_left);
			newNode->_right = Copy(root->_right);
			return newNode;
		}

		void _InOrder(Node* root)
		{
			if (root == nullptr) return;

			_InOrder(root->_left);
			cout << root->_key << ":" << root->_value << endl;
			_InOrder(root->_right);
		}
	private:
		Node* _root = nullptr;
	};

	void test1()
	{
		BSTree<string, string> dict;
		dict.Insert("left", "左边");
		dict.Insert("right", "右边");
		dict.Insert("insert", "插入");
		dict.Insert("string", "字符串");
		string str;
		while (cin >> str)
		{
			auto ret = dict.Find(str);
			if (ret)
			{
				cout << "->" << ret->_value << endl;
			}
			else
			{
				cout << "无此单词，请重新输入" << endl;
			}
		}
	}

	void test2()
	{
		string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
		BSTree<string, int> countTree;
		for (const auto& str : arr)
		{
			// 先查找水果在不在搜索树中
			// 1、不在，说明水果第一次出现，则插入<水果, 1>
			// 2、在，则查找到的结点中水果对应的次数++
			//BSTreeNode<string, int>* ret = countTree.Find(str);
			auto ret = countTree.Find(str);
			if (ret == NULL)
			{
				countTree.Insert(str, 1);
			}
			else
			{
				ret->_value++;
			}
		}
		countTree.InOrder();
	}
}

【C++】18.二叉搜索树

1. 二叉搜索树的概念

2. 二叉搜索树的性能分析

3. 二叉搜索树的实现

3.1 二叉搜索树的插入

3.2 打印测试

3.3 二叉搜索树的查找

3.4 二叉搜索树的删除

4. 二叉搜索树key和key/value使用场景

4.1 key搜索场景：

4.2 key/value搜索场景：

I. 键（Key）与值（Value）的定义

II. 键与值的核心差异

拷贝构造:

构造函数：

赋值重载：

析构函数：

模拟测试一下场景1：

模拟测试一下场景3：

代码：

网站公告

今日签到

热门文章

最新发布