java - 如何将 BST 中的删除方法从递归切换为迭代？

Question

我想知道如何将删除方法从递归切换为迭代。我的递归方法运行得非常好，但我所有使其迭代的尝试却并非如此。我哪里出了问题，该如何解决？

这是我的递归方法:

public boolean remove(E someElement) {
    return remove(root, someElement);
}
private boolean remove(Node<E> node, E dataItem) {
    if (node == null) {
        return false;
    }
    int val = dataItem.compareTo(node.data);
    if (val < 0)
        return remove(node.left, dataItem);
    else if (val > 0)
        return remove(node.right, dataItem);
    else
        return false;
}

Answer 1

由于可以获取指向变量的指针，因此在 C/C++ 中迭代执行 BST 操作比在 Java 中容易得多。

在Java中，您需要区别对待在root处找到元素的情况；在所有其他情况下，您正在考虑的节点要么位于其父节点的左侧，要么位于其父节点的右侧；因此，您可以将 C 的指针(或引用)替换为具有父节点的指针和指示当前节点位于父节点的哪一侧的 boolean 值:

public boolean remove(E someElement) {
    if (root == null) {
        return false;
    }
    int val = someElement.compareTo(root.data);
    if (val < 0) {
        return remove(root, false, someElement);
    } else if (val > 0) {
        return remove(root, true, someElement);
    } else {
        root = removeNode(root);
        return true;
    }
}

private boolean remove(Node<E> parent, boolean right, E dataItem) {
    Node<E> node = right ? parent.right : parent.left;
    if (node == null) {
        return false;
    }
    int val = dataItem.compareTo(node.data);
    if (val < 0) {
        return remove(node, false, dataItem);
    } else if (val > 0) {
        return remove(node, true, dataItem);
    } else {
        node = removeNode(node);
        if (right) {
            parent.right = node;
        } else {
            parent.left = node;
        }
        return true;
    }
}

我暂时省略了方法removeNode，现在，我们可以迭代第二个方法:

private boolean remove(Node<E> parent, boolean right, E dataItem) {
    while (true) {
        Node<E> node = right ? parent.right : parent.left;
        if (node == null) {
            return false;
        }
        int val = dataItem.compareTo(node.data);
        if (val < 0) {
            right = false;
        } else if (val > 0) {
            right = true;
        } else {
            node = removeNode(node);
            if (right) {
                parent.right = node;
            } else {
                parent.left = node;
            }
            return true;
        }
        parent = node;
    }
}

现在方法removeNode必须删除顶部节点并在删除后返回新的顶部节点。如果left或right为null，则可以只返回另一个节点，否则，我们必须找到一个节点来替换topnode，它可以是left子树的最右边节点，也可以是right子树的leftmode节点。

private Node<E> removeNode(Node<E> parent) {
    if (parent.left == null) {
        return parent.right;
    } else if (parent.right == null) {
        return parent.left;
    }
    boolean right = random.nextBoolean();
    Node<E> node = right ? parent.right : parent.left;
    Node<E> last = removeLast(node, !right);
    if (last == null) {
        if (right) {
            node.left = parent.left;
        } else {
            node.right = parent.right;
        }
        return node;
    } else {
        last.left = parent.left;
        last.right = parent.right;
        return last;
    }
}

private Node<E> removeLast(Node<E> parent, boolean right) {
    Node<E> node = right ? parent.right : parent.left;
    if (node == null) {
        return null;
    }
    while (true) {
        Node<E> next = right ? node.right : node.left;
        if (next == null) {
            break;
        }
        parent = node;
        node = next;
    }
    if (right) {
        parent.right = node.left;
        node.left = null;
    } else {
        parent.left = node.right;
        node.right = null;
    }
    return node;
}