最新消息:

二叉搜索树的CRUD的代码实现

Java goomoon 108浏览 0评论

闲暇之余,手写了个二叉搜索树的代码实现,包括对二叉搜索树的构建、遍历、查询、删除节点的算法。

二叉搜索树

二叉查找树(Binary Search Tree),(又叫:二叉搜索树,二叉排序树),

特点:

  1. 是一棵空树;
  2. 具有下列性质的二叉树:
  • 
2.1、若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 
2.2、若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  • 
2.3、它的左、右子树也分别为二叉排序树。

二叉搜索树作为一种经典的数据结构,它既有链表的快速插入与删除操作的特点,又有数组快速查找的优势;所以应用十分广泛,例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

代码实现

首先,定义一个树的数据节点:

构建二叉搜索树

使用递归的方式,插入节点,代码如下:

测试:依次插入一个数组

用图形表示如下图:
binarytree_2

二叉搜索树的遍历:

根据根节点的遍历顺序,分为前序遍历,中序遍历,后序遍历。

前序遍历

遍历思路:根结点 —> 左子树 —> 右子树

运行结果:

前序遍历:[50,31,12,4,7,22,18,15,30,33,37,36,49,42,81,67,59,74,92,85,84,83,91,86,89,95,98,96]

中序遍历:

遍历思路:左子树–>根节点–>右子树

遍历结果:

中序遍历:[4,7,12,15,18,22,30,31,33,36,37,42,49,50,59,67,74,81,83,84,85,86,89,91,92,95,96,98]

后序遍历:

遍历思路:左子树—>右子树->根节点

遍历结果:

后序遍历:[7,4,15,18,30,22,12,36,42,49,37,33,31,59,74,67,83,84,89,86,91,85,96,98,95,92,81,50]

可以看到,前中后序遍历中,中序遍历是严格的从小到大的排序

查询节点

根据一个数值,查询树的节点,从头结点开始递归查找,比当前节点小,往左查找,比当前节点大,往右查找,直至找到相等节点或者查不到返回null。

删除节点

删除节点是最复杂的,分几种情况:

1、要删除的如果是叶子节点,直接删除

binarytree_3

例如,删除图中的15节点,不会影响其他节点,直接把18节点的left置为空即可。

2、要删除的节点,非叶子节点,左子树为空,则直接用右子节点替换本身所在的位置

例如上图中,删除节点4,只需要把4的父节点(节点12)的left置为其右子节点(节点7)即可。

3、要删除的节点,非叶子节点,右子树为空,则直接用其左子节点替换本身所在的位置。

例如上图中,要删除节点98,只需要把98的父节点(节点95)的right置为其左子节点(节点96)

4、要删除的节点,非叶子节点,且同时存在左右子树

这种情况最复杂,一般来说需要找一个与其数值最接近的节点替换它的位置即可,所以关键有两点:1)寻找最接近的节点,2)替换位置

根据二叉搜索的特性来看,该节点的左子树的最右边的子节点 或者 右子树的最左边的子节点,是最接近被删除节点的,所以一般来说,简单一点,我们直接找右子树的最左子节点。

20210616232416

如上图,如果要删除81节点,则81节点的左子树的最右子节点是74,右子树的最左子节点是83,

我们可以直接用83替换掉81的位置,替换的步骤如下:

1、节点50的right=节点83

2、节点83的left=节点67

3、节点83的right=节点92

4、节点84的left=null ,复杂的情况是,如果节点83还有右子树,则节点84的left应该等于83的右子节点。

实现代码:

由于我们在定义的二叉树是单向链接的关系,查询到某个节点,只知道其子节点,不能往上找,删除节点需要涉及目标节点的父节点的指针的改动,所以我们定义了两个方法:

查找目标节点,并返回其父节点

查找右子树的最左子节点,并返回其父节点

至此,一个简单的二叉搜索的构建、遍历、查找、删除节点的操作均已完毕,我们发现对于二叉树的CRUD操作基本都是 递归遍历,这也是对于树形结构的最直接、最常用的一种方法,需要大家有这种递归的思维。

下面奉上全部的源码,供参考调试:

 

 

转载请注明:刘召考的博客 » 二叉搜索树的CRUD的代码实现

发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址