树结构入门教程-二叉树的删除操作

前面两节我们分别学习了二叉树的遍历和查找基本操作,本节我们来学习二叉树的删除节点操作,首先我们来看我们的需求是怎么样的.

二叉树删除需求

要求:
1.如果我们删除的节点是叶子节点,则直接删除该节点
2.如果我们删除的节点是非叶子节点,则删除该子树即可
3.测试:
3.1.我们删除5号叶子节点和3号非叶子节点
首先我们来看我们的二叉树的图,如下图所示:

图.png

按照要求我们需要删除3号非叶子节点和5号叶子节点,关于具体的操作我们来进行简单的分析:

• 首先我们需要考虑一点,就是如果我们的树为空树(也就是只有root节点),那么后面的删除操作就不需要继续了,我们只需要将整个二叉树置为null即可.
• 删除的思路分析:

从上图中可以发现我们的二叉树为单向的,所以我们首先来判断当前的节点是否需要删除节点,而不是去判断当前节点是不是我们要删除的节点,这里可能有点绕,不过没关系,我们接着看:
1.如果当前的左子节点不为null,且左子节点就是我们要删除的节点,我们直接将this.left = null即可,同时返回(结束递归操作)
2.如果当前节点的右子节点不为null,且左子节点就是我们要删除的节点,我们直接将this.right = null即可,同时返回(结束递归操作)
3.如果上述两个过程都没有删除,则我们首先递归左子树删除

4. 如果上述步骤3没有删除掉,则我们进行右子树递归删除

上述就是删除的思路分析,我们结合代码来看

首先来看看HeroNode节点中的删除操作,代码如下:

//节点删除操作
//需求:
//1.如果删除的节点是叶子节点,则直接删除该节点
//2.如果删除的是非叶子节点,则删除该子树

/**
 *
 * @param no 要删除节点的编号
 */
public void deleteNode(int no){
    //1.如果当前的左子节点不为null,且左子节点就是我们要删除的节点,我们直接将this.left = null即可,同时返回(结束递归操作)
    if (this.left !=null && this.left.no == no){
        this.left = null;
        return;
    }
    //2.如果当前节点的右子节点不为null,且左子节点就是我们要删除的节点,我们直接将this.right = null即可,同时返回(结束递归操作)
    if (this.right !=null && this.right.no == no){
        this.right = null;
        return;
    }
    //3.如果上述两个过程都没有删除,则我们首先递归左子树删除
    if (this.left !=null){
        this.left.deleteNode(no);
    }
    //4. 如果上述步骤3没有删除掉,则我们进行右子树递归删除
    if (this.right !=null){
        this.right.deleteNode(no);
    }

}

上述是删除操作的具体过程,接着我们来看看二叉树(BinaryTree)中的具体逻辑处理代码:

//删除节点
public void deleteNode(int no){
    if (root !=null){
        if (root.getNo() == no){ //表示root就是我们要删除的节点,直接将root置null即可
            root =null;
        }else { //递归删除
            root.deleteNode(no);
        }
    }else {
        System.out.println("二叉树为null,不能删除!");
    }
}

还记得我们前面删除的思路分析的第一点,如果我们的树为空树(也就是只有root节点),那么后面的删除操作就不需要继续了,我们只需要将整个二叉树置为null即可.我们在二叉树的定义中判断处理即可,那么按照要求我们来测试分别删除叶子节点5和飞叶子节点3的结果,测试代码如下:

 //二叉树删除测试
    System.out.println("删除前,前序遍历结果为:");
    binaryTree.preOrder();
    binaryTree.deleteNode(5);
    //binaryTree.deleteNode(3);
    System.out.println("删除后,前序遍历结果为:");
    binaryTree.preOrder();

直接看测试结果:

叶子节点删除测试结果图.png

再来看非叶子节点的删除,看是不是直接将整个子树删除了,测试代码如下:

 //二叉树删除测试
    System.out.println("删除前,前序遍历结果为:");
    binaryTree.preOrder();
    //binaryTree.deleteNode(5);
    binaryTree.deleteNode(3);
    System.out.println("删除后,前序遍历结果为:");
    binaryTree.preOrder();

测试结果如下图:

非叶子节点删除测试结果图.png

从测试结果图来看,我们完成了前面的需求,这里有点绕,建议大家通过Dbug的方式来走一遍代码逻辑就清楚了,那么关于二叉树的删除就到这里了.