概念
二叉查找树是一种数据结构,采用了图的树形结构,数据存储于二叉查找树的各个结点中。
二叉查找树又叫二叉搜索树或二叉排序树。
如图所示,即为一个二叉查找树的示例。
二叉查找树的特点
- 同堆一样,每个节点最多有两个子结点
- 每个结点的值均大于其左子树上任意一个结点的值
- 每个结点的值均小于其右子树上任意一个结点的值
- 查询二叉树中最小值要从顶端开始找他的左子树
- 查询二叉树中最大值要从顶端开始找他的右子树
添加数据
- 首先从二叉查找树的顶端结点开始寻找数字的位置
- 将想要添加的结点的值与该结点的值进行比较
- 若要添加的结点值小于当前结点值则往左移否则右移
- 左移或右移后与其子结点继续比较,重复步骤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,查询结束
写在最后
- 文中使用的图片源自《我的第一本算法书》,如若侵权,请评论区留言,作者立即删除相关图片。
- 文中如有错误,欢迎在评论区指正,如果这篇文章帮到了你,欢迎点赞和关注😊
- 本文首发于掘金,未经许可禁止转载💌
评论区