• [C++](17)数据结构：二叉搜索树的操作与实现

    文章目录

    概念

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

    • 若它的左子树不为空，则左子树上所有结点的值都小于根结点的值
    • 若它的右子树不为空，则右子树上所有结点的值都大于根结点的值
    • 它的左右子树也分别为二叉搜索树

    操作

    如图是一棵二叉搜索树：

    img

    1. 查找：如要找7，则可以按路径 8-3-6-7 找到，查找次数不大于二叉树深度。
    2. 删除：找到要删除的结点，要保证删除后依然是一棵二叉搜索树。
    3. 插入：从上往下找，将一个带有新的值的结点插入到合适的位置。本文讲的二叉搜索树是不支持重复数据的版本。

    性能分析

    插入和删除操作都必须先查找，查找效率代表了二叉搜索树的性能。

    对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

    同一组数据，采用不同的插入顺序，得到的二叉搜索树的结构是不一样的。

    img

    最优情况：二叉搜索树为完全二叉树（或者接近完全二叉树），其平均比较次数为： log ⁡ 2 n \log_2n log2​n

    最差情况：二叉搜索树退化为单支树（或者类似单支），其平均比较次数为： n 2 \frac n2 2n​

    退化成单支树的二叉搜索树性能较低，那么能否对其进行干预，保持数的平衡呢？这个需要我们后续学习了AVL树和红黑树来解决。

    实现

    框架

    template<class K>
struct BSTreeNode
{
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;

	K _key;

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:

private:
	Node* _root = nullptr;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    插入

    迭代写法

    • 若插入 key 值，则从根结点向下找，key 比结点大，则往右子树找，比结点小，则往左子树找，直到找到空结点，然后将 key 结点接上去。
    • 接结点需要结点位置的父结点，所以定义一个 cur 和一个 parent 指针。
    • 遇到相同的元素直接返回 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->_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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    为了方便查看结果，这里写个递归的中序遍历：

    因为递归函数需要传入根结点，但是外部无法访问内部的 _root 这里的解决方案是，

    中序遍历的递归函数作为子函数 _Inorder 设为私有，对外提供函数接口 Inorder

    public:
	void InOrder()
	{
		_InOrder(_root);
	}

private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_key << ' ';
		_InOrder(root->_right);
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    中序遍历的结果就是数据的升序排列。

    测试：

    void TestBSTree()
{
	BSTree<int> t;
	int a[] = { 8,3,1,10,6,4,7,14,13 };
	for (auto e : a)
	{
		t.Insert(e);
	}
	t.InOrder();
}
//结果：1 3 4 6 7 8 10 13 14

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    递归写法

    public:
	bool InsertR(const K& key)
	{
		return _InsertR(_root, key);
	}
private:
	bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		if (root->_key < key)
			return _InsertR(root->_right, key);
		else if (root->_key > key)
			return _InsertR(root->_left, key);
		else
			return false;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    逻辑看起来很简单，不过这个写法妙就妙在参数 Node*& root ，当 root == nullptr，也就是找到要插入的位置时，root 就是父结点的左/右指针的别名，root = new Node(key); 就直接把结点成功连接上去了。而不需要额外的 parent 参数。

    查找

    广州大学 数据结构实验报告 实验二 二叉树的操作与实现
    doc 0星 超过10%的资源 210KB
    下载

    迭代写法

    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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    递归写法

    public:
	bool FindR(const K& key)
	{
		return _FindR(_root, key);
	}
private:
	bool _FindR(Node* root, const K& key)
	{
		if (root == nullptr)
			return false;
		if (root->_key < key)
			return _FindR(root->_right, key);
		else if (root->_key > key)
			return _FindR(root->_left, key);
		else
			return true;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    删除

    迭代写法

    删除结点要保证删除后仍是二叉搜索树，分三种情况：

    1. 要删除的结点没有孩子：可以直接删除
    2. 要删除的结点有一个孩子：删除该结点后令它的父结点指向它的孩子结点
    3. 要删除的结点有两个孩子：替换法，把要删除的结点和它左子树的最大结点或右子树的最小结点替换，然后按1、2两种情况删除被替换的结点。
    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 (cur == parent->_left)
					{
						parent->_left = cur->_right;
					}
					else
					{
						parent->_right = cur->_right;
					}
				}
				delete cur;
			}
			else if (cur->_right == nullptr) //只有左孩子
			{
				if (cur == _root) //特殊判断，删除根结点
				{
					_root = cur->_left;
				}
				else
				{
					if (cur == parent->_left)
					{
						parent->_left = cur->_left;
					}
					else
					{
						parent->_right = cur->_left;
					}
				}
				delete cur;
			}
			else //有两个孩子
			{
				//这里选择找右子树的最小结点，其可能有右孩子，删除的时候需要其父结点
				Node* minParent = cur;
				Node* minRight = cur->_right;
				while (minRight->_left) //找右子树的最小结点
				{
					minParent = minRight;
					minRight = minRight->_left;
				}
				cur->_key = minRight->_key; //覆盖要删除的值
				//注意判断minRight是父结点的左孩子还是右孩子
				//因为minRight可能是右子树的根结点，此时就是右孩子，不是根结点，则是左孩子
				if (minParent->_left == minRight)
				{
					minParent->_left = minRight->_right;
				}
				else
				{
					minParent->_right = minRight->_right;
				}
				delete minRight;
			}
			return true;
		}
	}
	return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86

    尤其要注意第三种情况，如下图：

    • 删除3，则是用其右子树的4去替换，最后直接删除6的左结点4。
      • 如果4有个右孩子5，则5需要接到6的左子树上，然后将4删除
    • 删除8，则是用其右子树的根结点的值10去替换，然后将14接到8的右子树上

    img

    递归写法

    public:
	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}
private:
	bool _EraseR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			return false;
		}
		if (root->_key < key)
		{
			return _EraseR(root->_right, key);
		}
		else if (root->_key > key)
		{
			return _EraseR(root->_left, key);
		}
		else //删除
		{
			Node* del = root;
			if (root->_left == nullptr)
			{
				root = root->_right;
				delete del;
			}
			else if (root->_right == nullptr)
			{
				root = root->_left;
				delete del;
			}
			else
			{
				Node* minRight = root->_right;
				while (minRight->_left)
				{
					minRight = minRight->_left;
				}
				swap(root->_key, minRight->_key);
				return _EraseR(root->_right, key);
			}
		}
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    类似于插入的递归写法，这里我们也用了指针的引用 Node*& root 。

    • 重点在于删除逻辑，root 就是父结点的左/右指针的引用，具体是左还是右，已经隐含在里面了，免去了判断它是左孩子还是右孩子的步骤，根结点的情况也不用特别判断。
    • 对于有两个孩子的结点删除，依然要先找右子树的最小结点。然后使用 swap 去替换，注意，迭代写法是覆盖，和这里不同。目的是为了接下来能够通过递归在右子树中找到值被替换成 key 的结点，该结点必没有左孩子，会按照前两种情况进行删除。

    构造和析构、赋值重载

    拷贝构造需要深拷贝，前序构造，后序析构，详关于其递归写法的详细讲解：[数据结构二叉树的遍历_世真的博客-CSDN博客](https://blog.csdn.net/CegghnnoR/article/details/124234117)

    private:
	void DestroyTree(Node* root)
	{
		if (root == nullptr)
			return;
		DestroyTree(root->_left);
		DestroyTree(root->_right);
		delete root;
	}

	Node* CopyTree(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* copyNode = new Node(root->_key);
		copyNode->_left = CopyTree(root->_left);
		copyNode->_right = CopyTree(root->_right);
		return copyNode;
	}
public:
	BSTree() = default; //C++11语法，强制编译器生成默认构造

	BSTree(const BSTree<K>& t)
	{
		_root = CopyTree(t._root);
	}

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    C++ 二叉搜索树(BST)的实现方法
    pdf 0星 超过10%的资源 30KB
    下载

    赋值重载可以采用现代写法：

    	BSTree<K>& operator=(BSTree<K> t)
	{
		swap(_root, t._root);
		return *this;
	}

    • 1
    • 2
    • 3
    • 4
    • 5

    完整代码

    #pragma once
#include 
using namespace std;

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;
private:
	void DestroyTree(Node* root)
	{
		if (root == nullptr)
			return;
		DestroyTree(root->_left);
		DestroyTree(root->_right);
		delete root;
	}

	Node* CopyTree(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* copyNode = new Node(root->_key);
		copyNode->_left = CopyTree(root->_left);
		copyNode->_right = CopyTree(root->_right);
		return copyNode;
	}
public:
	BSTree() = default;

	BSTree(const BSTree<K>& t)
	{
		_root = CopyTree(t._root);
	}

	BSTree<K>& operator=(BSTree<K> t)
	{
		swap(_root, t._root);
		return *this;
	}

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

	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;
	}

	void InOrder()
	{
		_InOrder(_root);
	}

	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 (cur == parent->_left)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
					}
					delete cur;
				}
				else if (cur->_right == nullptr) //只有左孩子
				{
					if (cur == _root) //特殊判断，删除根结点
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}
					delete cur;
				}
				else //有两个孩子
				{
					//这里选择找右子树的最小结点，其可能有右孩子，删除的时候需要其父结点
					Node* minParent = cur;
					Node* minRight = cur->_right;
					while (minRight->_left) //找右子树的最小结点
					{
						minParent = minRight;
						minRight = minRight->_left;
					}
					cur->_key = minRight->_key; //覆盖要删除的值
					//注意判断minRight是父结点的左孩子还是右孩子
					//因为minRight可能是右子树的根结点，此时就是右孩子，不是根结点，则是左孩子
					if (minParent->_left == minRight)
					{
						minParent->_left = minRight->_right;
					}
					else
					{
						minParent->_right = minRight->_right;
					}
					delete minRight;
				}
				return true;
			}
		}
		return false;
	}

	bool FindR(const K& key)
	{
		return _FindR(_root, key);
	}

	bool InsertR(const K& key)
	{
		return _InsertR(_root, key);
	}

	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}

private:
	bool _EraseR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			return false;
		}
		if (root->_key < key)
		{
			return _EraseR(root->_right, key);
		}
		else if (root->_key > key)
		{
			return _EraseR(root->_left, key);
		}
		else
		{
			Node* del = root;
			if (root->_left == nullptr)
			{
				root = root->_right;
				delete del;
			}
			else if (root->_right == nullptr)
			{
				root = root->_left;
				delete del;
			}
			else
			{
				Node* minRight = root->_right;
				while (minRight->_left)
				{
					minRight = minRight->_left;
				}
				swap(root->_key, minRight->_key);
				return _EraseR(root->_right, key);
			}
		}
	}

	bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		if (root->_key < key)
			return _InsertR(root->_right, key);
		else if (root->_key > key)
			return _InsertR(root->_left, key);
		else
			return false;
	}

	bool _FindR(Node* root, const K& key)
	{
		if (root == nullptr)
			return false;
		if (root->_key < key)
			return _FindR(root->_right, key);
		else if (root->_key > key)
			return _FindR(root->_left, key);
		else
			return true;
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_key << ' ';
		_InOrder(root->_right);
	}
private:
	Node* _root = nullptr;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295

    应用

    1. K模型：K模型只有 key 作为关键码，结构中只需要存储 key 即可，关键码即为需要搜索到的值。我们刚刚写的就属于 K 模型的二叉搜索树。

      如给一个单词，判断该单词是狗拼写正确，具体方式如下：

      • 以词库中每个单词作为 key，构建一棵二叉搜索树
      • 在二叉搜索树中搜索该单词是否存在， 存在则拼写正确，否则拼写错误。

    2. KV模型：每一个关键码 key，都有与之对应的值 value，即 键值对。

      • 如英汉词典中的英文与中文形成对应关系，通过英文可以快速找到其对应的中文，英文单词与其对应的中文 就构成一种键值对

      • 再如统计单词次数，统计成功后，给定单词就可以快速找到其出现的次数，单词与其出现的次数就是 就构成一种键值对。

    下面以递归版本为例，将K模型改为KV模型：

    对于结点类，增加一个模板参数，下面的实现也相应的增加。

    template<class K, class V>
struct BSTreeNode
{
	BSTreeNode<K, V>* _left;
	BSTreeNode<K, V>* _right;

	const K _key;
	V _value;

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    template<class K, class V>
class BSTree
{
	typedef BSTreeNode<K, V> Node;
    
private:
	Node* _root = nullptr;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    find 要返回结点指针，因为要支持修改返回的结点的 value：

    public:
	Node* FindR(const K& key)
	{
		return _FindR(_root, key);
	}
private:
	Node* _FindR(Node* root, const K& key)
	{
		if (root == nullptr)
			return nullptr;
		if (root->_key < key)
			return _FindR(root->_right, key);
		else if (root->_key > key)
			return _FindR(root->_left, key);
		else
			return root;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    插入时要增加一个值 value：

    public:
	bool InsertR(const K& key, const V& value)
	{
		return _InsertR(_root, key, value);
	}
private:
	bool _InsertR(Node*& root, const K& key, const V& value)
	{
		if (root == nullptr)
		{
			root = new Node(key, value);
			return true;
		}
		if (root->_key < key)
			return _InsertR(root->_right, key, value);
		else if (root->_key > key)
			return _InsertR(root->_left, key, value);
		else
			return false;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    测试：

    我们插入几个词，这就相当于一个小词典了，然后输入单词进行查找。

    void test()
{
	BSTree<string, string> ECDict;
	ECDict.InsertR("apple", "苹果");
	ECDict.InsertR("banana", "香蕉");
	ECDict.InsertR("cherry", "樱桃");
	ECDict.InsertR("pear", "梨");

	string str;
	while (cin >> str)
	{
		BSTreeNode<string, string>* ret = ECDict.FindR(str);
		if (ret != nullptr)
		{
			cout << "中文：" << ret->_value << endl;
		}
		else
		{
			cout << "无此单词" << endl;
		}
	}
}
//结果：
//apple
//中文：苹果
//banana
//中文：香蕉
//grape
//无此单词

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
  • 相关阅读:
    给 Helm 提一个 PR，重温开源项目参与过程
    OneDiff加速“图生生”，解锁电商AI图像处理新范式
    【Java】电子病历编辑器源码（云端SaaS服务）
    【网络原理】UDP和TCP协议重点知识汇总
    为什么我的文章就是审核不通过或者不推荐呢？
    5G-A 商用加速，赋能工业互联网
    【每日一好题】这么经典的题你不能不会：矩阵置零
    四轴FPV手动训练进阶步骤
    舵机应该如果选择？讲讲模拟舵机，数字舵机和总线舵机的区别
    Spring让读取和存储Bean更加简单（下篇）——使用注解获取Bean对象
  • 原文地址：https://blog.csdn.net/CegghnnoR/article/details/126058989