java - Java二叉搜索树删除

Question

我正在为二叉搜索树编写删除方法，它不完整，但我填充了一棵树，以便我至少可以测试我要删除的节点是叶子但它似乎不是的情况在职的。我的逻辑有什么明显的错误吗？

public void delete(E d)
{
    delete( d, root);
}

private void delete( E d, Node<E> T)
{
    if(T == null)
    {
        return;
    }
    else if(d.equals(T.getData()))
    {
        System.out.println("it found the node at least");
        if(T.getRight() == null && T.getLeft() == null)
        {
            T.setData(null);
        }
        //do alot)
    }
    else if(d.compareTo(T.getData()) > 0)
    {
        System.out.println("going right");
        delete(d, T.getRight());
    }
    //s is less than T, insert on left subtree
    else
    {System.out.println("going left");
        delete(d,T.getLeft());
    }

}  

Answer 1

您的代码不会删除节点。它只是清除它们。
为了实现删除，您必须将您的功能更改为无效，但是：

private Node delete( E d, Node<E> T)

你的代码应该是这样的：

public void delete(E d) {
    root = delete( d, root);
}

private void delete( E d, Node<E> T)
{
    if(T == null)
    {
        return;
    }
    else if(d.equals(T.getData()))
    {
        System.out.println("it found the node at least");
        if(T.getRight() == null && T.getLeft() == null)
        {
           return null;
        }
        //do alot)
    }
    else if(d.compareTo(T.getData()) > 0)
    {
        System.out.println("going right");
        T.right = delete(d, T.getRight());
    }
    //s is less than T, insert on left subtree
    else
    {
        System.out.println("going left");
        T.left = delete(d,T.getLeft());
    }

}  

你明白了……