树结构入门教程-二叉排序树的删除节点操作

上节我们学习了二叉排序树的创建和遍历操作,这节在上节的基础上我们来学习二叉排序树的删除节点操作,这里的删除操作又分为了非叶子节点和叶子节点的删除,具体如何删除我们一起来学习.

首先我们来看张二叉排序树的图,如下:

二叉排序树的删除分许图.png

首先我们来看最简单的一种删除场景,假设我要删除叶子节点(图中的2,5,9,12),我们该如何处理,来看下具体的删除思路的分析:

• 首先我们需要找到删除的目前节点,这里命名为targetNode
• 接着我们需要找到targetNode的父节点,如 targetNode为节点2,那么它的父节点就是1,这里命名为parent
• 确定targetNode是parent的左子节点还是右子节点
• 最后我们根据上述确认的情况来对应删除即可也就是:
• 1.左子节点的话我们只需要parent.left=null;
• 2.右子节点的话我们只需要parent.right=null;

上述就是叶子节点的删除过程,具体实现我们直接看代码实现:

• 代码实现

所有的操作都是在上节的前提上完成的,所以我这里只写删除操作相管的代码

按照上述的分析我们发现我们在删除叶子节点时需要寻找删除的目标节点targetNode和目标节点的父节点,因此我们需要这两个方法,首先来看寻找删除目标叶子节点的代码(Node中)编写:

   /**
 *
 * @param value 待删除节点的value
 * @return 如果找到,就删除,没找到就返回null
 */
public Node search(int value){
    //这里不用判断节点是否为null,因为我们在Node类中
    if (this.value == value){ //表示找到
        return this;
    }else if (value < this.value){ //表示需要向左递归去找
        if (this.left == null){
            return null;
        }
        return this.left.search(value);
    }else { //表示需要去向右递归去找
        if (this.right == null){
            return null;
        }
        return this.right.search(value);
    }
}

上述代码注释很详细,这里就不多说了,通过上述方法我们我们就能找到删除的目标节点了,接着我们来看目标节点的parent的代码编写,同样是在Node中完成:

  /**
 *
 * @param value 待删除节点的value值
 * @return 如果找到了要删除的节点,则返回该节点的父节点,否则返回null
 */
public Node searchParent(int value){
    //表示找到 this就是我们要找的父节点
    if ((this.left !=null && this.left.value == value)||
            this.right !=null && this.right.value == value ){
        return this;
    }else { //如果要查找的值小于当前节点的值,需要向左递归去找

        if (this.left !=null && value < this.value){
            return this.left.searchParent(value);
        }else if (this.right !=null && value >= this.value){
            return this.right.searchParent(value); //向右递归去找
        }else { //都没有找到的话,返回null
            return null;
        }


    }

}

通过上述方法我们就能找到targetNode的parent节点了,接着我们来看真正的删除操作:

代码在我我们的BinarySortTree中进行编写,具体请看:

//查找要删除的节点
public Node search(int value){
    if (root ==null){
        return null;
    }else {
        return this.root.search(value);
    }
}
//查找父节点
public Node searchParent(int value){
    if (root == null){
        return null;
    }else {
        return this.root.searchParent(value);
    }
}

 //删除方法
public void delete(int value){
    if (root == null){
        return;
    }
    //1.找到需要删除的目标节点targetNode
    Node targetNode = search(value);
    if (targetNode == null){
        return;
    }
    //如果当前二叉树只有一个节点的话
    if (root.left == null && root.right ==null){
        root = null;
        return;
    }
    //2找到targetNode的父节点
    Node parent = searchParent(value);
    //2.1如果删除的是叶子节点
    if (targetNode.left ==null && targetNode.right ==null){
        //判断一下,targetNode是父节点的左子节点还是右子节点
        if (parent.left !=null && value == parent.left.value){ //左子节点
            parent.left = null;
        }else if (parent.right !=null && value == parent.right.value){//右子节点
            parent.right = null;
        }

来看测试代码:

 binarySortTree.delete(2);
    binarySortTree.delete(5);
    binarySortTree.delete(9);
    binarySortTree.delete(12);
    System.out.println("删除节点后~");
    binarySortTree.midOrder();

测试结果如下图所示:

二叉排序树的叶子节点删除测试图.png

上图所展示的是删除之后我们通过中序遍历的结果,接着我们我们来看删除非叶子节点的过程,删除非叶子节点又分为了两种情况:

• 删除只有一棵子树的节点如上图中的1
• 删除有两棵子树的节点如上图中的7,3,10(每一个节点可以称称之为最简单的树)

那么我们先来分析删除有两棵子树的节点,如删除7,3,10剩下的就是只有一颗子树的节点,思路分析如下:

• 首先我们需要找到要删除的目标节点targetNode
• 接着找到要删除节点的父节点parent
• 从目标节点的右子节点中去找到最小的节点
• 用一个临时变量来保存我们找到的最小值
• 删除我们找到的最小节点
• 最后我们让targetNode.value = temp 即可

上述就是删除有两棵子树节点的思路分析,接着我们来看代码实现

我们已经知道关于寻找目标节点和父节点的方法我们已经完成了,此时我们还有需要编写一个寻找右子节点的最小值的方法,代码实现如下:

   /**
 * 返回以node为根节点的二叉排序树的最小节点
 * 同时删除最小的节点值
 * @param node 传入的节点
 * @return
 */
public int deleteRightTreeMin(Node node){
    //创建临时的变量来保存传入的节点
    Node targetNode = node;
    //循环从左子树找最小的节点的值
    while (targetNode.left !=null){
        targetNode = targetNode.left;
    }
    //这时targetNode指向的是最小的节点
    //删除最小节点
    delete(targetNode.value);
    return targetNode.value;
}

接着我们来实现删除的操作过程,代码如下:

//删除方法
public void delete(int value){
    if (root == null){
        return;
    }
    //1.找到需要删除的目标节点targetNode
    Node targetNode = search(value);
    if (targetNode == null){
        return;
    }
    //如果当前二叉树只有一个节点的话
    if (root.left == null && root.right ==null){
        root = null;
        return;
    }
    //2找到targetNode的父节点
    Node parent = searchParent(value);
    //2.1如果删除的是叶子节点
    if (targetNode.left ==null && targetNode.right ==null){
        //判断一下,targetNode是父节点的左子节点还是右子节点
        if (parent.left !=null && value == parent.left.value){ //左子节点
            parent.left = null;
        }else if (parent.right !=null && value == parent.right.value){//右子节点
            parent.right = null;
        }
    }else if (targetNode.left !=null && targetNode.right !=null){ //删除有两颗子树的节点
        int minValue = deleteRightTreeMin(targetNode.right);
        targetNode.value = minValue;
    }

代码是从删除的第一种情况中我们加了一种另外的一种情况,直接测试一把

   binarySortTree.delete(7);
    binarySortTree.delete(3);
    binarySortTree.delete(10);
    System.out.println("删除节点后~");
    binarySortTree.midOrder();

测试结果如下图所示:

二叉排序树的删除有两棵子树节点的测试图.png

我们来看最后一种情况删除一棵子树的节点 如图中的节点1,先看思路分析:

• 首先我们需要找到要删除的目标节点targetNode
• 接着找到要删除节点的父节点parent
• 接着是确定targetNode的子节点是左子节点还是右子节点
• 接着确定targetNode是父节点的左子节点还是右子节点
• 如果targetNode有左子节点且targetNode是parent的左子节点
• 1.我们只需要让parent.left = targetNode.left即可
• 如果targetNode有右子节点且targetNode是parent的左子节点
• 1.我们只需要让parent.left = targetNode.right即可
• 如果targetNode有左子节点且targetNode是parent的右子节点
• 1.我们只需要让parent.right = targetNode.left即可
• 如果targetNode有右子节点且targetNode是parent的右子节点
• 1我们只需要让parent.right = target.right即可

上述就是删除有一颗子树节点的思路分析,看着挺复杂的,其实不然,我们接着用代码来实现次过程:

//删除方法
public void delete(int value){
    if (root == null){
        return;
    }
    //1.找到需要删除的目标节点targetNode
    Node targetNode = search(value);
    if (targetNode == null){
        return;
    }
    //如果当前二叉树只有一个节点的话
    if (root.left == null && root.right ==null){
        root = null;
        return;
    }
    //2找到targetNode的父节点
    Node parent = searchParent(value);
    //2.1如果删除的是叶子节点
    if (targetNode.left ==null && targetNode.right ==null){
        //判断一下,targetNode是父节点的左子节点还是右子节点
        if (parent.left !=null && value == parent.left.value){ //左子节点
            parent.left = null;
        }else if (parent.right !=null && value == parent.right.value){//右子节点
            parent.right = null;
        }
    }else if (targetNode.left !=null && targetNode.right !=null){ //删除有两颗子树的节点
        int minValue = deleteRightTreeMin(targetNode.right);
        targetNode.value = minValue;
    }else { //删除一棵子树的节点
        //如果要删除的节点是有左子节点
        if (targetNode.left !=null) {
            if (parent != null) {
            //如果targetNode是parent的左子节点
            if (parent.left.value == value) {
                parent.left = targetNode.left;
            } else { //如果targetNode是parent的右子节点 (我们的targetNode是有左子节点的)
                parent.right = targetNode.left;
            }
        }else {
                root = targetNode.left;
            }
        }else { //要删除的节点(targetNode)是有右子节点
            if (parent !=null) {
                //如果targetNode是parent的左子节点
                if (parent.left.value == value) {
                    parent.left = targetNode.right;
                } else {//如果targetNode是parent的右子节点 (我们的targetNode是有右子节点的)
                    parent.right = targetNode.right;
                }
            }else {
                root = targetNode.right;
            }

        }
    }
}

上述代码是三种情况合起来的代码最后一个else分支就是我们删除有一棵子树节点的实现过程,注释很详细,就不多说了,我们直接测试一把

   binarySortTree.delete(1);
    System.out.println("删除节点后~");
    binarySortTree.midOrder();

测试结果如下图:

二叉排序树删除有一棵子树节点的测试结果图.png

那么关于二叉排序树的删除操作的相关学习我们就到这了