java - "Capping"二叉搜索树(删除所有元素> cap)

Question

我想不出执行此操作的递归算法。我的尝试是:

void capValue(Node node) {

    if (node == null)
        return

    if (node.element > cap)
        capValue(node.left)
        node = null;
    else // node.element < cap
        capValue(node.right)
}

但是，您不能只清空节点(至少在 Java 中，我想在其中编写代码)因为这只会将当前指针移动到地址 0，而我们想要摆脱的对象仍然有一个通过树根指向它的“指针路径”，因此不会被垃圾收集。

Answer 1

您可以从函数返回节点。它可以像这样:

Node cap(Node node, int val)
    // There's no node. There's nothing to cap.
    if (node == null)
        return null;
    // The node and it's left subtree should stay
    if node.key <= val {
        node.right = cap(node.right, val);
        return node;
    }
    // The node and it's right subtree must be deleted,
    // so we can go to the left subtree
    return cap(node.left, val);

在代码后面应该像 root = cap(root, val) 一样调用它。