PZY

Enjoy software architecture and programming

16 Sep 2022

二叉查找树图解

二叉查找树(Binary Search Tree),又叫二叉搜索对或二叉排序树,是一种数据结构,采用了图的树形结构。数据存储于二叉查找树的各个结点中,每个结点最多有两个子结点,如下图示。

二叉查找树 结点中的数字是存储的数据,且前提是不存在相同的数字

二叉查找树性质

二叉查找树具有以下性质:

  • 1、每个结点的值均大于其左子树上任意一个结点的值,例如结点 8 大于其左子树上任意一个结点的值;
  • 2、每个结点的值均小于其右子树上任意一个结点的值,例如结点 10 大于其右子树上的 14 和 13;
  • 3、任意结点的左、右子树也分别为二叉查找树;

根据上述性质,我们可以得出推论:二叉查找树的最小结点,要从顶端开始往其左侧的末端寻找,图示二叉查找树的最小值为 1;相反地,二叉查找树的最大结点,要从顶端开始往其右侧的末端寻找,图示二叉查找树的最大值为 14。

添加数据结点

我们尝试往图示二叉查找树添加数字 2,具体演变过程如下:

  1. 从二叉查找树的顶端结点开始寻找添加数字的位置,将要添加的 2 与结点中的值(假设为 x)进行比较,小于 x 则往左移,大于 x 则往右移;
  2. 与 8 比较,由于 2 小于 8,所以将其往左移;
  3. 左移后遇到结点 3,由于 2 小于 3,所以继续将其往左移;
  4. 左移后遇到结点 1,由于 2 大于 1,需要将其往右移,但结点 1 没有子结点了,所以把 2 作为新结点添加;
  5. 根据二叉查找树性质,需要交换结点 1 与 新结点 2 的位置,即结点 2 为结点 3 的左子树,为结点 1 的父结点。

下图为添加数字 2 后的最终二叉查找树:

二叉查找树添加结点

我们尝试再往上图二叉查找树添加数字 15,按照上述演变过程,得到下图所示最终效果:

二叉查找树添加结点2

查找数据结点

在二叉查找树中查找目标结点,是从根结点出发,先将根结点和目标结点做比较:

  • 与添加数据时一样,目标结点与二叉查找树其它结点中的值逐个比较,小于该结点的值则往左子树查找,大于则往右子树查找。
  • 若目标值对应的结点不存在,则查找失败;若当前结点的值和目标结点值相等,则查找成功;

我们来尝试如何在二叉查找树(上图示)中查找结点 6。由于6 < 8,所以往左子树查找;遇到结点 3,因3 > 6,所以往右子树查找,最终找到结点 6。以下为查找过程图示:

二叉查找树查找结点

删除数据结点

删除二叉查找树中已有的结点,必须确保整棵树还是二叉查找树,即删除的同时需要妥善处理它的左、右子树,可以归结为以下 3 种情况:

  1. 如果需要删除的结点是叶子结点(也就是说没有子结点),直接删除该结点即可,整棵树还是二叉查找树。我们尝试删除刚刚添加的结点 15,直接删除它并不会破坏二叉查找树的结构。得到如下图示效果:

二叉查找树删除结点

  1. 如果需要删除的结点只有一个子结点,那么先删除目标结点,然后把子结点移到被删除结点的位置上即可。比如我们尝试删除上图结点 2,得到本文最初二叉查找树图示:

二叉查找树

  1. 如果需要删除的结点有两个子结点,那么先删除目标结点,然后在被删除结点的左子树中寻找最大结点,并将最大结点移到被删除结点的位置上。比如我们尝试删除上图结点 8,得到如下图示效果:

二叉查找树删除结点2

这样,就能在满足二叉查找树性质的前提下删除结点了。如果需要移动的结点还有子结点,就递归执行前面的操作。

有很多数据结构是以二叉查找树为基础,比如“平衡二叉查找树”。这种数据结构可以修正形状不平衡的树,让其始终保持均衡形态,以提高查找效率。

关于二叉查找树新增、查找和删除数据结点的具体算法,限于篇幅原因,将在后续文章进行介绍。