«Укупоривание» двоичного дерева поиска (удаление всех элементов> колпачок)

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.

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