如何从二叉树中删除？

Question

我在许多网站上发现了下面的代码，可以从java的二进制搜索树中删除节点。我在这段代码中遇到的问题是，当找到要删除的元素时，在其中一种情况下，它会尝试获取空值。现在，当我们递归调用这个方法时，我认为实际的pos不会被设置为null。如果我是对的，请告诉我。

public void remove (String key, BSTNode pos)
{
    if (pos == null) return;
    if (key.compareTo(pos.key)<0)
        remove (key, pos.leftChild);
    else if (key.compareTo(pos.key)>0)
        remove (key, pos.rightChild);
    else {
        if (pos.leftChild != null && pos.rightChild != null)
        {
            /* pos has two children */
            BSTNode maxFromLeft = findMax (pos.leftChild); //need to make a findMax helper 
            //"Replacing "  pos.key " with " maxFromLeft.key
            pos.key = maxFromLeft.key;
            remove (maxFromLeft.key, pos.leftChild);
        }
        else if(pos.leftChild != null) {
            /* node pointed by pos has at most one child */
            BSTNode trash = pos;
            //"Promoting " pos.leftChild.key " to replace " pos.key
            pos = pos.leftChild;
            trash = null;
        }
        else if(pos.rightChild != null) {
            /* node pointed by pos has at most one child */
            BSTNode trash = pos;
            /* "Promoting " pos.rightChild.key" to replace " pos.key */
            pos = pos.rightChild;
            trash = null;
        }
        else {
            pos = null;
        }
    }
}

Answer 1

是的，你是对的。实际采购订单不会设置为null。

Reason

因为它在每次递归调用时都是空的，所以一旦找到节点，它就会检查你共享的每个代码是否有左或右child.As，当节点没有左和右子节点时，它会被设置为空，这是正确的。

简而言之，如果您要删除的节点是叶子节点，则会将其设置为null。

注意:在你的delete start中还需要做更多的修改，我想说的是你最终需要返回pos，并且在像这样递归调用code.To方法的时候必须分配它。

pos.leftChild=remove (maxFromLeft.key, pos.leftChild);

Answer 2

你是正确的。pos将不会设置为null。它只是在当前堆栈帧中更改局部变量pos的值，但是一旦从该递归级返回，更改就不会持久。