Java中怎么实现 二叉树删除,相信很多没有经验的人对此束手无策,为此本文总结了问题出现的原因和解决方法,通过这篇文章希望你能解决这个问题。
二叉树删除要分为三种情况。
第一种:如果为叶子结点,则可以直接删除,如图一。
第二种:如果只有左子树或者只有右子树的时候,只要令其左子树或右子树为其父节点的左子树或右子树即可,如图二。
第三种:如果节点既有左节点,又有右节点,则我们需要先用中序序列中节点的前驱或后序替换该节点,然后删除其前驱或后序节点。此时该节点的前驱或后序节点必然是没有右孩子或者左孩子的节点,删除方法可以参照第二种,如图三。
输入:待删除元素ele
输出:在二叉查找树中删除ele
代码:
public Object remove(Object ele){
BinTreeNode v = (BinTreeNode)binTSearch(root,ele);if (v==null) return null; //查找失败BinTreeNode del = null; //待删结点BinTreeNode subT = null; //待删结点的子树if (!v.hasLChild()||!v.hasRChild()) //确定待删结点del = v;else{
del = getPredecessor(v);
Object old = v.getData();
v.setData(del.getData());
del.setData(old);
}
startBN = del.getParent(); //待平衡出发点 *//此时待删结点只有左子树或右子树if (del.hasLChild())
subT = del.getLChild();elsesubT = del.getRChild();if (del==root) { //若待删结点为根if (subT!=null) subT.sever();
root = subT;
} elseif (subT!=null){//del为非叶子结点if (del.isLChild()) del.getParent().setLChild(subT);else del.getParent().setRChild(subT);
}else//del为叶子结点del.sever();return del.getData();
}
看完上述内容,你们掌握Java中怎么实现 二叉树删除的方法了吗?如果还想学到更多技能或想了解更多相关内容,欢迎关注亿速云行业资讯频道,感谢各位的阅读!
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
原文链接:https://my.oschina.net/u/3473376/blog/895259