如何从二叉搜索树中删除？

我在许多网站上发现了以下代码，用于从Java的二进制搜索树中删除节点。问题是这个代码的含义是，当被删除的元素被发现后，在这种情况之后，它试图向pos指出null值。现在，当我们递归调用这个方法时，我认为实际的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; 
     } 
    } 
}

来源

2015-10-11 Yatin Garg

是的，你是对的。实际的pos不会被设置为空。

原因

自recursion.for每一个递归调用，pos是different.So一旦节点被发现了，它会检查它是否已经离开或每码权child.As通过共享你，当节点没有左右子节点时，它将被设置为null，这是正确的。

总之，如果要删除的节点是叶节点，它将被设置为空。

注意：在你的代码中还需要一些更改。首先我要说你最后需要返回pos，并且必须在像这样递归调用delete方法时分配它。

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

来源

2015-10-11 12:45:31

你说得对。 pos不会设置为空。它只是简单地改变当前堆栈帧中局部变量pos的值，但只要从该递归级别返回，该更改将不会持久。

来源

2015-10-11 12:46:11 triadiktyo

如何从二叉搜索树中删除？

回答

相关问题