实现在二叉搜索树中删除节点

Question

试图从BST中删除节点。执行后，节点仍然保留在树中。我如何正确实施它？

public void deleteNode(TreeNode removeNode, TreeNode root) 
{ 


    if(removeNode.Left==null && removeNode.Right==null) //0 children 
    { 
     removeNode = null; 
    } 
    else if(removeNode.Left==null)//1 children 
    { 

     removeNode = removeNode.Right; 
    } 
    else if(removeNode.Right==null)//1 children 
    { 
     removeNode = removeNode.Left; 
    } 
    else // 2 children 
    { 
     int successorValue = this.getSuccessor(removeNode, root); 
     TreeNode successor = this.search(successorValue,root); 

     removeNode.data = successor.data; 

     deleteNode(successor, root); 
    } 

} 

Answer 1

节点仍然存在，因为您永远不会将它从树中移除。

当您致电deleteNode时，您将得到一个参考到您要删除的节点和树的根。当你说removeNode = null;你设置你的参考null，你不会删除该对象。这意味着树中的节点仍然引用该节点。

要从树中删除节点，您需要删除对节点的引用。我不应该是现在什么方法你有可用的，但是送你在正确的方向是这样的：

public void deleteNode(TreeNode removeNode, TreeNode root) 
{ 
    TreeNode parent = removeNode.getParent(); //Find parent node to removeNode. 

    if(removeNode.Left==null && removeNode.Right==null) //0 children 
    { 
     if(parent.Left.equals(removeNode)) 
      parent.Left = null;    //Set the parents reference to null. 
     else 
      parent.Right = null; 
    } 
    else if(removeNode.Left==null)//1 child 
    { 
     if(parent.Left.equals(removeNode)) 
      parent.Left = removeNode.Right; //Reassign the parents reference to the correct node. 
     else 
      parent.Right = removeNode.Right; 
    } 
    ... //etc. 

的一点是你必须改变引用树而不是你当地参考。希望这是有道理的。