實現在二叉搜索樹中刪除節點

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. 

的一點是你必須改變引用樹而不是你當地參考。希望這是有道理的。