上海一家做服饰包鞋穿上用品的网站百度知道合伙人答题兼职入口
引言：
上次我们结束了类和对象的收尾，之后我们就要学习一些高级的数据结构，今天我们先来看一个数据结构-- 二叉搜索树。
一： 二叉搜索树的概念(性质)
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值。
- 若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值。
- 它的左右子树也分别为二叉搜索树。
- 二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义，后续我们学习
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，可以直接删除。
（1） 思路分析：
（2）代码实现：
(3) 测试:
5. 销毁
（1）思路分析：
跟之前我们的二叉树销毁一样，只需要后序遍历来销毁即可。
（2） 代码实现：
6. 拷贝构造函数
这里跟之前二叉树的构建一样，只需要一边遍历一边构建即可。
（2）代码实现：
（3）测试：
7. 赋值运算符重载：
（1）思路分析：
这里的赋值运算符重载和之前差不多，还是复用拷贝构造函数。
（2）代码实现：
（3）测试：
