Javaのバイナリ検索ツリーからノードを削除する

Question

私はBSTからノードを削除しようとしています。私はノードが2つの子を持つときに1つ（findInorderSuccesor）が呼び出されている2つの関数の助けを借りています。 問題は、削除されたノードの代替として提供されているノードが元の位置から削除されていないことです。その結果、同じ値を持つ2つのノードがあります。

obj.addNode(8); 
    obj.addNode(2); 
    obj.addNode(5); 
    obj.addNode(1); 
    obj.addNode(13); 
    obj.addNode(10); 
    obj.addNode(15); 

    obj.deleteNode(obj.root,8); 

    public void deleteNode(treeNode focusNode, int data) 
    { 
    if(data<focusNode.data) 
     deleteNode(focusNode.left,data); 
    else if (data>focusNode.data) 
     deleteNode(focusNode.right,data); 
    else 
    { 
     if(focusNode.right == null && focusNode.left == null) 
      focusNode=null; 
     else if(focusNode.left!=null && focusNode.right==null) 
      focusNode = focusNode.left; 
     else if (focusNode.right!=null && focusNode.left==null) 
      focusNode = focusNode.right; 
     else 
     { 
      //node has two children 
      BSTDeletion obj = new BSTDeletion(); 
      treeNode replacement =obj.findInorderSuccessor(focusNode.right); 
      focusNode.data = replacement.data; 
      deleteNode(focusNode.right, replacement.data); 

     } 
    } 
} 



public treeNode findInorderSuccessor(treeNode focusNode) 
{ 
treeNode preFocusNode = null; 
while(focusNode!=null) 
{ 
    preFocusNode = focusNode; 
    focusNode = focusNode.left; 
} 
return preFocusNode; 
} 

Answer 1

Boolaが書いたように、あなたはあなたが削除されたノードの親を知る必要があります。

focusNode = nullと言ったとき。親が依然としてそのノードを参照しているため、参照をnullにするだけです。ツリーからオブジェクトを削除しないでください。 あなたは次のようなものが必要です：

public void deleteNode(treeNode focusNode, int data) 
{ 
if(data<focusNode.data) 
    deleteNode(focusNode.left,data); 
else if (data>focusNode.data) 
    deleteNode(focusNode.right,data); 
else 
{ 
    treeNode parent = focusNode.getParent(); // get the parent. 
if(focusNode.left==null && focusNode.right==null) 
    { 
     if(parent.left.equals(focusNode)) 
      parent.left = null;    //Set the parents reference to null. 
     else 
      parent.Right = null; 
    } 
else if(focusNode.left!=null && focusNode.right==null) 
    { 
     if(parent.left.equals(focusNode)) 
      parent.left = focusNode.left; //Reassign the parents reference to the correct node. 
     else 
      parent.right = focusNode.left; 
    } 

などが必要です。