从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;
}
答
由于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;
}
等等。
你需要知道inorder后继者的父母才能删除孩子。但您正在保存父引用。因此,你的代码将永远无法删除节点。 – Boola