haskell - Haskell 中的通用树 = 玫瑰树？玫瑰树的海报？

Question

我应该为树创建一个数据结构，其中每个节点都有未定义数量的分支。我猜这将是一棵玫瑰树。

data GTree a = Node a [GTree a] 

现在我应该写一个 postorderG 函数，它会在我写的后序序列中给我一个我的将军中所有元素的列表，但它似乎不正确......有人可以帮助我吗？

postorderG :: GTree a -> [a]
postorderG (Node x l r) = postorder l ++ postorder r ++ [GTree x]

Answer 1

GTree是类型构造函数，而不是数据构造函数；将创建一棵树Node x []，而不是GTree x。

但是，您根本不需要在这里创建树。对于返回值中的最终列表，您只需要存储在输入树根部的值。

postorderG :: GTree a -> [a]
postorderG (Node x ch) =  concatMap postorderG ch -- [a]
                          ++ [x]         -- [a], not [GTree a]

如果你愿意，你可以创建一个单例树来追加到ch，按顺序应用postOrderG到每个孩子和新的单例。

postorderG (Node x ch) = concatMap postorderG (ch ++ [Node x []])

利用[]monad 而不是 using concatMap，RHS 看起来像

(ch >>= postorderG) ++ [x]

或者

(ch ++ [Node x []]) >>= postorderG