列出在树中离开的路径 [英] Listing the paths to leaves in a tree

问题描述

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

  1 
 / \ 
 2 5 
 / \\ 
 3 4 6 
  

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

此函数的类型签名是： branches：Tree a - > [[α]] 。请注意，它使用中定义的树类型Data.Tree 包，虽然示例树是二进制的，但实际的树类型是玫瑰树。

解决方案

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

  listtree tree = map reverse $ traverse [] tree 
其中遍历路径（Node label []）= [label：path] 
遍历路径（节点标签xs）= concat $ map（遍历（label：path ））xs 
  

将标签添加到列表的前面而不是结尾的原因是，追加在O（N）的时间和分配内存，而增加一个头部需要O（1）。当然，扭转名单也是O（N），但是逆转只会在每个名单上进行一次... ...

因此，上面的添加头，然后如果需要的话，反转模式在使用函数算法和数据结构时是一个普遍的习惯用法。

---

编辑：来自@ luqui的评论，

  listtree（节点标签[]）= [[标签]] 
 listtree（节点标签xs）= map（标签:) $ concat $ map listtree xs 
  

这比我的解决方案更短（也可能更清晰），并且它具有以您希望的顺序为您提供路径的额外优势：路径始于叶子而不是根。 / p>

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

b $ b

I'm trying to write a function that finds all of the paths to the leaves in a tree. For example, given a tree that looks like this:

           1
         /  \
        2    5
       / \    \
      3   4    6

The output list would be: [[1,2,3],[1,2,4],[1,5,6]].

The type signature for this function is:branches :: Tree a -> [[a]]. Note that this uses the Tree type defined in the Data.Tree package, and that although the example tree is binary, the actual tree type is a rose tree.

解决方案

I would build the paths by adding new labels to the front of the partial path list, then reversing them for output:

listtree tree = map reverse $ traverse [] tree
  where traverse path (Node label []) = [label:path]
        traverse path (Node label xs) = concat $ map (traverse (label:path)) xs

The reason to add labels to the front of the list instead of the end is that appending takes O(N) in time and allocated memory, while adding a head takes O(1). Of course, reversing the list is also O(N), but the reversal is only done once per list...

Consequently, the above "add to head, then reverse if necessary" pattern is a pervasive idiom when working with functional algorithms and datastructures.

---

Edit: from @luqui's comment, a complementary way to get your paths is to build them from the bottom up:

listtree (Node label []) = [[label]]
listtree (Node label xs) = map (label:) $ concat $ map listtree xs

This is shorter (and possibly clearer) than my solution, and it has the additional advantage of giving you your paths in the order you want them: the paths are built starting at the leaves, instead of at the root.

Note (as with the previous solution) the path lists are extended by adding a head to the beginning of the list, rather than appending to the end.

这篇关于列出在树中离开的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！