手撕二叉搜索树的建立与算法实现(二叉排序树,二叉查找树)java实现

手撕二叉搜索树的建立与算法实现(二叉排序树,二叉查找树)java实现

目录

前言

1. 设计二叉搜索树类

2.方法的实现

2.1 判断树是否为空

2.2 向树中添加元素

2.3 查找元素

2.4 求最大和最小元素

2.5 删除最大和最小结点

 2.6  删除任意的结点

3 .二叉搜索树的遍历

 3.1 中序遍历

 3.2 先序遍历,后序遍历

3.3 层序遍历 (广度优先)

4.测试 

4.1 测试添加算法创建一棵树

4.2 测试删除

总结:

---

前言

什么是二叉搜索树 : 

1. 二叉搜索树是一颗二叉树

2. 二叉搜索树每个节点的值 :

    大于其左子树所有节点的值,小于其右子树所有节点的值

3. 每一颗子树也是二叉搜索树

4. 在天然的树形结构上,融合了数组(查找快)和链表(增删快)的好处

接着我们来从头建立一颗二叉搜索树

1. 设计二叉搜索树类

 这里我们先定义节点类,并设计它的构造方法

       这里让二叉搜索树类的泛型T 继承 Comparable接口(接口是可以被继承的),目的是为了实现一些比较的算法

然后我们定义搜索树类的成员属性root,实现它的构造方法

这样一个二叉搜索树类已经被设计好了,接着我们来实现它的一些方法

2.方法的实现

2.1 判断树是否为空

我们直接返回这个根的val属性,就可以判断

2.2 向树中添加元素

这里我们使用重载和递归 

       因为我们添加节点的时候,肯定是不需要返回值的,但是我们添加节点后,肯定是要给我们返回一个新树,所以我们采用重载就可以完美解决这个问题  

       另外,树是一种天然的递归结构,所以我们算法大多采用递归来实现

       根据二叉搜索树的特性,我们用递归一步步查找添加节点适合插入的位置

2.3 查找元素

       我们要查找结点,首先要判断结点是否存在,所以我们先给出判断是否存在的方法(调用查找结点的方法,如果返回null,就说明结点不存在)

       然后同样采用递归的方法,如果找到直接返回就行,没找到返回null

2.4 求最大和最小元素

       根据二叉搜索树的特性,我们可以了解到 : 最左边的结点一定是最小元素,最右边的结点一定是最大元素

       根据这样的特点,我们求最大元素,直接一直往右边找,到底就是最大元素(求最小同理)

2.5 删除最大和最小结点

如图,这是一棵二叉搜索树,我们可以看出最大元素是58,最小元素是13

      先来以删除最大元素为例,我们要删除58,那么肯定要把41和50连接起来,这里右边的结点肯定是大于根节点的,我们直接把50 return 就行(直接让 41 的右子树指向 50结点就行)

算法实现:

        这里我们删除58,需要先保存58之前的连接信息,然后我们才能切断连接(步骤顺序错误会造成信息丢失),然后建立新连接即可

 删除最小元素同理,实现代码如下 :

 2.6  删除任意的结点

这里分为两种情况 : 1.叶子结点  2.非叶子结点

1.删除叶子结点

如果我们需要删除  14 这个结点的话,我们只需把13指向null就行

2.删除非叶子结点

删除非叶子结点又可以分为三种

左子树为空(例:上图13结点),右子树为空(上图58结点),左右都不为空(上图22结点)

其中叶子结点就是左右子树都为空的一种,所以我们并不需要单独写删除叶子结点的算法

但是如果我们需要删除  22 这个结点的话,我们则需要考虑 15,33,41这三个结点的连接问题

我们先来看左右子树为空的这二种情况

先通过左图可以看出,我们要删除10结点,只需考虑将10结点删除后,与20结点的连接问题就行

       我们给出算法思路: 先创建10结点的虚拟右结点(rightNode)来保存之前的连接信息,然后我们将10结点的右节点直接指向null(断开连接) , 最后返回rightNode就行(建立新连接)

右边采用同样的思路即可

如果当左右子树都不为null时,算法该怎样实现呢

如下图

        如果我们要删除 d 结点,那么就要考虑之后结点的连接问题,我们这次不能像之前那样直接连接就行了,这次我们要考虑谁来顶替 d 结点的位置

根据二叉搜索树的特性,我们可以看出上图中 53 结点和 59 结点(s结点)都适合替换 d 结点的位置

而53结点就是 d 结点左子树的最大值, 59结点是 d 右子树的最小值,所以两种都可以

那么算法思路如下(我们以连接 s 结点为例),如图 : 

1.我们先找到d 结点右子树的最小值(s结点),用newNode保存

2.删除s结点,然后保存返回的新右子树(可直接调用前面写好的函数)

3.让newNode的left指向要删除结点的left

   newNode的right指向步骤2返回的新树

4.将要删除的结点left和right指向null,然后返回newNode即可

算法思路如上,看下代码实现:

以上就是常用方法的实现

3 .二叉搜索树的遍历  3.1 中序遍历

我们都知道中序遍历是按照从小到大的顺序排列的,我们给出算法

我们用一个ArrayList来存储遍历后的元素,实现如下: 

 3.2 先序遍历,后序遍历

先序遍历:

 后序遍历:

3.3 层序遍历 (广度优先)

这里我们采用队列的思路

我们从根节点开始,先让根节点进队,然后出队获得它的值,然后让它的左右子树进队,然后出队获取值,然后子树的子树.....一直到遍历完

算法实现:

4.测试 

我们以下图这棵树为例来测试我们的算法

4.1 测试添加算法创建一棵树

然后测试四次遍历的结果以及查找算法

运行结果 :

 可见,二叉搜索树被成功创建,接着我们来测试其他算法

4.2 测试删除

结果如下:

由结果可见,最小和最大结点成功被删除

结果如下:

总结:

二叉搜索树(二叉查找树,二叉排序树)是一种很重要的树形结构,它结合了链表(增删快)和数组(查找快)的好处,同时在一定程度上降低了算法的时间复杂度

以上就是本次分享的一颗二叉搜索树的从头建立到测试的全部代码实现,如有疑惑,欢迎指出讨论,谢谢