算法与数据结构(十) 二叉排序树的查找、插入与删除(Swift版)

在上一篇博客中,我们主要介绍了四种查找的方法,包括顺序查找、折半查找、插入查找以及Fibonacci查找。上面这几种查找方式都是基于线性表的查找方式,今天博客中我们来介绍一下基于二叉树结构的查找,也就是我们今天要聊的二叉排序树。今天主要聊的是二叉排序树的查找、插入与删除的内容,二叉排序的创建过程其实就是不断查找与插入的过程,也就是说当我们在创建二叉排序树时,我们会先搜索该节点在二叉排序树中的位置,若没有找到该节点则返回该节点将要插入的父节点,然后将该结点插入。而二叉排序树结点的删除则有些复杂,分为几种情况讨论,下方会给出详细的介绍。

在本篇博客的开头,我们先聊聊什么是二叉排序树。说的直白一些,具有左子树上的值<根节点的值<右子树上的值的二叉树,我们称之为二叉排序树。基于二叉排序树的特点,有结合着中序遍历的特点(中序遍历是先遍历左子树,再遍历根节点,然后遍历右子树),我们不难发现,二叉排序树的中序遍历的结果是从小到大有序的。下方我们会先给出二叉排序树的创建,然后给出二叉排序树的节点删除的代码。废话少说,进入今天博客的主题。

一、二叉排序树的创建

上面也简单的提了一下,二叉排序树的创建无非就是不断查找和插入的过程,当我们查找某个值没有找到时,我们就会将该值插入到二叉排序树中。因为再查找的过程中可以确定该结点要插入的合适位置,所以插入就显得比较简单了。下方我们会先给出二叉排序树查找与插入的示意图,然后再给出相应的代码实现。最后给出中序遍历的结果,观察我们创建的二叉排序树的中序遍历是否是有序的。

1、二叉排序树的查找与插入的示意图

我们要将集合{62, 88, 58, 47, 35, 73, 51, 99, 37, 93}中的元素放入到我们的二叉排序树中去存储,如果对我们创建好的二叉排序树进行中序搜索的话,输出的结果就是上面集合的有序序列。下方就是我们二叉排序树从无到有的完整创建过程。

  • (1)、在初始化状态下我们二叉排序树的根节点为空,我们依次将集合中的元素通过搜索插入到二叉排序树中合适的位置。
  • (2)、首先在二叉排序中进行搜索62的位置,树为空,所以将62存入到二叉排序树的根节点中,及root=(62)。
  • (3)、从集合中取出88,然后查找我们的二叉排序树,发现88大于我们的根节点62,所以将88插入到62节点的右子树中,即(62)->rightChild=(88)。
  • (4)、从集合中取出58,然后从根节点开始查找我们现有的二叉排序树,发现55<62,将55作为62的左结点,即(62)->leftChild=(55)。
  • (5)、从集合中取出47,然后对二叉排序树进行搜索,发现47<55, 所以(55)->leftChild=(47)。
  • (6)、从集合中取出35,再次对二叉排序树进行搜索,发现35又小于47,所以(47)->leftChild=(35)。
  • (7)、从集合中取出73,再次对二叉排序树进行搜索,发现62<73<88, 所以有(88)->leftChild=(73)。
  • 以此类推,要做的事情就是不断从集合中取值,然后对二叉排序树进行查找,找到合适的插入点,然后将相应的节点进行插入,具体步骤就不做过多赘述了。

2.二叉排序树创建的代码实现

接下来我们就来实现二叉排序树创建的代码实现的阶段了,二叉排序树创建分为几个步骤,第一步创建二叉树的结点,第二步二叉排序树的搜索,第三步则是结点的插入。接下来我们将要慢慢的来实现这几个过程。

(1)、二叉排序树的结点类

下方这段代码就是二叉排序树的结点类,该类的结构与之前我们聊二叉树时的结构没什么区别。因为二叉排序树的物理存储结构也是通过二叉链表的形式来组织的,所以下方的BinaryTreeNote中data字段用于存储结点数据,leftChild用来指向左孩子,rightChild用来指向右孩子。二叉树更详细的特性请参考之前发布的博客吧《二叉树的遍历及其线索化》,在此就不做过多赘述了。

(2)、查找二叉排序树代码实现

首先我们先创建一个类,也就是下方的SearchResult类,该类中存储的就是每次查找返回的结果。下方就是对每个结点的介绍:

  • searchNote字段存储的就是查找到的节点,如果未查找到,那么该结点就为空。
  • fatherNote字段就负责存储当前查到节点的父节点,如果该节点为空,那么当前查到的节点就为根节点。如果查找失败,那么我们的结点将要挂到fatherNote节点上。
  • isFound字段负责存储查找的结果,如果二叉排序树中有要查找的节点,那么该字段为true, 如果没有,该字段就为false。

实现完查找结果的存储类后,接下来我们就该实现我们的查找方法了。下方这个searchBST()方法就是我们二叉排序树的查找方法,该方法有三个参数,第一个参数currentRoot是当前二叉排序树的根节点,当然在每次递归遍历时该参数就是每轮递归时子树的根节点。第二个参数是fatherNote,也就是第一个参数currentRoot的父节点,如果currentRoot是整个二叉排序树的根节点的话,那么fatherNote就为空。而第三个参数就是我们要匹配的关键字key。该方法的返回值就是上面SearchResult的对象,该对象中存储的就是查找的相关结果。 

下方代码主要分为下方几步:

  • 首先创建存储查找结果的对象searchResult,以备下方查找时使用。
  • 然后判断currentRoot是否为空,如果为nil说明没有找到key相应的结点。根据此结果设置searchResult的值,并返回searchResult。
  • 紧接着在判断key是否等于currentRoot.data, 如果等于就说明我们找到了相应的结点,根据此结果设置searchResult的值,并返回searchResult对象。
  • 如果没有查找失败,也没有查找成功,我们就比较key是否小于currentRoot.data,如果小于的话,说明我们的key有可能位于左子树上,然后递归查找左子树。
  • 如果key大于currentRoot.data, 那么说明我们的key有可能位于右子树上,递归查找右子树。

(3)、二叉排序树节点的插入操作

二叉排序树的插入操作就显得比较简单了,因为再查找的返回结果中,如果查找失败,那么返回结果中也会有fatherNote。这个FatherNote就是我们将要插入节点的父节点。不过二叉排序树为空树时,查找结果的fatherNote为空,所以我们先判断fatherNote节点是否为空,如果为nil的话,我们就把当前关键字key对应的结点作为二叉排序树的根结点。如果fatherNote不为nil, 那么我们就判断key是否大于fatherNote.data, 如果大于的话,我们就把key作为fatherNote的右结点,否则作为fatherNote的左结点。具体代码如下所示。

(4)、二叉排序树的创建

上面我们实现了二叉排序树的搜索和插入的代码,上面我们不止一次的提到过,二叉排序树的创建就是不断查找和插入的过程。也就是先对要插入的结点key进行查找,如果二叉排序树上没有该key的话,就需要根据查找结果将key插入的二叉排序树中相应的位置上。下方代码就是二叉排序树的创建,就是先查找,如果没找到就插入,具体代码如下所示:

3、创建二叉排序树测试用例

下方就是我们创建二叉排序树的测试用例,会将searchTable数组中的线性元素转换成二叉排序树。BinarySearchTree的参数就是一个线性表,该类中的构造器会调用上面的createBinarySearchTree()的方法来构建二叉排序树。构建完二叉排序树后,对二叉排序树进行中序遍历,下方输出的就是中序遍历的结果,从结果中我们不难看出中序遍历的结果是从小到大有序的,由此可见我们的二叉排序树已正确创建了。如果你不放心,你可以将其先序遍历的结果也输出,进行检查。

二、二叉排序树结点的删除

二叉排序树的结点删除要比二叉排序树结点的插入要复杂一些,不过也并不难,要分为几种情况进行讨论。二叉排序树结点的插入与删除都是在查找的基础上来做的。下方我们就假设找到了我们要删除的结点,根据结点含有的左右结点的个数来进行分类讨论。下方会对这几种情况进行讨论。

1.删除结点的几种情况

(1)、删除结点为叶子结点

删除的结点没有左子树也没有右子树,也就是删除的结点为叶子结点。这种情况下我们有可以细分为两类,一种是该叶子结点就是二叉排序树的根节点,也就是二叉排序树中只有一个节点的情况。只需要将root指针置为空即可。再一种情况是有删除的叶子节点有父节点,直接将父节点连接该删除节点的指针置空即可。示意图如下所示:

(2)、删除的节点只有左子树的情况

该情况也可以细分为两类,一种是该删除的结点没有父节点,也就删除的节点为根节点,我们需要将根节点的root指针指向即将删除结点的左孩子,然后将删除结点的leftChild置空即可。

如果该结点有父节点,那么将父节点相应的孩子指针指向删除节点的左孩子,然后将删除节点的leftChild置空。示意图如下所示: 

(3)、删除的节点只有右子树的情况

该情况也可以细分为两类,一种是该删除的结点没有父节点,也就删除的节点为根节点,我们需要将根节点的root指针指向即将删除结点的右孩子,然后将删除结点的rightChild置空即可。

如果该结点有父节点,那么将父节点相应的孩子指针指向删除节点的右孩子,然后将删除节点的rightChild置空。 示意图如下所示:

(4)、删除的节点既有左子树也有右子树的情况

这种情况会稍微复杂一些,我们采用覆盖,再删除的方式进行解决。也就是曲线解决。直接将有左子树也有右子树的结点干掉似乎不是很好实现,因为这样会破坏二叉排序树的结果。我们可以间接的去做。可以分为下方的两步。

  • 第一步:查找删除结点右子树中最小的那个值,也就是右子树中位于最左方的那个结点。然后将这个结点的值的父节点记录下来。并且将该节点的值赋给我们要删除的结点。也就是覆盖。
  • 第二步:然后将右子树中最小的那个结点进行删除,该节点肯定符合上述三种情况的某一种情况,所以可以使用上述的方法进行删除。

这样一来我们就间接的删除了既有左子树也有右子树的结点。具体示意图如下所示

2.删除结点的代码实现

接下来我们要根据上述的示例图来实现我们的代码。上述将删除的结点分为了四类,其实仔细分析一下,上面的前三种删除结点的情况类似。于是乎我们在代码实现时将前三种删除结点的方法归为一类处理,也就是封装成一个函数来删除有一个或者没有子结点类型的结点。下方的deleteNoteHaveZeroOrOneChild()函数就是相应的方法。该函数有两个参数,第一个就是我们查找到要删除结点的查找结果对象,第二个参数就是该节点的子节点,如果该节点没有子节点的话,那么该参数就为nil。

在下方函数代码中,大体可以分为以下几步:

  • 首先调用setNilForNote()方法将该将要删除的结点的子节点指针置空
  • 然后判断此将要被删除的结点是否是二叉排序树的根节点,如果是的话,就使rootNote指针指向该结点的子结点。
  • 如果要被删除的结点不为根节点的话,我们需要判断要删除结点的值是比其父节点的值是大还是小,如果是小的话,说明要删除的结点是其父节点的左孩子,然后就要把父节点的leftChild指针指向要删除结点的子节点。同理如果删除结点的值要比父节点的值要大,那么就需要将父节点的rightChild指针指向删除结点的子结点。

接下来我们就要实现要删除的结点有两个子节点的情况,这种情况上面我们已经分析过了,实现起来并不复杂。下方这个deleteNoteHaveTwoChild()方法就是删除有两个子节点的情况,该方法的参数是查找的我们要删除的结点的查找结果。其实就是查找,替换和删除三个步骤。下方代码可以分为以下几步:

  • 首先初始化将被删除的结点的右子树的最左边结点的查找结果对象。
  • 然后便利要删除结点的右子树,找到右子树上最左边的结点,也是右子书上最小的那个结点,并将相应信息存储到我们的查找结果对象中。
  • 将右子树中最小的值赋值给我们要删除的结点,然后调用上面的方法将该右子树上的最小结点删除即可。

三、测试用例

经过上的所有步骤,我们的二叉排序树的查找、插入、删除实现完毕。接下来又到了测试的时间了,下方就是我们本篇博客的测试用例。首先我们通过线性表来创建二叉排序,如何依次删除99,35,37,62这些节点,这些节点有叶子节点,有的只有左子树,有的也只有右子树,有的既有左子树也有右子树。

上述代码的输出结果为,从最后一个输出结果我们可以看出,我们要删除的结点62既有左子树也有右子树,所以寻找62右子树上最小的值73,然后将62进行覆盖。最后把62右子树上的73进行释放掉即可。

本篇博客只对二叉排序树的核心代码进行了介绍,完整示例请移步github, 本篇博客中所有代码都会在github上进行分享,分享地址如下所示:

github分享地址:https://github.com/lizelu/DataStruct-Swift/tree/master/BinarySearchTree

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏软件开发 -- 分享 互助 成长

java中大数类的学习

java中提供了大数类BigInteger和BigDecimal分别表示大整数类和大浮点数类,这两个类都在java.math.*包中,因此每次必须在开头处引用该...

27850
来自专栏专注 Java 基础分享

深入理解Java常用类-----时间日期

     除了String这个类在日常的项目中比较常用之外,有关时间和日期的操作也是经常遇到的,本篇就讲详细介绍下Java API中对时间和日期的支持。其实在J...

27880
来自专栏算法与数据结构

PTA 循环单链表区间删除 (15 分)

本题要求实现带头结点的循环单链表的创建和单链表的区间删除。L是一个带头结点的循环单链表,函数ListCreate_CL用于创建一个循环单链表,函数ListDel...

27880
来自专栏猿人谷

线性表简介

学习数据结构 -> 线性表 -> 线性表的介绍     线性表是一种典型的数据结构, 线性结构的基本特点是线性表中的数据元素是有序且有限的, 在线性结构中...

22280
来自专栏desperate633

LintCode 子集题目代码

10120
来自专栏撸码那些事

【图解数据结构】 线性表

27750
来自专栏决胜机器学习

PHP数据结构(十三) ——动态查找表(二叉排序树)

PHP数据结构(十三) ——动态查找表(二叉排序树) (原创内容,转载请注明来源,谢谢) 一、概念 1、动态查找表特点 当对动态查找表进行查...

557100
来自专栏算法与数据结构

数据结构 单链表&顺序表

顺序表: 一般使用数组(C语言中的数组采用顺序存储方式。即连续地址存储)来描述。 优点:在于随机访问元素, 缺点:插入和和删除的时候,需要移动大量的元素。 链表...

594100
来自专栏WD学习记录

Python数据结构与算法笔记(4)

前序遍历中,我们首先访问根节点,然后递归地做左侧子树的前序遍历,随后是右侧子树的递归前序。

13320
来自专栏赵俊的Java专栏

LeetCode 804 Unique Morse Code Words

首先为每个单词的每个字符进行转码, 将转码后的数据放到 Set 集合中, 最后返回 Set 的长度。

11540

扫码关注云+社区

领取腾讯云代金券