一千萬個為什麽

搜索

二叉搜索樹中的下一個最大元素

我正在尋找一個簡單的算法來查找二叉搜索樹中的下一個最大元素(鍵),任何人都可以幫忙嗎?

最佳答案

假設“下一個最大”是指當前節點的下一個最大節點...

從當前節點向右走一次。你已經去了一個更高價值的節點。然後,盡可能多地離開。你已經結束了最低價值的節點,它比你開始的地方還要高。

http://cs.lmu.edu/~ray/images/bstexample.png

例。從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

不能保證沒有錯誤,但總體思路是檢查每個父母,慢慢地走到樹頂。在每個節點上,你停下來看看它是否是候選者是“下一個最大”(即它大於你開始的節點並且小於當前下一個最大的猜測)。在每個停靠點上,如果節點大於開始位置,則必須沿著左側分支上的該節點的子樹完整探索,並檢查每個值。我認為應該這樣做,但你應該用隨機值進行大量測試,以確保沒有任何其他我們忽略的情況。

轉載註明原文: 二叉搜索樹中的下一個最大元素