如何在 Java 中从二叉搜索树中"delete"节点？

Question

我在 Java 中制作了一个二叉搜索树，但我在删除节点部分时遇到了麻烦。当节点只有 1 个儿子时，我设法擦除了节点，当它有 2 个儿子时，我有删除的想法，无论如何，当它没有儿子时(当它是叶子时)我使用的方法在 Java 中不起作用。通常，在C++我会将节点分配给"null"，但它在这里不起作用。

if (numberOfSons(node) == 0) {
node= null;
return true;
}

这是处理空部分的代码部分。当我调试它时，它引用了正确的节点并为其分配了 null 值，但是当我返回到我为我的树调用 delete 方法的 Frame 时，节点仍然存在。在 Java 中"清空"对象的正确方法是什么？我认为这里的一切都是一个指针，因此这会起作用，但我认为它没有。

Answer 1

当你null某些东西时，你只需在你所在的范围内进行引用null。它不会影响外面的任何东西。

让我举例解释一下。假设你有一个方法foo：

public void foo(Node node) {
node = null;
if(node == null) {
System.out.println("node is null");
} else {
System.out.println("node is not null");
}
}

现在你这样称呼它：

public void doSomething() {
Node node = new Node();
foo(node);
if(node == null) {
System.out.println("Original node is null");
} else {
System.out.println("Original node is not null");
}   
}

在主机中，你将获得：

node is null
original node in not null

原因是它不是一个指针，而是一个参考。当您null引用时，您只需说"将此引用同义为 null"。这并不意味着该对象被删除，它可能仍然存在于其他地方。无法在 java 中删除对象。您所能做的就是确保没有其他对象指向它们，垃圾回收器将删除这些对象(有时)。

Answer 2

除了重新插入左子树或右子树之外，什么都没有留下。例如：

class BinaryTree<T extends Comparable<T>> {
class Node {
Node left;
Node right;
T value;
}
Node root;
void delete(T soughtValue) {
root = deleteRec(root, soughtValue);
}
Node deleteRec(Node node, T soughtValue) {
if (node == null) {
return null;
}
int comparison = soughtValue.compareTo(node.value);
if (comparison < 0) {
node.left = deleteRec(node.left, soughtValue);
} else if (comparison > 0) {
node.right = deleteRec(node.right, soughtValue);
} else {
if (node.left == null) {
return node.right;
} else if (node.right == null) {
return node.left;
} else {
// Two subtrees remain, do for instance:
// Return left, with its greatest element getting
// the right subtree.
Node leftsRightmost = node.left;
while (leftsRightmost.right != null) {
leftsRightmost = leftsRightmost.right;
}
leftsRightmost.right = node.right;
return node.left;
}
}
return node;
}
}

由于 Java 没有像 C++Node*&中的别名参数 - 一种进出参数，因此我在这里使用deleteRec的结果。在 java 中，任何作为对象变量的函数参数都不会用另一个对象实例更改变量。这是语言设计决策之一，就像单一继承一样。