-3

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

4

2 回答 2

3

假设通过“下一个最大”，您的意思是，当前节点所在位置的下一个最大节点......

从当前节点，向右走一次。你去了一个更高价值的节点。然后，尽可能多地向左走。您已在价值最低的节点处结束，该节点仍高于您开始的地方。

在此处输入图像描述
（来源：ray at cs.lmu.edu）

例子。从 60 岁开始，向右走一次，尽可能多地向左走。你最终到了 62 岁。

为 41 尝试同样的事情。你最终会在 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

不能保证没有错误，但一般的想法是你检查每个父母，慢慢地工作到树的顶部。在每个节点处，您停下来看看它是否是“下一个最大”的候选者（即它大于您开始的节点并且小于当前猜测的下一个最大节点）。在这些站点中的每一个站点，如果节点大于您开始的位置，则您必须仅沿着左侧分支上该节点的子树向下探索，并沿途检查每个值。我认为应该这样做，但是您可能应该使用随机值对其进行大量测试，以确保没有我们忽略的任何其他情况。

于 2012-12-07T05:37:51.000 回答
1

情况 1：右 (x) 是非空的后继 (x) = 右 (x) 中的最小值 情况 2：右 (x) 是空的 上树直到当前节点是左孩子：后继 (x) 是如果你不能走得更远（并且你到达了根），则为当前节点的父节点：x 是最大的元素

于 2012-12-07T05:42:44.557 回答