二叉查找树的认识

概念

二叉查找树是一种数据结构，采用了图的树形结构，数据存储于二叉查找树的各个结点中。

二叉查找树又叫二叉搜索树或二叉排序树。

如图所示，即为一个二叉查找树的示例。

二叉查找树的特点

• 同堆一样，每个节点最多有两个子结点
• 每个结点的值均大于其左子树上任意一个结点的值
• 每个结点的值均小于其右子树上任意一个结点的值
• 查询二叉树中最小值要从顶端开始找他的左子树
• 查询二叉树中最大值要从顶端开始找他的右子树

添加数据

• 首先从二叉查找树的顶端结点开始寻找数字的位置
• 将想要添加的结点的值与该结点的值进行比较
• 若要添加的结点值小于当前结点值则往左移否则右移
• 左移或右移后与其子结点继续比较，重复步骤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，查询结束

写在最后

• 文中使用的图片源自《我的第一本算法书》，如若侵权，请评论区留言，作者立即删除相关图片。