二叉搜索树（C++）

一、概念

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

*若他的左子树不为空，则左子树上所有结点的值都小于等于根结点的值

*若他的右子树不为空，则右子树上所有结点的值都大于等于根结点的值

*它的左右子树也分别为二叉搜索树

二叉树可以插入相同的值也可以插入不同的值

2、性能

最优情况：完全二叉树或接近完全二叉树（如上图），其高度为log2N

最坏情况：单支树，其高度为N  如下图

3、二叉树的插入

接下来是代码实现

想打印出树的中序可用如下代码

可由_root是私有不能使用，所以

4、查找

从根开始比较，查找x，x比根的值大则往右查找，x比根值小则往左边查找

如果支持插入相同的值，意味着有多个x存在，一般要求查找中序的第一个x

5、删除

可以分成4种情况，其中前3种是删除节点只有1个孩子或者没有孩子

第4种情况

左为空右为空左右都空

但是有一种特殊情况，若删除的是根，则需要特殊处理

接下来是复杂情况（以右子树的最左节点为例）

代码进行完善

6、二叉搜索树key和key/value使用场景

a、key搜索场景

只有key作为关键词，结构中只要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断key在不在。key的搜索场景实现的二叉树搜索树支持增删查，但是不支持修改，修改key破坏搜索树结构

b、key/value

每一个关键码key，都有与之对应的值value，value可以是任意类型对象。树的结构除了需要存储key还要存储对应的value，增/删/查还是以key为关键字走二叉树搜索树的规则进行比较，可以快速找到key对应的value。此支持修改value不能修改key，