java 实现排序二叉树的删除

一、二叉排序树的删除

二叉排序树的删除情况比较复杂，有以下三种情况需要考虑
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 value
     */
    public void insert(Integer value) {
        //  新建一个节点
        TreeNode newNode = new TreeNode(value);
        if (root == null) {
            root = newNode;
        } else {
            // 定义一个指针用来遍历二叉树
            TreeNode currentNode = root;
            //定义这个指针的目的是：记录currentNode的前一个位置
            TreeNode parentNode;
            // 有孩子继续循环，一直循环到最后一个节点 和插入的节点比较
            // 大的放到右节点，小于放到左节点
            while (true) {
                //记录currentNode
                parentNode = currentNode;
                // 往右放
                if (newNode.getValue() > currentNode.getValue()) {
                    currentNode = currentNode.getRightTreeNode();
                    if (currentNode == null) {
                        parentNode.setRightTreeNode(newNode);
                        return;
                    }
                } else {
                    // 往左放
                    currentNode = currentNode.getLeftTreeNode();
                    if (currentNode == null) {
                        parentNode.setLeftTreeNode(newNode);
                        return;
                    }
                }
            }
        }
    }

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());
            }
        }
    }

}