java实现二叉搜索树中删除节点

Question

正在尝试从BST中删除节点。执行后，该节点仍保留在树中。我怎样才能正确地实施它

public void deleteNode(TreeNode removeNode, TreeNode root)
{


    if(removeNode.Left==null && removeNode.Right==null) //0 children
    {
        removeNode = null;
    }
    else if(removeNode.Left==null)//1 children
    {

        removeNode = removeNode.Right;
    }
    else if(removeNode.Right==null)//1 children
    {
        removeNode = removeNode.Left;
    }
    else // 2 children
    {
        int successorValue = this.getSuccessor(removeNode, root);
        TreeNode successor = this.search(successorValue,root);

        removeNode.data = successor.data;

        deleteNode(successor, root);
    }

}

Answer 1

节点仍然存在，因为您从未将其从树中删除

当您调用deleteNode时，您会得到一个对要删除的节点和树的根的引用。当你说removeNode = null;你将你的引用设置为null时，你不会移除这个对象。这意味着树中的节点仍然引用该节点

要从树中删除节点，需要删除对该节点的引用。我现在不知道您有什么可用的方法，但要让您走上正确的方向，应该是这样的：

public void deleteNode(TreeNode removeNode, TreeNode root)
{
    TreeNode parent = removeNode.getParent();   //Find parent node to removeNode.

    if(removeNode.Left==null && removeNode.Right==null) //0 children
    {
        if(parent.Left.equals(removeNode))
             parent.Left = null;                //Set the parents reference to null. 
        else
             parent.Right = null;
    }
    else if(removeNode.Left==null)//1 child
    {
        if(parent.Left.equals(removeNode))
             parent.Left = removeNode.Right;  //Reassign the parents reference to the correct node. 
        else
             parent.Right = removeNode.Right;
    }
    ... //etc.

关键是您必须更改树中的引用，而不是您的本地引用。希望这是有意义的