"Capping"二叉搜索树(删除所有元素>上限)

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)一样调用它。

Answer 2

这应该有效。我们将首先找到更大的节点，然后将父链接更新为 null。如果根节点本身大于上限，则将其为 null。

boolean capValue(Node node) 
{
if (node == null)
    return false;
if (node.element > cap) {
node = null;
return true;            
}
else {// node.element < cap 
     if(capValue(node.right))
     node.right=null;
     return false;  
}    
}