Haskell-从根到叶的列表

Question

代码假设返回树中从根到叶的每条路径的列表，顺序从左到右。具有一个子节点（一个子节点（一个子节点）和一个子节点（一个子节点）不被视为叶节点。

我试着像这样编码

paths :: Tree a -> [[a]]
paths Tip = [[]]
paths (Bin Tip x Tip) = [[x]]
paths (Bin left x right) = map (x:) (paths left ++ paths right)

但返回的路径似乎包括具有一个子节点的节点。这将导致类似于Bin（Bin Tip 3 Tip）4 Tip上的路径。




Answer 1

匿名用户

这是因为您的路径提示=[[]]返回一个包含一个元素的列表：空列表。

因此，这意味着，例如，对于箱子提示4（箱子提示3提示），左侧的路径将返回一个[[]]，并且您在该列表前面加上4，因此也将生成[4]。

如果您将其更改为路径提示 = [] ，您就解决了问题，因为它不会产生元素：

paths :: Tree a -> [[a]]
paths Tip = []
paths (Bin Tip x Tip) = [[x]]
paths (Bin left x right) = map (x:) (paths left ++ paths right)