Haskell中的水平顺序

我有一棵树的结构，我想按级别打印树。Haskell中的水平顺序

data Tree a = Nd a [Tree a] deriving Show 
type Nd = String 
tree = Nd "a" [Nd "b" [Nd "c" [], 
         Nd "g" [Nd "h" [], 
           Nd "i" [], 
           Nd "j" [], 
           Nd "k" []]], 
       Nd "d" [Nd "f" []], 
       Nd "e" [Nd "l" [Nd "n" [Nd "o" []]], 
         Nd "m" []]] 
preorder (Nd x ts) = x : concatMap preorder ts 
postorder (Nd x ts) = (concatMap postorder ts) ++ [x]

但如何通过级别来做到这一点？ “水平树”应该打印[“a”，“bde”，“cgflm”，“hijkn”，“o”]。我认为“迭代”将是合适的功能，但我不能想出如何使用它的解决方案。你能帮我吗？

来源

2010-04-28 brain_damage

你不需要'type Nd = String'。它不会在你的代码中做任何事情，因为你永远不会使用类型Nd（你使用类型树的数据构造函数Nd，但这完全不相关）。 – sepp2k 2010-04-28 18:56:57

我不认为你想要的结果显示在表格中：它连接来自相邻节点的数据的方式，a）如果a不是列表类型，并且b）丢失关于遍历的信息，则不起作用。考虑这个树：Nd“a”[Nd“bde”[Nd“cgflm”[Nd“hijkn”[Nd“o”[]]]]] - 它会带来与您所要求的结果相同的结果。为了不陷入这个陷阱，使用字符（'a'）或数字作为示例树中的节点值。这将保持你的解决方案很好的一般性。 – MtnViewMark 2010-04-28 21:44:46

你只需要计算水平对所有的子树和根后压缩它们放在一起：

levels :: Tree [a] -> [[a]] 
levels (Nd a bs) = a : foldr (zipWith' (++)) [] (map levels bs)

可悲的是，zipWith没有做正确的事情，所以我们可以改用：

zipWith' f xs [] = xs 
zipWith' f [] xs = xs 
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys

更新：有一些问题（我同意），你最初问的是有点奇怪，因为它不是一个通用的广度优先树来列出转换器。你可能真的想要的是Concat的结果：

levels' (Nd a bs) = [a] : foldr (zipWith' (++)) [] (map levels' bs)

来源

2010-04-28 19:09:58 sigfpe

不错的解决方案。我想Haskell没有你的变种zipWith，它并不停留在较小的列表中，它只适用于a-> a-> a类型的f。你可以用zipWith写成它，如'levels（Nd a bs）= a：foldr（zipWith（++））（repeat []）（map levels bs）'并使用'takeWhile（not.null）$级树'，但这可能只是愚蠢的。 :-) – ShreevatsaR 2010-04-28 19:45:39

你可以编写一个'zipWith''版本，它可以通过将一对参数用作填充来处理不同的类型。 – sigfpe 2010-04-28 19:53:45

此解决方案不适用于完整抽象类型“树a” - 而zipWith的变体有点奇怪。 – MtnViewMark 2010-04-28 21:41:04

levels :: (Tree a) -> [[a]] 
levels (Nd x ts) = [[x]] ++ levelshelper ts 

level2 = (map concat).levels 

levelshelper :: [Tree a] -> [[a]] 
levelshelper [] = [] 
levelshelper xs = (map (\(Nd x ts) -> x) xs) : (levelshelper (extractl xs)) 

--get the next level's Nd's 
extractl :: [Tree a] -> [Tree a] 
extractl [] = [] 
extractl ((Nd x ts):xs) = ts ++ (extractl xs)

我的做法被证明是更有点笨拙的不是我想要的。但是，如果我错了，请纠正我，因为字符串是字符列表，但是您使用的是多态类型，是否真的很直接地将结果打印出来，就像问题中指定的一样？此代码生成字符串列表的列表。 ***道具克里斯在他更优雅的回答提醒我关于使用concat !!

来源

2010-04-28 19:41:13 thegravian

这是另一个版本，可以应用于Tree a而不是Tree [a]。

levelorder :: Tree a -> [[a]] 
levelorder (Nd x ts) = [x]:(ziplist (map levelorder ts)) 

ziplist :: [[[a]]] -> [[a]] 
ziplist l = if null ls then [] else (concat heads):(ziplist tails) 
    where 
     ls = filter (not.null) l 
     heads = map head ls 
     tails = map tail ls

如果你想连接在最后的字符串你可以使用：

levelorder2 :: Tree [a] -> [[a]] 
levelorder2 = (map concat).levelorder

来源

2010-04-28 19:45:00 Kru

我猜这是功课。假设它是，那么这里有一些关于如何思考可能会导致你回答的问题的想法：

在preorder中，首先将当前项目“报告”，然后对所有该节点的尾部递归。在postorder这两个步骤是相反的。在这两种情况下，递归都是“本地”的，因为它只需要一次处理一个节点。这是否适用于levelorder？或者以另一种方式提出，levelorder递归时，执行递归的结果还是不相交？如果是这样的话，递归的“单位”是什么，如果不是一个Tree？

了解levelorder的递归（或迭代..?）的性质将使您找到一个非常简单和优雅的解决方案。我的版本只有三行！

顺便说一句，这可能是不错的这些实用功能，使代码，甚至在一些地方更清晰：

element :: Tree a -> a 
element (Nd x _) = x 
subtrees :: Tree a -> [Tree a] 
subtrees (Nd _ s) = s

或者，如果你熟悉哈斯克尔记录语法，就可以实现准确这种通过改变你原来的Tree定义：

data Tree a = Nd { element :: a, subtrees :: [Tree a] } 
    deriving Show

完整的解决方案：

关键是认识到levelorder需要递归在Tree的列表上。在每一步从每个Tree元素被提取，并且下一步骤是在所述子树的级联：

levelorder :: Tree a -> [a] 
levelorder t = step [t] 
    where step [] = [] 
      step ts = map element ts ++ step (concatMap subtrees ts)

这产生在单一的元件的，扁平的列表，很像preorder和postorder做的，是广度优先遍历的通常定义。

相反，如果你真的想通过水平分组的元素，将++运营商到:一个变化将产生版本：

bylevel :: Tree a -> [[a]] 
bylevel t = step [t] 
    where step [] = [] 
      step ts = map element ts : step (concatMap subtrees ts)

注：我已经给定类型签名所有顶级功能。这是一个非常好的习惯，并且可以节省您相当多的时间进行调试。

来源

2010-04-28 19:58:39 MtnViewMark

Haskell中的水平顺序

回答

相关问题