“封顶”二叉搜索树(移除所有元素>封顶)

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。如果根节点本身大于cap，则将其设为空。

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;  
}    
}