二叉搜索树实现删除功能 Java-EW帮帮网

在开始编写删除功能之前，先要编写好searchParent()(寻找父节点)和min()(查找树中最小值)两个函数，后期会在删除功能中使用到。

searchParent()的编写

    /**
     * 
     * @param value
     * @return Node
     */
    public Node searchParent(int value){
        if(root==null) return null;
        Node index = root;
        while (index!=null){
            if ((index.left!=null&&index.left.value==value)||(index.right!=null&&index.right.value==value)){
                return index;
            }else if(index.value>value){
                index = index.left;
            }else {
                index = index.right;
            }
        }
        return null;
    }

用于判断父节点是否为空，以及通过父节点直径指向后面节点来删除指定节点。

min()

    /**
     * 找树当中的最小值
     * @param node
     * @return
     */
    public int min(Node node){
        Node index = node;
        while (index.left!=null){
            index = index.left;
        }
        return index.value;
    }

查找树中的最小值，用于在删除指定元素后重构二叉树时，来代替原来的值。

有了前面两个函数，就可以来实现Tree的删除功能：

    /**
     * 删除
     * @param value
     * @return
     */
    public void delete(int value){
        if(root == null) {
            System.out.println("空树");
            return;
        }
        Node target = Search(value);
        if(target == null){
            System.out.println("没有目标节点");
            return;
        }
        //查找目标节点的父节点
        Node parent = searchParent(value);
        //三种情况
        if (target.left==null&&target.right==null){
            //叶子节点
            //没有父节点
            if(parent==null){
                root=null;
                return;
            }
            //有父节点
            if (parent.left!=null&&parent.left.value==value){
                parent.left = null;
            }else {
                parent.right = null;
            }
    }else if (target.left!=null&&target.right!=null){
            //两颗子树
            int minVal = min(target.right);
            delete(minVal);
            target.value = minVal;
        }else {
            //有一颗子树
            //没有父节点
            if(parent==null) {
                if (parent.left != null) {
                    root = target.left;
                } else {
                    root = target.right;
                }
                return;
            }
            //有父节点
            //判断目标节点是父节点的左孩子
            if(parent.left!=null&&parent.left.value==value){
                if(target.left!=null){
                    parent.left=target.left;
                }else {
                    parent.left = target.right;
                }
            }else {
                if(target.left!=null){
                    parent.right = target.left;
                }else {
                    parent.right = target.right;
                }
            }
        }
    }

这段代码实现了二叉搜索树（Binary Search Tree，BST）中删除指定值节点的功能。下面为你详细解释代码的逻辑：

代码功能概述

该代码定义了一个 delete 方法，其作用是从二叉搜索树里删除具有指定值的节点。若树为空或者指定值的节点不存在，会输出相应提示信息。删除节点时，会依据节点的子节点情况分三种情形处理：叶子节点、有两个子节点、仅有一个子节点。

代码详细解释

1. 方法签名与参数

public void delete(int value)

value：要删除的节点的值。

2. 空树检查

if(root == null) {
    System.out.println("空树");
    return;
}

若树的根节点 root 为 null，就表明树是空的，输出“空树”提示信息并终止方法。

3. 查找目标节点

Node target = Search(value);
if(target == null){
    System.out.println("没有目标节点");
    return;
}

调用 Search 方法查找值为 value 的节点。若未找到，输出“没有目标节点”提示信息并终止方法。

4. 查找目标节点的父节点

Node parent = searchParent(value);

调用 searchParent 方法查找目标节点的父节点。

5. 处理三种删除情况

叶子节点（无左右子节点）

if (target.left==null&&target.right==null){
    // 叶子节点
    // 没有父节点
    if(parent==null){
        root=null;
        return;
    }
    // 有父节点
    if (parent.left!=null&&parent.left.value==value){
        parent.left = null;
    }else {
        parent.right = null;
    }
}

若目标节点是叶子节点，并且没有父节点（即该节点为根节点），把根节点置为 null。
若目标节点有父节点，判断目标节点是父节点的左子节点还是右子节点，然后将对应的子节点引用置为 null。

有两个子节点

else if (target.left!=null&&target.right!=null){
    // 两颗子树
    int minVal = min(target.right);
    delete(minVal);
    target.value = minVal;
}

若目标节点有两个子节点，在其右子树中找出最小的值 minVal。
调用 delete 方法删除右子树中的最小节点。
把目标节点的值更新为右子树中的最小节点的值。

有一个子节点

else {
    // 有一颗子树
    // 没有父节点
    if(parent==null) {
        if (target.left != null) {
            root = target.left;
        } else {
            root = target.right;
        }
        return;
    }
    // 有父节点
    // 判断目标节点是父节点的左孩子
    if(parent.left!=null&&parent.left.value==value){
        if(target.left!=null){
            parent.left=target.left;
        }else {
            parent.left = target.right;
        }
    }else {
        if(target.left!=null){
            parent.right = target.left;
        }else {
            parent.right = target.right;
        }
    }
}

若目标节点只有一个子节点，且没有父节点（即该节点为根节点），把根节点更新为目标节点的子节点。
若目标节点有父节点，判断目标节点是父节点的左子节点还是右子节点，然后将父节点对应的子节点引用更新为目标节点的子节点。

总结

此 delete 方法能依据节点的不同情况正确删除二叉搜索树中的指定节点。不过，代码里调用的 Search、searchParent 和 min 方法并未给出实现，在使用时需要确保这些方法已正确实现。

二叉搜索树实现删除功能 Java