java是二进制搜索树中的第二大元素

Question

我正在寻找一个简单的算法来查找二叉搜索树中的下一个最大元素（键），有人能帮忙吗

Answer 1

案例1：右侧（x）为非空 继任者（x）=右边的最小值（x） 案例2：右侧（x）为空 沿树向上移动，直到当前节点是左子节点：后续节点（x）是当前节点的父节点 如果你不能再往前走（你到达了根）：x是最大的元素

Answer 2

假设“下一个最大的”是指当前节点所在位置的下一个最大节点

从当前节点向右移动一次。您已转到更高值的节点。然后，尽可能多地向左走。您已在值最低的节点处结束，该节点仍高于开始位置

_{（来源：ray at cs.lmu.edu）}

例如。从60岁开始，向右走一次，尽量向左走几次。你到了62岁

试着用同样的方法。你将在42岁结束

编辑：

这将有助于你的第二个案例。伪代码：

If (current.hasNoRightChild)
    testParent = current
    nextLargest = maxValueInTree
    While (testParent.hasParent)
        testParent = current.Parent
        If (testParent > current  && testParent < nextLargest)
            nextLargest = testParent
            While (testParent.hasLeftChild)
                testLeftChild = testParent.testLeftChild
                If (testLeftChild > current && testLeftChild < nextLargest)
                    nextLargest = testLeftChild
                End if
            End while
        End if
    End while
End if

虽然不能保证没有bug，但一般的想法是你检查每一位家长，慢慢地爬到树的顶端。在每个节点上，您停止并查看它是否是“下一个最大的”候选节点（即，它大于您开始的节点，并且小于当前对下一个最大节点的猜测）。在这些站点中的每一个站点上，如果节点大于开始位置，则必须沿着左分支上该节点的子树向下搜索，同时检查每个值。我认为应该这样做，但您可能应该使用随机值对其进行大量测试，以确保没有其他我们忽略的情况