java - 删除 Java 二叉搜索树中的方法

Question

所以我的界面表明必须注意以下资格:

/**
 * Remove the data element from the tree.
 * 
 * In the case that a node you want to remove has two children
 * replace it with the successor. If the data is null throw 
 * IllegalArgumentException.
 * 
 * @param data The data you want to remove.
 *            
 * @return The data that was removed from the tree. Return null if
 *         the data doesn't exist.
 */
public T remove(T data);

这是我迄今为止完成的一些额外的调试:

public T remove(T data) {
    if (data == null) {
        throw new IllegalArgumentException();
    }
    return removeHelper(data, root);
}

    public T removeHelper(T data, Node<T> node) {
    System.out.println("DATA: " + data);
    System.out.println("NODE: " + node);
    System.out.println(); 

    if (node == null) {
        System.out.println("I should be here last: " + data);
        return data;
    } else if (data.compareTo(node.getData()) < 0) {
        System.out.println("im here");
        removeHelper(data, node.getLeft());
    } else if (data.compareTo(node.getData()) > 0) {
        removeHelper(data, node.getRight());
    } else {
        System.out.println("im here again");
        if (node.getLeft() != null && node.getRight() != null) {
            node.setData(minFromRight(node.getRight()).getData());
            removeHelper(minFromRight(node.getRight()).getData(), node.getRight());
        } else if (node.getLeft() != null) {
            node = node.getLeft();
        } else if (node.getRight() != null) {
            node = node.getRight();
        } else {
            node = null;
            removeHelper(data, node);
        }
    }
    return null;
}

private Node<T> minFromRight(Node<T> toTraverse) {
    if (toTraverse.getLeft() == null) {
        return toTraverse;
    } else if (toTraverse.getLeft() != null) {
        minFromRight(toTraverse.getLeft());
    }
    return null;
}

我已经开始测试叶节点情况，但它们不起作用。难道我做错了什么？我的 BST 的所有其他功能都工作正常并且已经过彻底测试。我只需要得到这个该死的remove()。

Answer 1

我认为问题源于这样一个事实:您试图操纵本地节点变量，认为它会影响树。例如看一下这部分代码:

} else {
     node = null;
     removeHelper(data, node);
}

当你说node = null时，你必须考虑到node并不代表真正的节点，而是你传递的引用的副本称为函数。因此，如果您设置 node = null，您只是说本地 node 变量不再指向树中的节点，而是指向 null。

如果要从树中删除节点，则必须首先引用父节点，然后使用父节点的引用将子节点设置为 null。