Listing the paths to leaves in a tree

问题:

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.

回答1:

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.

回答2:

just a simple function:

listtree :: [a] -> Tree a -> [[a]]
listtree l (Node a []) = [l++[a]]
listtree l (Node a forest) = concatMap (listtree (l++[a])) forest

use a list to record path from root to current node, and append current node's label to the path, then recursively map listtree to each subnode.

listtree [] (Node 1 [(Node 2 [(Node 3 []), (Node 4 [])]), (Node 5 [(Node 6 [])])]))

yield the desired result [[1,2,3],[1,2,4],[1,5,6]]

回答3:

It's simple...These are the things that you need to have in mind :-

1. Recursively call the function
2. Within the function the traversal should be in the form of PreOrder ( root, left and then right)
3. Use an array within the recursive function and store the value of every node visited.
4. If the visited node is a leaf ... node--> left == NULL and node--> right == NULL. Then output the contents of the array.