一、二叉排序树的删除

二叉排序树的删除情况比较复杂，有以下三种情况需要考虑。

1. 删除叶子节点 （比如：2,5,9,10）
2. 删除只有一个子树的节点（比如：1）
3. 删除有两个子树的节点 （比如：7,3,10）

分析情况一

删除叶子节点 （比如：2,5,9,10）思路：

分析情况二

删除只有一个子树的节点（比如：1）思路：

分析情况三

删除有两个子树的节点 （比如：7,3,10）思路：

二、代码实现

1.查找相应的节点

/**
 *
 * @param value  希望删除的节点值
 * @return       如果找到返回该节点值，找不到返回null
 */
public TreeNode search(TreeNode node,int value){

    if(root == null){
        return null;
    }

    // 找到的就是这个节点
    if(value == node.getValue()){
        return node;
    }else if(value < node.getValue()){ //如果查找的值小于当前节点向左子树递归查找
        // 判断左子树是否为空
        if(node.getLeftTreeNode() == null){
            return  null;
        }
       return search(node.getLeftTreeNode(),value);
    }else {
        if(node.getRightTreeNode() == null){
            return null;
        }
        return search(node.getRightTreeNode(),value);
    }

}

2.查找节点的父节点

/**
 *  查找节点的父节点
 * @param node   父节点
 * @param value  节点的值
 * @return       父节点
 */
public TreeNode SearchParent(TreeNode node,int value) {
    // 当前树为空树
    if(root == null){
        return null;
    }

     // 如果当前节点就是我们想要删除的节点的父节点，就返回
    if((node.getLeftTreeNode() != null && node.getLeftTreeNode().getValue() == value) ||
            (node.getRightTreeNode() !=null && node.getRightTreeNode().getValue() == value)){
        return node;
    }else {
        // 如果当前节点的值小于当前节点的值，并且当前节点的左子树不为空
        if(  node.getLeftTreeNode() !=null && value < node.getValue()){
            return SearchParent(node.getLeftTreeNode(),value); //左子树递归查找
        }else if( node.getRightTreeNode() !=null && value > node.getValue()){
            return SearchParent(node.getRightTreeNode(),value);//右子树递归查找
        }else {
            return null; // 没有找到父节点
        }
    }
}

3.找到右子树当中的最小值

/**
 * 找到右子树当中的最小值
 *
 * @param node 节点
 * @return     节点最小值
 */
public int delRightTreeMin(TreeNode node){
    //定义遍历的指针
   TreeNode target = node;

   // 循环的查询左子树，就会找到最小值
    while (target.getLeftTreeNode() !=null){
        target = target.getLeftTreeNode();
    }


    // 此时 target 执向最小值
    // 删除最小的节点 //这个地方传值要注意：一定是root
    // 因为如果传的值是parent是没有父节点的，会导致 父节点没有办法和子节点相连
    delNode(root,target.getValue());
    return target.getValue();
}

4.删除方法的实现

/**
 * 删除方法
 * @param node
 * @param value
 */
public void delNode(TreeNode node,int value){
    if(node == null){
        return;
    }
    //1.找到先删除的节点
    TreeNode targetNode = search(node,value);
    //如果没有找到要删除的节点
    if(targetNode == null){
      return;
    }
    //如果我们发现这颗二叉树只有一个节点
    if(node.getLeftTreeNode() == null && node.getRightTreeNode() == null){
        // 删除
        root = null;
        return;
    }

    // 找到targetNode的父节点
    TreeNode parent = SearchParent(node,value);


    //如果要删除的节点是叶子节点
    if(targetNode.getLeftTreeNode() == null && targetNode.getRightTreeNode() == null){
        // 判断targetNode是父节点的左子节点还是右子节点
        if(parent.getLeftTreeNode() !=null && parent.getLeftTreeNode().getValue() == value){
            parent.setLeftTreeNode(null);
        }else if(parent.getRightTreeNode() !=null && parent.getRightTreeNode().getValue() == value){
            parent.setRightTreeNode(null);
        }
    }else if(targetNode.getLeftTreeNode() != null && targetNode.getRightTreeNode() !=null){
        //删除有两颗子树的节点
        //System.out.println(targetNode.getValue());
        int minValue = delRightTreeMin(targetNode.getRightTreeNode());
        targetNode.setValue(minValue);
    }else {  //删除只有一颗子树的节点
        //如果要删除的节点有左子节点
        if(targetNode.getLeftTreeNode() !=null){
            if(parent.getLeftTreeNode().getValue() == value){
                //如果targetNode是parent的左子节点
                parent.setLeftTreeNode(targetNode.getLeftTreeNode());
            }else {  //如果targetNode是parent的右子节点
                parent.setRightTreeNode(targetNode.getLeftTreeNode());
            }
        }else {
            System.out.println("parent:"+parent);
            if(parent.getLeftTreeNode().getValue() == value){
                //如果targetNode是parent的左子节点
                parent.setLeftTreeNode(targetNode.getRightTreeNode());
            }else {//如果targetNode是parent的右子节点
                parent.setRightTreeNode(targetNode.getRightTreeNode());
            }
        }
    }

}