本文实例讲述了Java删除二叉搜索树的任意元素的方法。分享给大家供大家参考,具体如下:
一。删除思路分析
在删除二叉搜索树的任意元素时,会有三种情况:
1.1删除只有左孩子的节点
节点删除之后,将左孩子所在的二叉树取代其位置;连在原来节点父亲元素右节点的位置,比如在图中需要删除<代码> 58 这个节点。
删除<代码> 58 这个节点后,如下图所示:
,
,
1.2删除只有右孩子的节点:
节点删除之后,将右孩子所在的二叉树取代其位置;连在原来节点的位置,比如在下图中需要删除<代码> 58 这个节点。
删除58这个节点后,如下图所示:
这里需要说明说一下,以上两种情况其实包含了叶子节点情况的,我们可以把叶子节点理解成只有左孩子的节点,也可以把它理解为只有右孩子的节点,只不过左孩子,右孩子为零 <代码>。
1.3删除包含左右孩子的节点
如下图,二叉搜索树包含有左右孩子,假设现需要删除<代码> 58 这个节点。
针对该种情况,分析如下:
58我们把<代码> 这个节点记为<代码> d 节点(包含有左子树与右子树),如下图所示:
针对这种节点删除情况需要把左子树与右子树融合起来,融合方法:
从<代码> d 这节点的左孩子与右孩子中找一个比<代码> d 节点还要大的节点取代<代码> d 节点,根据二叉搜索树的性质可知(左边节点& lt;当前节点& lt;右边节点),这个需要被找的节点存在于<代码> d 节点的右孩子节点中。
寻找规则:
寻找需要被删除节点58(<代码> d> 这59个节点【即右子树中的最小值,记为<代码> ,如下图所示:
<>强删除步骤:
(1)从<代码> d> s> d> d> s 的右孩子,如下图所示:
(2)将<代码> d 节点58(<代码> 节点)的左子树,变为后继节点<代码> s (<代码> 节59点)的左子树,如下图所示:
(3)将后继节点<代码> s (<代码> 节59点)连接到<代码> d 节点58(<代码> 节点)父亲节点的右边,删除<代码> d 节点58(<代码> 节点)后,后继<代码> s 节点(<代码> 节59点)成为新的根,如下图所示:
二、编码实现二叉搜索树的任意元素
根据上述的分析,在此基础上进行编码,删除代码如下:
