二叉树删除指定节点

举报
周小末天天开心 发表于 2022/12/31 22:50:50 2022/12/31
【摘要】 二叉树-删除节点(1)如果删除的节点是叶子节点,则删除该节点 。(2)如果删除的节点是非叶子节点,则删除该子树。(3)测试,删除掉5号叶子节点和3号。思路分析(1)首先考虑如果树是空树root,如果只有一个root结点,则等价将二叉树置空。(2)因为我们的二叉树是单向的,所以我们要判断当前结点的子结点是否需要删除结点,而不能去判断当前这个结点是不是需要删除结点。(3)如果当前结点的左子节点不...

二叉树-删除节点

(1)如果删除的节点是叶子节点,则删除该节点 。

(2)如果删除的节点是非叶子节点,则删除该子树。

(3)测试,删除掉5号叶子节点和3号。

思路分析

(1)首先考虑如果树是空树root,如果只有一个root结点,则等价将二叉树置空。

(2)因为我们的二叉树是单向的,所以我们要判断当前结点的子结点是否需要删除结点,而不能去判断当前这个结点是不是需要删除结点。

(3)如果当前结点的左子节点不为空,并且左子节点就是要删除的节点,就将this.left = null;结束递归删除。

(4)如果当前结点的右子节点不为空,并且右子节点就是要删除的节点,就将this.right = null;结束地柜删除。

(5)如果第三步和第四步没有删除结点,那么我们就需要向左子树进行递归删除。

(6)如果第五步也没有删除结点,则应该向右子树进行递归删除。

案例


public class BinaryTreeDemo{

    public static void main(String[] args) {

        //在 BinaryTreeDemo 类增加测试代码:
        //测试一把删除结点
        System.out.println("删除前,前序遍历");
        binaryTree.preOrder(); // 1,2,3,5,4
        binaryTree.delNode(5);
        //binaryTree.delNode(3);
        System.out.println("删除后,前序遍历");
        binaryTree.preOrder(); // 1,2,3,4
    }
}

public void delNode(int no) {

    //如果当前结点的左子节点不为空,并且左子节点就是要删除的节点,就将this.left = null;结束递归删除
    if(this.left != null && this.left.no == no) {
        this.left = null;
        return;
    }
    
    //如果当前结点的右子节点不为空,并且右子节点就是要删除的节点,就将this.right = null;结束地柜删除
    if(this.right != null && this.right.no == no) {
        this.right = null;
        return;
    }
    
    //如果第三步和第四步没有删除结点,那么我们就需要向左子树进行递归删除
    if(this.left != null) {
        this.left.delNode(no);
    }
    
    //如果第五步也没有删除结点,则应该向右子树进行递归删除
    if(this.right != null) {
        this.right.delNode(no);
    }
}

//在 BinaryTree 类增加方法
//删除结点
public void delNode(int no) {
    if(root != null) {
        //如果只有一个 root 结点, 这里立即判断 root 是不是就是要删除结点
        if(root.getNo() == no) {
            root = null;
        } else {
            //递归删除
            root.delNode(no);
        }
    }else{
        System.out.println("空树,不能删除~");
    }
}
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。