BST中删除节点（二）

Question

我有 BST，当我想从 BST 中删除节点时，没有任何反应。有人可以解释为什么吗？

这是我的代码：

private void delete(int value, Node node) {
    if (value<node.value) delete(value, node.left);
    else if (value> node.value)
        delete(value, node.right);
    else {
        if (node.left != null && node.right != null) {
            int maxFromLeft = findMax(node.left);
            node.value = maxFromLeft;
            delete(maxFromLeft, node.left);
        } else if (node.left != null) {
            Node trash = node;
            node = node.left;
            trash = null;
        } else if (node.right != null) {
            Node trash = node;
            node = node.right;
            trash = null;
        } else {
            node = null;
        }
    }
}

Answer 1

考虑这部分

if (node.left != null) {
 Node trash = node;
 node = node.left;
 trash = null;
}

您需要删除 node。这什么都不做node = node.left。它只是将一个引用分配给另一个。这个不用太trash = null.

要删除节点，您需要先断开它与父节点的连接，然后将已删除节点的一个子节点连接到父节点，然后将另一个子节点插入到应有的位置！

Answer 2

签名为 void delete(int,Node) 的方法无法工作。考虑当您尝试从只有一个节点的树中删除根时会发生什么：此方法无法删除节点，因为方法参数是按值传递的。

你可以做的是 return 通过这种方法修改后的 BST：

Node delete(int value, Node node) {
    if (value<node.value) node.left = delete(value, node.left);
    else if (value> node.value)
        node.right = delete(value, node.right);
    ...I'll leave the rest as an exercise...
    return node;
}

BST中删除节点（二）

Delete Node in BST (2)

java

recursion

binary-search-tree