java数据结构和算法——二叉排序树的删除

一、二叉排序树删除结点的思路图解

• 第一种情况:删除叶子节点 (如下图的 2, 5, 9, 12 节点)
• 第二种情况:删除只有一颗子树的节点 (如下图的 1 节点)
• 第三种情况:删除有两颗子树的节点 (如下图的 7, 3, 10 节点 )

二、二叉排序树删除叶子节点的代码示例

1、创建Node结点

package com.rf.springboot01.dataStructure.binarySortTree;

/**
 * @description:  创建Node结点
 * @author: xiaozhi
 * @create: 2020-09-27 21:48
 */
public class Node {
    public int value;//节点的值
    public Node left;//左节点
    public Node right;//右节点

    //构造方法
    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    /**
    * @Description: 一、递归的形式添加结点，注意需要满足二叉排序树的要求
    * @Param:  node 传入的几点
    * @Author: xz
    * @Date: 2020/9/27 21:58
    */
    public void addNode(Node node){
        if(node == null){
            return;
        }
        if(node.value  当前结点的值
            if(this.right == null){ //如果当前结点右子结点为null
                this.right = node;
            }else{//递归的向右子树添加
                this.right.addNode(node);
            }
        }
    }

    /** 
    * @Description: 二、中序遍历二叉排序树
    * @Param:  
    * @Author: xz  
    * @return: 
    * @Date: 2020/9/27 22:09
    */
    public void infixOrder(){
        //左子节点不为null，向左子节点中序遍历
        if(this.left != null){
            this.left.infixOrder();
        }

        //输出当前节点
        System.out.println(this);

        //右子节点不为null，向右子节点中序遍历
        if(this.right != null) {
            this.right.infixOrder();
        }
    }
    /**
    * @Description:  三、查找要删除的结点
    * @Param:  value 传入需要删除的结点的值
    * @Author: xz
    * @return: Node 如果找到返回该结点，否则返回null
    * @Date: 2020/9/28 21:05
    */
    public Node searchDeleteNode(int value){
        if(value == this.value){ //查找的值 == 当前节点的值，说明已找到需要删除的结点
            return this;
        }else if(value  当前结点的值，向右子树递归查找
            if(this.right == null ){//如果右子结点为空,直接返回null
                return null;
            }
            return this.right.searchDeleteNode(value);
        }
    }
    
    /** 
    * @Description: 四、查找要删除结点的父结点
    * @Param:  value 要找到的结点的值
    * @Author: xz  
    * @return: Node 返回的是要删除的结点的父结点，如果没有就返回null
    * @Date: 2020/9/28 21:12
    */
    public Node searchDeleteNodeParentNode(int value){
        //如果当前结点就是要删除的结点的父结点，就返回
        if(this.left != null && this.left.value == value ||
           this.right != null && this.right.value == value){
            return this;
        }else{
            if(value = this.value && this.right != null){//如果查找的值 >= 当前结点的值, 并且当前结点的右子结点不为空
                //向右子树递归查找
                return this.right.searchDeleteNodeParentNode(value);
            }else{
                return null;// 没有找到父结点
            }
        }
    }


}

2、创建二叉排序树类

package com.rf.springboot01.dataStructure.binarySortTree;

/**
 * @description: 创建二叉排序树
 * @author: xiaozhi
 * @create: 2020-09-27 22:16
 */
public class BinarySortTree {
    public Node root;

    public Node getRoot() {
        return root;
    }
    
    /** 
    * @Description:  一、添加二叉排序树节点方法
    * @Param:  node 传入的节点
    * @Author: xz  
    * @Date: 2020/9/27 22:18
    */
    public void addBstNode(Node node){
        if(root == null){//如果root为空则直接让root指向node
            root = node;
        }else{
            root.addNode(node);
        }
    }
    /** 
    * @Description:  二、中序遍历二叉排序树方法
    * @Param:  
    * @Author: xz  
    * @return: 
    * @Date: 2020/9/27 22:25
    */
    public void infixOrder() {
        if(root != null) {
            root.infixOrder();
        } else {
            System.out.println("二叉排序树为空，不能遍历");
        }
    }
    /**
    * @Description:  三、查找要删除的结点
    * @Param:  value 传入需要删除的结点的值
    * @Author: xz
    * @return:  Node 如果找到返回该结点，否则返回null
    * @Date: 2020/9/28 21:40
    */
    public Node searchDelNode(int value){
        if(root ==null){
            return null;
        }else{
            return root.searchDeleteNode(value);
        }
    }

    /**
     * @Description: 四、查找要删除结点的父结点
     * @Param:  value 要找到的结点的值
     * @Author: xz
     * @return: Node 返回的是要删除的结点的父结点，如果没有就返回null
     * @Date: 2020/9/28 21:50
     */
    public Node searchDelNodeParentNode(int value){
        if(root ==null){
            return null;
        }else{
            return root.searchDeleteNodeParentNode(value);
        }
    }
    /** 
    * @Description: 五、删除二叉排序树的结点
    * @Param:  value 传入需要删除的叶子节点的值
    * @Author: xz  
    * @return: 
    * @Date: 2020/9/28 22:10  
    */
    public void delNode(int value){
        if(root ==null ){
            return;
        }else{
            //1.查找要删除的结点targetNode
            Node targetNode= searchDelNode(value);
            if(targetNode ==null){//没有找到要删除的结点
                return;
            }
            if(root.left == null && root.right == null){//二叉排序树只有一个结点
                root = null;//直接把root置空
                return;
            }
            //2、查找节点targetNode的父结点
            Node parentNode=root.searchDeleteNodeParentNode(value);
            if(targetNode.left == null && targetNode.right == null){ //如果要删除的结点是叶子结点
                if(parentNode.left != null && parentNode.left.value == value) { //targetNode是父结点的左子结点
                    parentNode.left = null;
                } else if (parentNode.right != null && parentNode.right.value == value) {//targetNode是父结点的右子结点
                    parentNode.right = null;
                }
            }

        }
    }

}

3、创建二叉排序树测试类

package com.rf.springboot01.dataStructure.binarySortTree;

/**
 * @description: 二叉排序树测试类
 * @author: xiaozhi
 * @create: 2020-09-27 16:42
 */
public class Test {
    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
        BinarySortTree binarySortTree = new BinarySortTree();
        //循环的添加结点到二叉排序树
        for(int i=0;i