Удаление узла из двоичного дерева поиска в Java

Question

Я пытался удалить узел из BST. Я пользуюсь двумя функциями, в которых один (findInorderSuccesor) вызывается, когда узел имеет двух детей. Проблема заключается в том, что узел, входящий в качестве замены удаленного узла, не удаляется из исходной позиции. В результате у меня есть два узла с одинаковым значением.

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; 
    } 

и так далее.