Enumerating all paths in a tree

I was wondering how to best implement a tree data structure to be able to enumerate paths of all levels. Let me explain it with the following example:

     A
   /   \
   B    C
   |    /\
   D   E  F

I want to be able to generate the following:

A
B
C
D
E
F
A-B
A-C
B-D
C-E
C-F
A-B-D
A-C-E
A-C-F

As of now, I am executing a depth-first-search for different depths on a data structure built using a dictionary and recording unique nodes that are seen but I was wondering if there is a better way to do this kind of a traversal. A开发者_运维百科ny suggestions?

Whenever you find a problem on trees, just use recursion :D

def paths(tree):
  #Helper function
  #receives a tree and 
  #returns all paths that have this node as root and all other paths

  if tree is the empty tree:
    return ([], [])
  else: #tree is a node
    root = tree.value
    rooted_paths = [[root]]
    unrooted_paths = []
    for subtree in tree.children:
        (useable, unueseable) = paths(subtree)
        for path in useable:
            unrooted_paths.append(path)
            rooted_paths.append([root]+path)
        for path in unuseable:
            unrooted_paths.append(path)
    return (rooted_paths, unrooted_paths)

def the_function_you_use_in_the_end(tree):
   a,b = paths(tree)
   return a+b

Just one more way:

Every path without repetitions in tree is uniquely described by its start and finish.

So one of ways to enumerate paths is to enumerate every possible pair of vertices. For each pair it's relatively easy to find path (find common ancestor and go through it).

Find a path to each node of the tree using depth first search, then call enumerate-paths(Path p), where p is the path from the root to the node. Let's assume that a path p is an array of nodes p[0] [1] .. p[n] where p[0] is the root and p[n] is the current node.

enumerate-paths(p) {
    for i = 0 .. n  
        output p[n - i] .. p[n] as a path. 
}

Each of these paths is different, and each of them is different from the results returned from any other node of the tree since no other paths end in p[n]. Clearly it is complete, since any path is from a node to some node between it and the root. It is also optimal, since it finds and outputs each path exactly once.

The order will be slightly different from yours, but you could always create an array of list of paths where A[x] is a List of the paths of length x. Then you could output the paths in order of their length, although this would take O(n) storage.