二进制搜索树节点删除未删除替换Java

Question

我正在尝试从二叉查找树中删除节点。我可以成功地删除树上的任何其他节点，除了一个特殊的情况。如果目标节点有两个子节点，左边的子节点有右边的子树，我可以定位正确的替换节点，并将值切换到目标节点，但替换节点永远不会被删除。

看看上面的图片，如果我尝试删除17，程序将正确地导航到13，并用13替换17，但它不会像预期的那样删除原来的13。

我附加了我的remove方法和其中引用的方法。

public Node root;    

    public void delete(int value){

    Node node = new Node<>(value);
    Node temp;

    if(root == null) {
        System.out.println("The tree is already empty!");           //tree is empty
        return;     
    }

    if (root.value == node.value) {                                 //Root is target value
        temp = node.left;

        if(temp.right == null){
            node.value = temp.value;
            temp = null;
        }
        else{
            while(temp.right != null){
                temp = temp.right;
            }
            node.value = temp.value;
            temp = null;
        }
        return;
    }
    deleteRec(root, node);
}

private void deleteRec(Node lastRoot, Node node){

    Node temp;

    if (lastRoot.value >= node.value){

        if (lastRoot.left.value == node.value){
            node = lastRoot.left;
            if(node.left == null && node.right == null){        //No children
                node = null;
                lastRoot.left = null;
            }
            else if(node.left == null && node.right != null){   //Right Child
                lastRoot.left = node.right;
                node = null;
                lastRoot.left = null;
            }
            else if(node.left != null && node.right == null){   //Left Child
                lastRoot.left = node.left;
                node = null;
            }
            else{                                               //Two Children

                if(node.left.right == null){
                    node.value = node.left.value;
                    node.left = node.left.left;
                    node.left = null;
                }
                else{
                    node = findReplacement(node.left);
                    lastRoot.left.value = node.value;
                    node.left = null;
                }
            }
        }
        else{
            deleteRec(lastRoot.left, node);
        }
    }
    else{
        if (lastRoot.right.value == node.value){
            node = lastRoot.right;
            if(node.left == null && node.right == null){        //No Children
                node = null;
                lastRoot.right = null;
            }
            else if(node.left == null && node.right != null){   //Right Child
                lastRoot.left = node.right;
                node = null;
                lastRoot.right = null;
            }
            else if(node.left != null && node.right == null){   //Left Child
                lastRoot.right = node.left;
                node = null;
            }
            else{                                               //Two Children

                if(node.left.right == null){
                    node.value = node.left.value;
                    node.left = node.left.left;
                    node.left = null;
                }
                else{
                    node = findReplacement(node.left);
                    lastRoot.left.value = node.value;
                    node.left = null;
                }
            }
        }
        else{
            deleteRec(lastRoot.right, node);
        }
    }
}

private Node findReplacement(Node node) {

    while(node.right != null){
        node = node.right;
    }        
    return node;
}

这是我的Node类：

 public class Node<T> {
    public int value;
    public Node left;
    public Node right;
    public Node parent;

    public Node(int value) {
        this.value = value;
    }
}

Answer 1

考虑代码的这一部分：

Node rep = findReplacement(node.left);
node.value = rep.value;
rep = null;

您正在寻找替换项，并使rep指向它。然后，本质上，您正在做的是使rep指向null。这不会删除节点！父节点仍然指向它！

在您的代码中有几个地方，您正在按照这些思路做一些事情。在这个Java实现中，您需要从树中删除节点的方式是通过更改父节点指向的内容。垃圾收集器负责其他细节。我希望解决这个问题可以帮助您解决问题！