Java : BST - removing a node with no children doesn't work

Question

我使用链接节点来表示 BST。 我可以找到一个没有子节点的节点，但该节点的删除方法不起作用:

在我添加一个值为“cat”的节点后，我的 BST 只有一个没有子节点的节点。

我尝试删除“cat”节点，却发现删除方法不起作用——“cat”节点仍然在 BST 中。

有谁知道如何解决这个问题吗？谢谢

public class BinarySearchTree {

Node root;

public BinarySearchTree() {
    root = null;
}

/*
 * Adds the specified node to the BST
 */
public String add(String value) {
    if (root == null) {
        root = new Node(value);
        return value;
    }
    return add(root, value);
}

public String add(Node root, String value) {
    int comparision = value.compareTo(root.data);

    if (comparision < 0) {
        if (root.left != null)
            return add(root.left, value);
        root.left = new Node(value);
        return value;
    }

    if (comparision > 0) {
        if (root.right != null)
            return add(root.right, value);
        root.right = new Node(value);
        return value;
    }
    return value;// not allow duplicate
}

/*
 * Returns true if the string is found in the BST
 */
public boolean contains(String value) {
    return contains(root, value);
}

private boolean contains(Node root, String value) {
    if (root == null) {
        return false;
    }

    int comparison = value.compareTo(root.data);
    if (comparison == 0) {
        return true;
    }
    if (comparison < 0) {
        return contains(root.left, value);
    } else {
        return contains(root.right, value);
    }
}

/*
 * Checks whether the tree is empty or not
 */
public boolean isEmpty() {
    return root == null;
}

/*
 * Removes the specified string from the BST
 */
public boolean remove(String s) {
    if (contains(s) == false) {
        return false;
    }
    return remove(root, s);
}

public boolean remove(Node root, String s) {
    if (root == null) {
        return false;
    }

    int comparision = s.compareTo(root.data);

    if (comparision == 0) {
        if (root.left == null && root.right == null) {
            System.out.println("----------------------------------");
            root = null;
            return true;
        } else if (root.left != null && root.right != null) {
            Node temp = root;
            String min = minValue(temp.right).data;
            root.data = min;
            removemin(root.right);
            return true;
        }
    }

    if (comparision < 0) {
        if (root.left.data.equals(s)) {
            if (root.left.left == null || root.left.right == null) {
                root.left = root.left.right;
                return true;
            }
        }
        return remove(root.left, s);
    }

    if (comparision > 0) {
        if (root.right.data.equals(s)) {
            if (root.right.right == null || root.right.left == null) {
                root.right = root.right.left;
                return true;
            }
        }
        return remove(root.right, s);
    }
    return false;
}

public Node minValue(Node root) {
    if (root.left == null) {
        return root;
    } else
        return minValue(root.left);
}

public static void removemin(Node root) {
    if (root.left == null) {
        root = null;
    } else
        removemin(root.left);
}

/**
 * Prints the inorder traversal of this tree
 */
public void inorderTraversal() {
    inorderTraversal(root);
}

private void inorderTraversal(Node root) {
    if (root == null)
        return;
    inorderTraversal(root.left);
    System.out.print(root.data + " ");
    inorderTraversal(root.right);
}

private class Node {
    String data;
    Node left;
    Node right;

    public Node(String data) {
        this.data = data;
    }
}

/*
 * Returns the height of the tree
 */
public int getHeight() {
    return getHeight(root);
}

private int getHeight(Node root) {
    if (root == null)
        return 0;
    return 1 + Math.max(getHeight(root.left), getHeight(root.right));

}

Answer 1

这部分中的问题出在删除方法上:

if (root.left == null && root.right == null) {
    System.out.println("----------------------------------");
    root = null;
    return true;
}

您期望删除根，但它没有删除，因为 java 是按值传递的。 因此，当您执行 root = null; 时 您将复制的变量设置为 null，而不是 BST 的 root。

这是更新后的remove 方法。为了减少困惑，我已将 root 重命名为 node。

public boolean remove(Node node, String s) {
    if (node == null) {
        return false;
    }

    int comparision = s.compareTo(node.data);

    if (comparision == 0) {
        if (node.left == null && node.right == null) {
            System.out.println("----------------------------------");
            if (node.equals(root))
                this.root = null;
            node = null;
            return true;
        } else if (node.left != null && node.right != null) {
            Node temp = node;
            String min = minValue(temp.right).data;
            node.data = min;
            removemin(node.right);
            return true;
        }
    }

    if (comparision < 0) {
        if (node.left.data.equals(s)) {
            if (node.left.left == null || node.left.right == null) {
                node.left = node.left.right;
                return true;
            }
        }
        return remove(node.left, s);
    }

    if (comparision > 0) {
        if (node.right.data.equals(s)) {
            if (node.right.right == null || node.right.left == null) {
                node.right = node.right.left;
                return true;
            }
        }
        return remove(node.right, s);
    }
    return false;
}

请注意这部分代码，我将 this.root 设置为 null。

if (node.equals(root))
    this.root = null;