时间:2021-05-20
本文实例讲述了Java删除二叉搜索树的任意元素的方法。分享给大家供大家参考,具体如下:
在删除二叉搜索树的任意元素时,会有三种情况:
节点删除之后,将左孩子所在的二叉树取代其位置;连在原来节点父亲元素右节点的位置,比如在图中需要删除58这个节点。
删除58这个节点后,如下图所示:
节点删除之后,将右孩子所在的二叉树取代其位置;连在原来节点的位置,比如在下图中需要删除58这个节点。
删除58这个节点后,如下图所示:
这里需要说明说一下,以上两种情况其实包含了叶子节点情况的,我们可以把叶子节点理解成只有左孩子的节点,也可以把它理解为只有右孩子的节点,只不过左孩子、右孩子为null。
如下图,二叉搜索树包含有左右孩子,假设现需要删除58这个节点。
针对该种情况,分析如下:
我们把58这个节点记为d节点(包含有左子树与右子树),如下图所示:
针对这种节点删除情况需要把左子树与右子树融合起来,融合方法:
从d这节点的左孩子与右孩子中找一个比d节点还要大的节点取代d节点,根据二叉搜索树的性质可知(左边节点<当前节点<右边节点),这个需要被找的节点存在于d节点的右孩子节点中。
寻找规则:
寻找需要被删除节点58(d)的后继的所有元素中,离 58 最近的且比 58 大的节点,在本例中为59这个节点【即右子树中的最小值】,记为s,如下图所示:
删除步骤:
(1)从d的右子树中删除最小值,将删除最小值s后的d的右子树, 变为d后继节点s的右孩子,如下图所示:
(2)将d节点(58节点)的左子树,变为后继节点s(59节点)的左子树,如下图所示:
(3)将后继节点s(59节点)连接到d节点(58节点)父亲节点的右边,删除d节点(58节点)后,后继s节点(59节点)成为新的根,如下图所示:
根据上述的分析,在此基础上进行编码,删除代码如下:
//从二叉搜索树中删除元素为e的节点 public void remove(E e) { root = remove(root, e); } //删除以node为根的二叉搜索树中值为e的节点,递归算法 //返回删除节点后更新的二叉搜索树的根 private Node remove(Node node, E e) { if (node == null) return null; if (e.compareTo(node.e) < 0) {//e<node.e (被删除元素e小于当前节点值e) node.left = remove(node.left, e); return node; } if (e.compareTo(node.e) > 0) {//e>node.e (被删除元素e大于当前节点值e) node.right = remove(node.right, e); return node; } else {//e==node.e (被删除元素e等于当前节点值e) //待删除节点左子树为空情况 if (node.left == null) { Node rightNode = node.right; node.right = null; size--; return rightNode; } //待删除节点右子树为空情况 if (node.right == null) { Node leftNode = node.left; node.left = null; size--; return leftNode; } //左右子树均不为空 //方法:找到比待删除节点大的最小节点,即待删除节点右子树的最小节点 //用这个节点顶替待删除节点的位置 Node successor = minimum(node.right); successor.right = removeMin(node.right); successor.left = node.left; node.left = node.right = null; return successor; } }对于上述代码中的minimum函数,在5.3节中已经实现,此处同样也把代码列出来:
// 寻找二分搜索树的最小元素 public E minimum() { if (size == 0) { throw new IllegalArgumentException("BST is empty"); } Node ninNode = minimum(root); return ninNode.e; } // 返回以node为根的二分搜索树的最小值所在的节点 private Node minimum(Node node) { if (node.left == null) { return node; } //返回相应的节点的左子树的最小值 return minimum(node.left); }源码地址 https://github.com/FelixBin/dataStructure/blob/master/src/BST/BST.java
更多关于java算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》
希望本文所述对大家java程序设计有所帮助。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了Java删除二叉搜索树最大元素和最小元素的方法。分享给大家供大家参考,具体如下:在前面一篇《Java二叉搜索树遍历操作》中完成了树的遍历,这一节中
Java实现的二叉搜索树,并实现对该树的搜索,插入,删除操作(合并删除,复制删除)首先我们要有一个编码的思路,大致如下:1、查找:根据二叉搜索树的数据特点,我们
本文实例讲述了Java二叉搜索树遍历操作。分享给大家供大家参考,具体如下:前言:在上一节Java二叉搜索树基础中,我们对树及其相关知识做了了解,对二叉搜索树做了
二叉树是一种非常重要的数据结构。本文总结了二叉树的常见操作:二叉树的构建,查找,删除,二叉树的遍历(包括前序遍历、中序遍历、后序遍历、层次遍历),二叉搜索树的构
JavaScript中的搜索二叉树实现,供大家参考,具体内容如下二叉搜索树(BST,BinarySearchTree),也称二叉排序树或二叉查找树二叉搜索树是一