c++实现二叉搜索树（下）

 好久不见啊，baby们，小吉我又回归了，发完这一篇小吉将会有两周时间不会更新blog了（sorry），在小吉没有发blog的日子里大家也要好好学习数据结构与算法哦，还有就是别忘了小吉我❤️
 这篇博客是二叉搜索树系列的最后一篇了，（提前预告一下）难度也相对于前几篇来说比较简单（前提是前几篇的知识大家都熟练掌握了）。让小吉没想到的是二叉搜索树这么受大家喜欢，阅读点赞收藏关注达到历史新高了（哇🎉🎉🎉），小吉在这里十分感谢大家的喜欢和支持（爱你们哦😘）
 好了，又说了这么多的废话，现在我们进入正题

二叉搜索树（范围查询）实现大纲
myless——找小于key（键值）的所有实值
mygreater——找大于key（键值）的所有实值
mybetween——找>=key1且<=key2的所有实值

myless——找<key的所有实值

思路：二叉搜索树使用中序遍历（左值右）的得到的遍历结果是升序的。对二叉搜索树采用中序遍历，当遍历的节点key小于传入的key时，将节点的实值加入到数组中；如果大于，直接结束中序遍历，最后再返回数组

如果有小可爱有点忘记中序遍历了，可以去看小吉的数据结构与算法（c++实现）专栏，里面有一篇讲前中后序遍历的，博客传送门🚪：二叉树遍历之深度优先遍历

代码实现👇：

vector<string> BSTTree::myless(int key)
{
	vector<string> v;
	BSTnode* curr = _root;
	stack<BSTnode*> s;
	while (curr != nullptr || !s.empty())
	{
		if (curr != nullptr)
		{
			s.push(curr);
			curr = curr->_left;
		}
		else
		{
			BSTnode* topval = s.top();
			if (topval->_key < key)
			{
				v.push_back(topval->_value);
			}
			else
			{
				break;
			}
			s.pop();
			curr = topval->_right;
		}
	}
	return v;
}

mygreater——找>key的所有实值

思路：和myless思路大致相同，采用中序遍历，当节点的key>传入的key时，将节点的实值加入到数组中，中序遍历结束返回数组

代码实现👇：

vector<string> BSTTree::mygreater(int key)
{
	vector<string> v;
	BSTnode* curr = _root;
	stack<BSTnode*> s;
	while (curr != nullptr || !s.empty())
	{
		if (curr != nullptr)
		{
			s.push(curr);
			curr = curr->_left;
		}
		else
		{
			BSTnode* topval = s.top();
			if (topval->_key > key)
			{
				v.push_back(topval->_value);
			}
			s.pop();
			curr = topval->_right;
		}
	}
	return v;
}

通过代码我们发现采用中序遍历查找>key的所有实值的效率并不高，要遍历完整个二叉搜索树，以实现myless为借鉴，我们可以采用反向中序遍历（右值左），这样当节点key大于传入的key，将节点的实值加入到数组中；当小于时，直接结束遍历，返回数组

代码实现👇:

vector<string> BSTTree::mygreater2(int key)
{
	vector<string> v;
	BSTnode* curr = _root;
	stack<BSTnode*> s;
	while (curr != nullptr || !s.empty())
	{
		if (curr != nullptr)
		{
			s.push(curr);
			curr = curr->_right;//右
		}
		else
		{
			BSTnode* topval = s.top();
			//值
			if (topval->_key > key)
			{
				v.push_back(topval->_value);
			}
			else
			{
				break;
			}
			s.pop();
			curr = topval->_left;//左
		}
	}
	return v;
}

mybetween——找>=key1且<=key2的所有实值

思路：就是找在一个区间的实值，还是采用中序遍历，就不细说了，和前面两种的实现思路非常相似，这个可以说是前面的结合

代码实现👇：

vector<string> BSTTree::mybetween(int key1, int key2)
{
	vector<string> v;
	BSTnode* curr = _root;
	stack<BSTnode*> s;
	while (curr != nullptr || !s.empty())
	{
		if (curr != nullptr)
		{
			s.push(curr);
			curr = curr->_left;
		}
		else
		{
			BSTnode* topval = s.top();
			if (topval->_key >= key1&&topval->_key <= key2)
			{
				v.push_back(topval->_value);
			}
			else if (topval->_key > key2)
			{
				break;
			}
			s.pop();
			curr = topval->_right;
		}
	}
	return v;
}

 到这里二叉搜索树的所有方法都已经实现了🎉🎉🎉，有没有宝子们觉得意犹未尽啊，下面小吉就推荐几道和二叉搜索树相关的力扣题

二叉搜索树力扣题推荐

🟦删除二叉搜索树中的节点
🟦二叉搜索树中的插入操作
🟦二叉搜索树中的搜索
🟦验证二叉搜索树
🟦二叉搜索树的范围和
🟦前序遍历构造二叉搜索树
🟦二叉搜索树的最近公共祖先
以上👆就是小吉推荐的题，这些题小吉都做过，感觉还是挺不错的，大家可以没事去做做，巩固所学的知识💪
 学习的时间总是短暂的，这篇blog到这里就已经全部结束了，大家课后一定要多敲敲代码，只有敲过代码才能发现问题🧐
 创作不易，还望各位多多支持，不要忘了点赞收藏关注小吉我🌹
最后，小吉的博客能得到大家的喜欢，小吉感觉很开心，十分感谢大家的支持和喜欢🤗

如有错，还望各位大佬多多指点🌹🌹🌹