java - 在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;您只需将引用设为空，就不会从树中删除该对象，因为父节点仍在引用该节点。 你需要这样的东西:

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

等等。