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.

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