二叉树的删除操作-java

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了二叉树的删除操作-java，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1580字，纯文字阅读大概需要3分钟。

内容图文

二叉树的删除操作，其中删除最小值最大值比较容易，就是一直不停的遍历二叉树的左子树和右子树，一直找到没有其左子树和右子树。然后直接将其删除就可以了

一、删除最小值（假定这个二叉树的构造是左节点小于父节点，右节点大于父节点）：从根节点开始遍历，如果有左子树就继续遍历左子树，直至没有左节点为止

代码如下

 public void deleteMin() {

        root = deleteMin(root);

    }

    private Node deleteMin(Node x) {
        if (x.left == null) return x.right;
        x.left = deleteMin(x.left);
        x.size = size(x.left) + size(x.right) + 1;
        return x;
    }

删除最大值也是一样的思想，只不过是遍历右子树：

    public void deleteMax() {

        root = deleteMax(root);

    }

    private Node deleteMax(Node x) {
        if (x.right == null) return x.left;
        x.right = deleteMax(x.right);
        x.size = size(x.left) + size(x.right) + 1;
        return x;
    }

 

二、删除节点操作（假定这个二叉树的构造是左节点小于父节点，右节点大于父节点）：

1. 将指向即将被删除的结点的链接保存为t;
2. 将x指向它的后继结点min（t.right）；
3. 将x的右链接（原本指向一颗所有结点都大于x.key的二叉查找树）指向deleteMin（t.right），也就是在删除后所有结点仍然都大于x.key的子二叉查找树；
4. 将x的左链接（本为空）设为t.left（其下所有的键都小于被删除的结点和他的后继节点）。

 

 代码：

    public void delete(Key key) {
        root = delete(root, key);
    }

    private Node delete(Node x, Key key) {
        if (x == null) return null;

        int cmp = key.compareTo(x.key);
        if      (cmp < 0) x.left  = delete(x.left,  key);
        else if (cmp > 0) x.right = delete(x.right, key);
        else { 
            if (x.right == null) return x.left;
            if (x.left  == null) return x.right;
            Node t = x;
            x = min(t.right);
            x.right = deleteMin(t.right);
            x.left = t.left;
        } 
        x.size = size(x.left) + size(x.right) + 1;
        return x;
    } 

 

内容总结

以上是互联网集市为您收集整理的二叉树的删除操作-java全部内容，希望文章能够帮你解决二叉树的删除操作-java所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---