从Java中的二叉搜索树中删除节点

我一直在试图从BST中删除一个节点。我正在接受两个函数的帮助，其中一个（findInorderSuccesor）在节点有两个子节点时被调用。问题是，作为被删除节点的替代品进入的节点未从其原始位置删除。结果，我有两个具有相同值的节点。从Java中的二叉搜索树中删除节点

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

BFS Traversal of the Tree

来源

2016-12-07 Satyaki Kundu

你需要知道inorder后继者的父母才能删除孩子。但您正在保存父引用。因此，你的代码将永远无法删除节点。 – Boola

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

等等。

来源

2016-12-07 11:05:26 jacobek09

从Java中的二叉搜索树中删除节点

回答

相关问题