最大和最小的二进制树的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