引言：

上次我们结束了类和对象的收尾，之后我们就要学习一些高级的数据结构，今天我们先来看一个数据结构-- 二叉搜索树。

一：二叉搜索树的概念(性质)

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

若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值。
若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值。
它的左右子树也分别为二叉搜索树。
二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义，后续我们学习map/set/multimap/multiset系列容器底层就是二叉搜索树，其中map/set不支持插入相等值，multimap/multiset支持插入相等值。

左图就是map，不支持插入相同的数据。
右图就是multimap，支持插入相同的数据。
在这里插入图片描述

二：二叉搜索树的性能分析：

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其高度为： log2N。
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其高度为：N。
所以综合而言二叉搜索树增删查改时间复杂度为：O(N)。
在这里插入图片描述
那么这样的效率显然是无法满足我们需求的，我们后续会接着学习二叉搜索树的变形，平衡二叉搜索树（AVL树）和红黑树，才能适用于我们在内存中存储和搜索数据。
另外需要说明的是，二分查找也可以实现o(log2N)级别的查找效率，但是二分查找有两大缺陷：

需要存储在支持下标随机访问的结构中，并且有序。
插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。
因此这里也就体现出了平衡二叉搜索树的价值。

三：模拟实现二叉搜索树

1. 基本框架：

因为二叉搜索树是二叉树衍生而来的，因此其基本结构和二叉树差不多，因此这里我们就不细讲：
在这里插入图片描述

2. 插入数据：

（1）插入原则：

插入的具体过程如下：

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

（2）思路分析：

在这里插入图片描述

（3）补充：

注：由于插入数据的时候牵扯到数据的申请，因此这里的节点结构要提供对于的构造函数来生成节点。

（4）代码实现：

在这里插入图片描述

（5）测试：

注：这里为了测试插入数据，因此我们再实现一个中序遍历。

中序遍历实现：

在这里插入图片描述

可以看到测试结果没有问题。

3. 查找数据：

（1）查找原则：

从根开始比较，查找x，x比根的值大则往右边走查找，x比根值小则往左边走查找。
2. 最多查找高度次，走到空，还没找到，这个值不存在。
3. 如果不支持插入相等的值，找到x即可返回。
4. 如果支持插入相等的值，意味着有多个x存在，一般要求查找中序的第一个x。如下图，查找3，要找到1的右孩子的那个3返回。

在这里插入图片描述

（2）思路分析：

查找的逻辑和插入的逻辑基本上一样，就不再具体分析。

（3）代码实现：

在这里插入图片描述

（4）测试:

在这里插入图片描述
测试没问题。

4. 删除数据：

相较于插入数据，删除数据就比较复杂了，需要考虑各种情况，下面我们来一点点分析：
首先查找元素是否在二叉搜索树中，如果不存在，则返回false。
如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为N）

要删除结点N左右孩子均为空。
要删除的结点N左孩子位空，右孩子结点不为空。
要删除的结点N右孩子位空，左孩子结点不为空。
要删除的结点N左右孩子结点均不为空。
对应以上四种情况的解决方案：
把N结点的父亲对应孩子指针指向空，直接删除N结点（情况1可以当成2或者3处理，效果是一样的）
把N结点的父亲对应孩子指针指向N的右孩子，直接删除N结点。
把N结点的父亲对应孩子指针指向N的左孩子，直接删除N结点。
无法直接删除N结点，因为N的两个孩子无处安放，只能用替换法删除。找N左子树的值最大结点R(最右结点)或者N右子树的值最小结点R(最左结点)替代N，因为这两个结点中任意一个，放到N的位置，都满足二叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转而变成删除R结点，R结点符合情况2或情况3，可以直接删除。