概念
二叉查找树是一种数据结构，采用了图的树形结构，数据存储于二叉查找树的各个结点中。
二叉查找树又叫二叉搜索树或二叉排序树。
如图所示，即为一个二叉查找树的示例。
二叉查找树的特点
- 同堆一样，每个节点最多有两个子结点
- 每个结点的值均大于其左子树上任意一个结点的值
- 每个结点的值均小于其右子树上任意一个结点的值
- 查询二叉树中最小值要从顶端开始找他的左子树
- 查询二叉树中最大值要从顶端开始找他的右子树
添加数据
- 首先从二叉查找树的顶端结点开始寻找数字的位置
- 将想要添加的结点的值与该结点的值进行比较
- 若要添加的结点值小于当前结点值则往左移否则右移
- 左移或右移后与其子结点继续比较，重复步骤3进行判断左移还是右移
- 当判断至当前结点的子结点不存在则数据插入完毕
示例1，将数字1插入一个二查找树中。
- 将插入的数据与树的顶端结点进行比较,1<15数据左移
- 左移后，与15的子结点9进行比较，1<9数据左移
- 左移后，与9的子结点3进行比较，1<3数据左移，由于3没有子结点了，所以将1作为新结点添加到左下方
- 至此，1的添加操作就完成了
示例2,将数字4插入一个二叉查找树中。
- 与示例1步骤一样，与二叉树顶端的结点进行比较，由于4<15，数据左移
- 将插入的结点与15的子结点9进行比价，4<9,数据左移
- 将插入的结点与9的子结点3进行比较，4>3，数据右移
- 将插入的结点与3的子结点8进行比较，4>8，数据左移，8没有子结点，所以将4作为新结点添加到左下方
- 至此，4的添加操作完成
删除数据
- 删除结点时，判断要删除的结点是否有子结点，若子结点不存在则直接删除
- 若要删除的结点只有一个子结点，则先删除目标结点，然后将子结点移到被删除结点的位置上即可
- 若删除的结点有多个子结点，则先删除目标结点，然后在被删除结点的左子树中寻找最大结点，最后将最大结点移到被删除结点的位置上，若要移动的结点还有子结点，则递归前面的操作。
- 存在多个子结点时，也可在被删除结点的右子树中寻找最小结点，将其移至被删除结点的位置。
示例1，删除数字28的结点
- 先判断28所在结点是否有子结点
- 28结点无子结点直接删除
示例2,删除结点8
- 结点8有一个子结点，则先删除目标结点8
- 移动目标结点的子结点4移到被删除结点的位置上
示例3，删除结点9
- 删除目标结点
- 在被删除结点的左子树中寻找最大结点
- 找到最大结点为4，将其移至被删除结点的位置
查询数据
- 首先，从二叉树的顶端结点开始往下查找。
- 与添加数据时一样，将要查找的结点和树中的结点进行比较，小于该结点则往左移，否则往右移
示例，查找树中的结点12
- 从二叉查找树的顶端结点开始往下查找，将要查询的结点12与顶端的结点15进行比较,12<15，数据左移
- 左移后，将要查询的结点12与结点15的子结点4进行比较，5<12,数据右移
- 右移后，找到结点12，查询结束
写在最后
- 文中使用的图片源自《我的第一本算法书》，如若侵权，请评论区留言，作者立即删除相关图片。
- 公众号无法外链，如果文中有链接，可点击下方阅读原文查看😊
