一、二叉搜索树的认识

1.1二叉搜索树的概念

二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，满足以下性质：

• 对于任意节点，若其左子树不为空，则左子树中所有节点的值均小于该节点的值。
• 对于任意节点，若其右子树不为空，则右子树中所有节点的值均大于该节点的值。
• 左右子树也必须是二叉搜索树。

如下图：

在这里插入图片描述

思考： 既然插入一个比根小的值就往左子树插入，插入一个比根大的值就往右子树插入，插入的都是不同的值。那二叉搜索树能不能插入相同的值呢？

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

1.2二叉搜索树的性能分析

为什么要进行二叉搜索树的性能分析？

二叉搜索树的核心功能是高效检索数据，所以性能分析至关重要。我们需要重点评估其查找效率。

在这里插入图片描述

对于第二种情形的二叉树显然是不满足我们的需求的，所以使用二叉搜索树来存储的查找数据是不稳定的，因此要存储数据一般使用的二叉搜索树的变形——平衡二叉搜索树(AVL树)和红黑树来存储和查找数据。(AVL树和红黑树后面介绍)。

二、二叉搜索树的实现

2.1二叉搜索树的整体框架

1、定义结点的结构：

代码语言：javascript

AI代码解释

#include<iostream>
using namespace std;

//定义一个结点
template <class k>
struct BSTNode
{
	k _key;
	BSTNode<k>* _left;
	BSTNode<k>* _right;

	//构造函数
	BSTNode(const k& key)
		:_key(key)
		,_left(nullptr)
		,_right(nullptr)
	{ }
};

2、二叉搜索树的整体框架：

代码语言：javascript

AI代码解释

template<class k>
class BSTree
{
	typedef BSTNode<k> Node;
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);
	}

private:
	Node* _root=nullptr;
};

注意： 二叉搜索树的中序遍历我们不是直接放在公有而是直接给成私有，因为这个接口要传_root，而_root在类外面是不能直接去访问的，但是又要提供这个接口，所以我们选择将他封装成私有(保证封装性)，然后再提供一个外层接口来调用中序遍历这一接口。

2.2二叉搜索树的插入

插入的具体过程如下：

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

代码语言：javascript

AI代码解释

bool Insert(const k& key)
{
	if (_root == nullptr)
	{
		_root = new Node(key);
		return true;
	}


	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (key < cur->_key)
		{
			//小于往左边走
			parent = cur;
			cur = cur->_left;
		}
		else if (key > cur->_key)
		{
			//大于往右边走
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			return false;
		}

	}
	//===================
	//跳出循环此时cur为空
	//先创建一个结点 给cur
	//====================
	cur= new Node(key);
	
	//====================
	//将parent与cur链接起来
	//这时候还要判断cur是parent的左还是右
	//如果传入的key大于parent的key那就插入在右边 小于反之
	//====================
	if (key > parent->_key)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	return true;
}

注意：下面谈到的key均为我们要插入的值！

2.3二叉搜索树的查找

查找过程：

1. 插入的key首先从根结点开始比较，如果插入的key大于根结点的值那么就往根的右子树去查找，如果插入的key小于根的值，那么就往根的左子树去查找。
2. 最多查找整棵树的高度次，如果还没有找到，则这个值不存在。
3. 如果不支持相同的值插入，那么找到与key值相等的结点就可以返回。(本篇文章实现的二叉搜索树不支持相同插入)