最大和最小的二進制樹的Haskell元件

Question

考慮樹的定義如下：

Data Tree a = Empty | Node a (Tree a) (Tree a) 

定義一個給定的數Ñ和樹的功能smallerbigger :: Float -> Tree Float -> ([Float],[Float])，產生一對列表，其元素爲較小的並且大於n。

（該問題最初表明該樹是一個搜索樹，這是錯誤的）。

Answer 1

感謝您的所有幫助和建議。

我設法找到不同的解決辦法：

smallerbigger :: Ord a => a -> Tree a -> ([a], [a]) 
smallerbigger n (Node r e d) = 
    let (e1,e2) = smallerbigger n e 
     (d1,d2) = smallerbigger n d 
    in if  r>n then ( e1++d1, r:(e2++d2)) 
     else if r<n then (r:(e1++d1), e2++d2) 
     else    ( e1++d1,  e2++d2) 

Answer 2

有關列表，你可以實現類似的算法作爲

smallerbigger :: Ord a => a -> [a] -> ([a], [a]) 
smallerbigger x xs = go x xs [] [] 
    where 
     go y [] lt gt = (lt, gt) 
     go y (z:zs) lt gt 
      | z < y = go y zs (z:lt) gt 
      | z >= y = go y zs lt (z:gt) 

的算法將保持相同的樹的基本形狀，但最大的區別是你如何遞歸。您需要遞減兩個分支，然後一旦您從每個分支中獲得結果，並將它們與當前節點的結果一起連接起來。

如果您遇到這種實現一棵樹，隨意評論，讓我知道您遇到什麼問題，包括在要點/引擎收錄/任何一個鏈接到您的代碼。

Answer 3

這裏的一小組實用程序導致簡單的解決方案。假設你需要懶惰的功能。 這裏有另外的只顯示能力調試

data Tree a = Empty | Node a (Tree a) (Tree a) deriving Show 

下一頁數據defition我們需要爲易樹創建的小工具。以下代碼構建了一個非常不平衡的樹，與原始列表非常相似。

fromList:: [a] -> Tree a 
fromList [] = Empty 
fromList (x:xs) = Node x Empty (fromList xs) 

列表形式的樹的簡單和明顯的表示形式。元素的順序被保留。

asList:: Tree a -> [a] 
asList Empty = [] 
asList (Node x left right) = asList left ++ x: asList right 

接下來，我們假設我們需要對列出了可能偷懶，無論我們的目的地的。 我們保持與中間的某個具有無限的結構樹的工作能力，而不是在最後或結束元素。 這個定義以懶惰的方式向相反的方向走過我們的樹。

reverseTree:: Tree a -> Tree a 
reverseTree Empty = Empty 
reverseTree (Node x left right) = Node x (reverseTree right) (reverseTree left) 

接下來我們終於建立了我們的程序。它可以創建兩個可能的無限小於大於第一個參數的元素列表。

smallerbigger::Ord a => a-> Tree a -> ([a],[a]) 
smallerbigger p t = (takeWhile (<p) $ asList t, takeWhile (>p) $ asList $ reverseTree t) 

main = let t = fromList [1..10] 
    in do 
     print t 
     print $ smallerbigger 7 t 

但在另一方面，我們可能要在第二個列表中保持秩序，而我們相信，我們從不打bottom建立第一個列表。因此，我們可以丟棄等於目標分離，只是跨越了名單在它的元素。

smallerbigger p = span (<p) . filter(/=p) . asList