5

我正在尝试编写一个函数来查找树中叶子的所有路径。例如，给定一棵如下所示的树：

           1
         /  \
        2    5
       / \    \
      3   4    6

输出列表将是：[[1,2,3],[1,2,4],[1,5,6]]。

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

4

3 回答 3

3

只是一个简单的功能：

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

于 2013-03-11T14:30:29.370 回答
1

我将通过在部分路径列表的前面添加新标签来构建路径，然后将它们反转以进行输出：

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

这比我的解决方案更短（并且可能更清晰），它还有一个额外的优势，就是按照你想要的顺序为你提供路径：路径是从叶子开始构建的，而不是从根开始。

注意（与前面的解决方案一样）路径列表是通过在列表的开头添加一个头来扩展的，而不是附加到末尾。

于 2013-03-11T17:27:55.163 回答
0

很简单...这些是您需要牢记的事情：-

  1. 递归调用函数
  2. 在函数内，遍历应采用 PreOrder 的形式（根、左、右）
  3. 在递归函数中使用数组并存储访问的每个节点的值。
  4. 如果访问的节点是叶子...节点--> 左== NULL 和节点--> 右== NULL。然后输出数组的内容。
于 2013-03-11T04:31:52.603 回答