1
我一直在試圖從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;
}
你需要知道inorder後繼者的父母才能刪除孩子。但您正在保存父引用。因此,你的代碼將永遠無法刪除節點。 – Boola