二叉搜索树查找最大节点并将其删除（泛型类）

Question

正如标题所说，我目前正试图找到BST的最大节点，我想删除它。我有方法来查找最大节点和删除节点准备从我的算法书，但我不知道如何在主方法中使用它们。我有一个方法，可以通过输入一个数字插入节点，例如8，这将打印一个级别有序的树：4, 2, 6, 1, 3, 5, 7其中4是根。我希望能够找到最后一个节点并删除它。到目前为止，我有这些方法：

public BinaryNode remove(AnyType x, BinaryNode<AnyType> t)
{
    if(t == null)
        return t;

    int compareResult = x.compareTo(t.element);

    if(compareResult < 0 )
        t.left = remove(x, t.left);
    else if(compareResult > 0)
        t.right = remove(x, t.right);
    else if(t.left != null && t.right != null)
    {
        t.element = (AnyType) findMax(t.right).element;
        t.right = remove(t.element, t.right);
    }
    else
        t = (t.left != null) ? t.left : t.right;
    return t;
}

public BinaryNode<AnyType> remove(AnyType x)
{
    return root = remove(x, root);
}

public BinaryNode<AnyType> findMax(BinaryNode<AnyType> t)
{
    if(t != null)
        while(t.right != null)
            t = t.right;
    return t;
}

我的主要方法是这样的：

public static void main(String[] args)
{
    CompleteBinarySearchTree<Integer> bst = new CompleteBinarySearchTree<>();
    BinaryNode<Integer> tree = bst.createBinarySearchTree(bst.insertNodes(8));
    bst.printLevelOrderedBST(tree);
}

我希望能够自由插入任何节点，并且树仍然能够删除max节点。我不知道如何在findMax（）上调用remove（）方法。我当然可以调用remove（7，tree），它将删除7，但这不是我想要的。非常感谢您的帮助。

Answer 1

删除max节点的关键是必须跟踪其父节点，以便可以更新父节点的右指针（将其设置为null）。您还必须处理这样的情况：您传递的节点没有正确的子节点，其中节点本身是最大的节点。

下面的代码显示了基本思想。未经测试，但应接近。

// removes the largest node in the binary tree with root at t.
// returns the new root.
public BinaryNode<AnyType> removeMax(BinaryNode<AnyType> t)
{
    if (t == null) return null;
    if (t.right == null) {
        // the node passed in is the largest.
        return t.left;
    }

    // traverse the right branch to the last node,
    // keeping track of the previous node so you can correctly set its
    // right pointer to null.
    BinaryNode<AnyType> parent = t;
    BinaryNode<AnyType> child = parent.right;
    while (child.right != null) {
        parent = child;
        child = child.right;
    }
    parent.right = null;
    return t;
}