Enumerar todos los caminos en un árbol

Me preguntaba cómo implementar mejor una estructura de datos de árbol para poder enumerar rutas de todos los niveles. Déjame explicarlo con el siguiente ejemplo:

A / \ BC | /\ DEF 

Quiero poder generar lo siguiente:

 A B C D E F AB AC BD CE CF ABD ACE ACF 

A partir de ahora, estoy ejecutando una búsqueda en profundidad para diferentes profundidades en una estructura de datos construida utilizando un diccionario y grabando nodos únicos que se ven, pero me preguntaba si hay una mejor manera de hacer este tipo de recorrido. ¿Alguna sugerencia?

Siempre que encuentre un problema en los árboles, simplemente use la recursión: 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 

Encuentre una ruta a cada nodo del árbol usando la búsqueda en profundidad en primer lugar, luego llame a enumerate-paths(Path p) , donde p es la ruta desde la raíz hasta el nodo. Supongamos que una ruta p es una matriz de nodos p[0] [1] .. p[n] donde p[0] es la raíz y p[n] es el nodo actual.

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

Cada una de estas rutas es diferente, y cada una de ellas es diferente de los resultados devueltos desde cualquier otro nodo del árbol, ya que ninguna otra ruta termina en p[n] . Claramente está completo, ya que cualquier ruta es desde un nodo a algún nodo entre este y la raíz. También es óptimo, ya que encuentra y genera cada ruta exactamente una vez.

El orden será ligeramente diferente del tuyo, pero siempre puedes crear una matriz de lista de rutas donde A[x] es una Lista de rutas de longitud x . Luego, podría generar las rutas en orden de su longitud, aunque esto tomaría almacenamiento O (n).

Sólo una forma más:

Cada ruta sin repeticiones en el árbol se describe de forma única por su inicio y final.

Así que una de las formas de enumerar rutas es enumerar cada par de vértices posibles. Para cada par es relativamente fácil encontrar una ruta (encontrar un ancestro común y recorrerla).