Java中怎么实现二叉树删除

Java中怎么实现 二叉树删除,相信很多没有经验的人对此束手无策,为此本文总结了问题出现的原因和解决方法,通过这篇文章希望你能解决这个问题。

双牌ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景,ssl证书未来市场广阔!成为创新互联的ssl证书销售渠道,可以享受市场价格4-6折优惠!如果有意向欢迎电话联系或者加微信:18982081108(备注:SSL证书合作)期待与您的合作!


  二叉树删除要分为三种情况。
  第一种:如果为叶子结点,则可以直接删除,如图一。


Java中怎么实现 二叉树删除


第二种:如果只有左子树或者只有右子树的时候,只要令其左子树或右子树为其父节点的左子树或右子树即可,如图二。


Java中怎么实现 二叉树删除


第三种:如果节点既有左节点,又有右节点,则我们需要先用中序序列中节点的前驱或后序替换该节点,然后删除其前驱或后序节点。此时该节点的前驱或后序节点必然是没有右孩子或者左孩子的节点,删除方法可以参照第二种,如图三。


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中怎么实现 二叉树删除的方法了吗?如果还想学到更多技能或想了解更多相关内容,欢迎关注创新互联行业资讯频道,感谢各位的阅读!


本文名称:Java中怎么实现二叉树删除
本文地址:http://myzitong.com/article/pipiji.html