在二叉樹中返回最小值

我試圖編寫代碼，如果給定一棵樹，將通過樹並返回該樹中的最小值，如果樹爲空，它將返回val。我現在編譯的內容不會運行。任何幫助？在二叉樹中返回最小值

minValue :: Ord a => a -> BTree a -> a 
minValue val Empty = val 
minValue val (BNode v left Empty) = minimum [minValue v left] 
minValue val (BNode v Empty right) = minimum [minValue v right] 
minValue val (BNode v left right) = minimum ([minValue v left]++[minValue v right])

來源

2015-04-02 tamais2

在二叉搜索樹中排列了樹的元素嗎？在任何情況下，您都不需要使用列表或「最小」來執行此操作。在第二和第三個方程中，它們是多餘的 - 單元素列表的最小值是列表的一個元素。 – 2015-04-02 20:56:33

樹是有序的，是的。 – tamais2 2015-04-02 21:00:20

另外：我只是試過你的功能，它有這個bug：'minValue 17（BNode 22 Empty Empty）== 22' – 2015-04-02 21:08:41

我假設BTree被定義爲

data BTree a = Empty | BNode a (BTree a) (BTree a) deriving (Eq, Show)

雖然以供將來參考請在你的問題的數據類型定義。

的關鍵，這裏的解決方案是一個節點的最小值是其值的最小值和每個分支的分鐘：

minValue :: Ord a => a -> BTree a -> a 
minValue val Empty = val 
minValue val (BNode v left right) = 
    let leftMin = minValue val left 
     rightMin = minValue val right 
    in ???

而是擔心，如果左邊或右邊的是Empty，只是信任遞歸來處理它。如果left是Empty，那麼minValue val left將只是val，並且類似地right。然後，您有4個要確定最小值的範圍值，val，v,leftMin和rightMin。你會怎麼做？

來源

2015-04-02 21:39:10 bheklilr

在二叉樹中返回最小值

回答

相關問題