bool Find(const K& key)
		{
			if (_root == nullptr)
			{
				return false;
			}

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

递归方式实现：

因为实现递归方式需要每次都传一次根节点，所以我们需要封装一个私有函数 _FindR 实现。

思路：

如果是root为空，则返回false。如果非空，先比较查找数key与当前root中的_key的大小，大则从右边开始查找，小则从左边开始查找，层层递归，最后直到找到或者为空返回。

bool FindR(const K& key)
		{
			return _FindR(_root, key);
		}
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;
			}
		}

2. 二叉搜索树的插入

树为空，则直接新增节点，赋值给root指针
树不空，按二叉搜索树性质查找插入位置，插入新节点（一颗二叉搜索树不能存在同样的数据）

代码实现：

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

递归方式实现：

思路：

当我们root为空的时候，直接让root指向新建的节点。非空的时候就一直递归向下。递归的思路还是非常简单的。

bool InsertR(const K& key)
		{
			return _InsertR(_root, 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;
			}
		}

3. 二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：

要删除的结点无孩子结点或者要删除的结点只有右孩子结点：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除
要删除的结点只有左孩子结点：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除
要删除的结点有左、右孩子结点：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题--替换法删除

思路：先找到删除的数据的位置，

删除节点的左节点为空的时候：

a)如果该节点是_root，直接将_root指向删除数据的右节点。

b)不是_root时，还需要删除节点的父节点来接受删除节点的右节点。

右节点为空的时候同理，只是左右位置改变一下。

当左右节点都不为空的时候：

从 cur 的右节点开始一直向左找到最小节点 minRight ，这时候 minRight 还可能有右节点（因为minRight最小所以一定没有了左节点），我们先把 cur 的指向的值改成 minRight 指向的值，然后让 minRight 的父节点 parent 指向自己的右节点。

代码：

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
				{
					//1.左边空
					//2.右边空
					//3.两边都不为空，替换删除
					if (cur->_left == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}

						delete cur;
					}
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}

						delete cur;
					}
					else
					{
						Node* parent = cur;
						Node* minRight = cur->_right;
						while (minRight->_left)
						{
							parent = minRight;
							minRight = minRight->_left;
						}

						cur->_key = minRight->_key;
						if (minRight == parent->_left)
						{
							parent->_left = minRight->_right;
						}
						else
						{
							parent->_right = minRight->_right;
						}
						delete minRight;
					}
					return true;
				}
			}

			return false;
		}

递归实现：

思路：

用值来判断，如果根节点的值小于 key ，那就右节点作为跟继续递归，反之则左节点作为根递归。

如果根节点等于key的时候：a) 如果有一边为空，那么根节点向另一边移动一个，然后删除原根节点。 b）如果两边都不为空，在从根节点的右节点开始向左寻找最小节点 minRight ，然后将root中的值与 minRight 中的值交换，然后根节点的右节点作为根节点继续递归。这样就转化成了在子树中删除对应节点。

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->_right == nullptr)
		{
			root = root->_left;
		}
		else if (root->_left == nullptr)
		{
			root = root->_right;
		}
		else
		{
			Node* minRight = root->_right;
			while (minRight->_left)
			{
				minRight = minRight->_left;
			}
			swap(root->_key, minRight->_key);

			return _EraseR(root->_right, key);
		}
		delete del;
		return true;
	}
}

4. 拷贝构造函数以及重载运算符=的实现

因为每次需要传根节点，所以我们写一个函数copy来实现拷贝功能。

copy函数原理：左右节点向上逐级链接形成一棵越来越大的树。

重载运算符=号：只需要与形参交换根节点，子节点自然也就跟着根节点过来了。

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

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

	Node* newRoot = new Node(root->_key);
	newRoot->_left = Copy(root->_left);
	newRoot->_right = Copy(root->_right);

	return newRoot;
}

5.析构函数

因为销毁需要递归销毁，要传参根节点，我们也需要写一个destroy函数来实现。

先递归删除左右节点，然后删除根节点。

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

	Destory(root->_left);
	Destory(root->_right);

	delete root;
}

二叉搜索树的完整代码：

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

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

	template<class K>
	class BSTree
	{
		typedef BSTreeNode<K> Node;
	public:
		BSTree()
			:_root(nullptr)
		{}

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

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

		~BSTree()
		{
			Destory(_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;
		}

		bool Find(const K& key)
		{
			if (_root == nullptr)
			{
				return false;
			}

			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
				{
					//1.左边空
					//2.右边空
					//3.两边都不为空，替换删除
					if (cur->_left == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}

						delete cur;
					}
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}

						delete cur;
					}
					else
					{
						Node* parent = cur;
						Node* minRight = cur->_right;
						while (minRight->_left)
						{
							parent = minRight;
							minRight = minRight->_left;
						}

						cur->_key = minRight->_key;
						if (minRight == parent->_left)
						{
							parent->_left = minRight->_right;
						}
						else
						{
							parent->_right = minRight->_right;
						}
						delete minRight;
					}
					return true;
				}
			}

			return false;
		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

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

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

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

	private:

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

			Node* newRoot = new Node(root->_key);
			newRoot->_left = Copy(root->_left);
			newRoot->_right = Copy(root->_right);

			return newRoot;
		}

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

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

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

			Destory(root->_left);
			Destory(root->_right);

			delete root;
		}

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

		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->_right == nullptr)
				{
					root = root->_left;
				}
				else if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else
				{
					Node* minRight = root->_right;
					while (minRight->_left)
					{
						minRight = minRight->_left;
					}
					swap(root->_key, minRight->_key);

					return _EraseR(root->_right, key);
				}
				delete del;
				return true;
			}
		}

	private:
		Node* _root = nullptr;
	};
	
}

三、二叉搜索树的KV用法

K就是二叉搜索树的第一个参数key，V就是第二个参数value。通过加入第二个参数，我们可以用二叉搜索树实现很多的功能。例如：翻译单词，输出数字中不同的词语出现的次数。

实现翻译功能

代码：

namespace KV
{
	template<class K, class V>
	struct BSTreeNode
	{
		BSTreeNode* _left;
		BSTreeNode* _right;
		K _key;
		V _value;

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

	template<class K, class V>
	class BSTree
	{
		typedef BSTreeNode<K, V> Node;
	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)
		{
			if (_root == nullptr)
			{
				return nullptr;
			}

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

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

}

void test2()
{
	KV::BSTree<string, string> dict;
	
+	dict.Insert("sort", "排序");
	dict.Insert("apple", "苹果");
	dict.Insert("excellent", "非常好的");
	dict.Insert("outgoing", "外向的");
	dict.Insert("welcome","欢迎");

	string str;
	while (cin >> str)
	{
		KV::BSTreeNode<string, string>* ret = dict.Find(str);
		if (ret)
		{
			cout << ret->_value << endl;
		}
		else
		{
			cout << "查无此单词" << endl;
		}
	}
}

在我们实现翻译单词功能的时候，我们key对应的是英文单词，value对应的就是中文意思。

void test3()
{
	string arr[] = { "苹果", "西瓜", "香蕉", "草莓","苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };

	KV::BSTree<string, int> count_tree;
	for (auto numb : arr)
	{
		KV::BSTreeNode<string, int>* ret = count_tree.Find(numb);
		if (ret == nullptr)
		{
			count_tree.Insert(numb, 1);
		}
		else
		{
			ret->_value++;
		}
	}
	count_tree.InOrder();
}

当我们实现统计次数的功能的时候，这时候的value对应的就是次数，当某个名词已经有了，那么再次插入的时候我们只需要将次数++即可。

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

原始发表：2023-03-01，如有侵权请联系 cloudcommunity@tencent.com 删除

递归