我正在尝试编写一个函数来查找树中叶子的所有路径。例如，给定一个如下所示的树：
1
/ \
2 5
/ \ \
3 4 6
输出列表将是：[[1,2,3],[1,2,4],[1,5,6]]。
此函数的类型签名是：branches :: Tree a -> [[a]]。请注意，这使用了Data.Tree包中定义的Tree类型，虽然示例树是二进制的，但实际的树类型是玫瑰树。
我会通过在部分路径列表的前面添加新标签来构建路径，然后将它们反转以进行输出：
listtree tree = map reverse $ traverse [] tree
where traverse path (Node label []) = [label:path]
traverse path (Node label xs) = concat $ map (traverse (label:path)) xs
将标签添加到列表前面而不是结尾的原因是追加时间为O（N）并分配内存，而添加头部则需要O（1）。当然，反转列表也是O（N），但每个列表只进行一次反转...
因此，在使用功能算法和数据结构时，上述“添加到头部，然后在必要时反转”模式是一种普遍的习惯用法。
编辑：从@ luqui的评论中，获取路径的一种补充方法是从下到上构建它们：
listtree (Node label []) = [[label]]
listtree (Node label xs) = map (label:) $ concat $ map listtree xs
这比我的解决方案更短（并且可能更清晰），并且它还具有以您希望的顺序为您提供路径的额外优势：路径是从叶子而不是从根开始构建的。
注意（与前面的解决方案一样）路径列表通过在列表的开头添加一个头而不是追加到末尾来扩展。
只是一个简单的功能：
listtree :: [a] -> Tree a -> [[a]]
listtree l (Node a []) = [l++[a]]
listtree l (Node a forest) = concatMap (listtree (l++[a])) forest
使用列表记录从根节点到当前节点的路径，并将当前节点的标签附加到路径，然后递归地将listtree映射到每个子节点。
listtree [] (Node 1 [(Node 2 [(Node 3 []), (Node 4 [])]), (Node 5 [(Node 6 [])])]))
产生理想的结果[[1,2,3],[1,2,4],[1,5,6]]
这很简单......这些是你需要考虑的事情： -