java 删除排序二叉树的节点

删除节点的操作比增加节点、遍历二叉树要复杂一些。怎么做?

 

一、怎么做

(1)找规律

在写程序之前,我们自己画一棵排序二叉树,手动尝试删除节点,看看有哪些规律。我建立了含有{ 8, 4, 7, 3, 2, 1, 5, 6}元素的排序二叉树。

11

我们尝试手动删除其中的某些节点。

1.删除叶子节点

如果要删除的节点是叶子节点(即没有左右孩子的节点),直接删除即可。不需要其他节点进行补位。

在图中,1、6、7均是叶子节点,可以直接把2、5、4节点的左孩子/右孩子置为null,即可让叶子节点从树中脱离。

代码实现大致为:

要注意这里存在特例:如果树中只有唯一一个根节点,那么这个根节点也是叶子节点。我们知道根节点不存在父节点,如果不做“节点是否为根节点”的判断,这种情况就会从逻辑中漏掉,导致节点删除失败。所以,如果要删除的叶子节点为根节点,直接置为null就好。

除此之外还有个问题,为什么不像处理根节点一样,直接把叶子节点置为null,而要把父节点的“指向”置为null?

我们要理解这里的“删除节点”只是把节点从树中移除而已,并不是“把这个节点摧毁掉”。举个例子:某公司中的人员可以根据其职位形成树。假如某员工离职了,我们会把他从树中移除(把他的上司“指向”他的引用置为null),而不是把这个员工人道毁灭掉(直接把员工设置为null)。

2.删除存在一个子节点的父节点

如果要删除的节点是存在一个子节点的父节点(只有一个左孩子/右孩子),需要其子节点补位。

在图中,2、5均是存在一个子节点的父节点。如果删掉2,1就要补位。如果删掉5,6就要补位,维持二叉排序树的结构(中序遍历出来的结果必须从小到大)。

代码实现大致为:

3.删除存在左右子树的父节点

这种情况是最麻烦的。如果被删除的节点既有左子树而且又有右子树,就需要把左子树的最右边的节点或者右子树最左边的节点提到被删除节点的位置。

为什么要这样做?根据二叉查找树的性质,父节点一定比所有左子树的节点值大,比右子树的节点的值小。所以,在删除父节点时,为了不破坏二叉查找树的平衡性,应当把左子树最大的节点/右子树最小的节点放在父节点的位置。

这就是说,我们在删除父节点前,需要找到左子树最大的节点/右子树最小的节点。其实就是找左子树中最右节点/右子树最左节点。

具体实现代码为:

我们在找到这个补位点,为父节点补位时,也要考虑到这个补位点是否有子节点(补位其实是另一种删除),他的子节点要怎么办?如果存在子节点,也要进行相同的处理(递归的思想)。

(2)具体实现

Tree.java

目的为删除树中的4、5两个节点。运行结果为(为了不占用太多空间,我把纵向排版转成横向):

二、总结

解决数据结构的问题时,要有一定的套路。

发表评论

电子邮件地址不会被公开。 必填项已用*标注