列出树中叶子的路径

Question

我正在尝试编写一个函数来查找到树中叶子的所有路径。
例如，给定一棵树，看起来像这样:

           1
         /  \
        2    5
       / \    \
      3   4    6

输出列表将是: [[1,2,3],[1,2,4],[1,5,6]] .

这个函数的类型签名是: branches :: Tree a -> [[a]] .请注意，这使用了 Data.Tree 中定义的 Tree 类型。包，虽然示例树是二叉树，但实际的树类型是玫瑰树。

Answer 1

只是一个简单的功能:

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]]