Traverse cada camino único (desde la raíz hasta las hojas) en una estructura de árbol arbitraria

Question

Tengo varias listas:

A = ["a0", "a1"]  // the number of lists varies 
B = ["b0", "b1", "b2"] // such as the number of elements in a list. 
C = ["c1"] 
D = ["d0", "d1"] 

puedo convertir esta estructura en un árbol:

   _____ROOT______ 
      /    \ 
     ___a0____  ____a1____ 
    / | \ / | \ 
    b0 b1 b2 b0 b1 b2 
    |  |  |  |  |  | 
    c1 c1 c1 c1 c1 c1 
/| /| /| /| /| /| 
    d0 d1 d0 d1 d0 d1 d0 d1 d0 d1 d0 d1 

estoy imprimiendo cada camino único en el árbol (omitiendo la raíz):

a0 -> b0 -> c1 -> d0 
a0 -> b0 -> c1 -> d1 
a0 -> b1 -> c1 -> d0 
... 
a1 -> b2 -> c1 -> d1 

que estoy haciendo esto por "destruir" el árbol en sí, mientras que lo atraviesa i n de la siguiente manera:

public static void delete(Node node) { 
    if (node.isLeaf() && !node.isRoot()) { 
    Node parent = node.getParent(); 
    parent.removeChild(node); 
    delete(parent); 
    } 
} 

public static void traverse(Node node) { 
    if (node.isRoot()) 
    System.out.println("---"); 
    else 
    System.out.println(node.getName()); 

    if (node.isLeaf()) { // I'm still working on 
    if (!node.isRoot()) { // removing unnecessary checks 
     delete(node); 
     traverse(node.getRoot()); 
    } 
    } else { 
    Node child = node.firstChild(); 
    if (null != child) 
     traverse(child); 
    } 
}  

traverse(Node) siempre imprime la primera ruta disponible del árbol (de la raíz a la hoja), mientras que delete(Node) cortes hojas del árbol que ya es visitada por traverse(Node).

Esto funciona como estaba previsto, pero estoy dispuesto a encontrar una solución para atravesar el árbol de la manera descrita anteriormente sin destruirlo. Si hay una manera de hacerlo, me interesaría atravesar esta misma estructura, pero en forma de gráfico para reducir la redundancia.

Answer 1

OK. Creo que realmente quieres decir que quieres encontrar todos los caminos desde la raíz hasta la hoja.

Entonces (una versión no-optimizado)

void traverse (Node root) { 
    // assume root != NULL 
    traverse (root, new LinkedList<Node>()); 
} 

private void traverse (Node root, LinkedList<Node> path) { 
    path.add(root); 
    if (root.isLeaf()) { 
    print path; 
    } 
    else { 
    for each node of root { 
     traverse (node, new LinkedList<Node>(path)); 
    } 
    } 
} 

Answer 2

Así que, básicamente, que está haciendo una primera búsqueda en profundidad, pero en lugar de seguimiento de la visita de los nodos de forma explícita en una forma no destructiva, o el mantenimiento de suficiente contexto para buscar sin seguimiento, estás destruyendo el árbol para hacer este seguimiento.

La forma tradicional de convertir esto en un DFS normal sería lazo alrededor de su condición recursividad, básicamente cambiar la llamada recursiva niño a algo como:

} else { 
    for (Node child = node.firstChild(); node != null; node = node.nextChild()) { 
     traverse(child); 
    } 
} 

Este atravesará todos sus hijos, y se puede más o menos elimina el caso node.isLeaf, ya que el rastreo retroactivo se realiza automáticamente. Tenga en cuenta que inventé la función nextChild ya que no puedo ver cómo se llama en su código, pero debe tener algo similar, o alguna forma de iterar a través de los elementos secundarios.

Una forma alternativa que conserva más de la estructura de su código existente sería mantener una estructura de datos independiente que contiene un conjunto de "visitados" nodos, esto podría ser tan simple como un conjunto de cadenas si todos los nombres de los nodos son únicos: en lugar de eliminar el nodo, agregarlo al conjunto "visitado" y en su condición de recursión, no verifique nulo, sino que busque el primer nodo no visitado. Esto es probablemente más complicado que la sugerencia anterior, pero podría ser más similar a lo que tiene ahora, y evitaría bucles en el caso de que necesite hacer esto en un gráfico cíclico en lugar de hacerlo en un árbol.

Answer 3

Algo que me ocurrió con el trabajo en la impresión de las palabras en un TrieTree que pueden ser fácilmente adaptable a otros tipos de árboles o diferentes necesidades:

public void rootToLeaves() { 
    HashMap<Integer, TrieNode> hashMap = new HashMap<Integer, TrieNode>(); 
    for(TrieNode trieNode : root.getChildren()) 
     rootToLeaves(trieNode, hashMap, 0); 
} 

private void rootToLeaves(TrieNode trieNode, HashMap<Integer, TrieNode> hashMap, int heightIndex) { 
    hashMap.put(heightIndex, trieNode); 

    if(trieNode.isLeaf()) 
     printValues(hashMap, heightIndex); 
    else 
     for(TrieNode childNode : trieNode.getChildren()) 
      rootToLeaves(childNode, hashMap, heightIndex + 1); 
} 

private void printValues(HashMap<Integer, TrieNode> hashMap, int heightIndex) { 
    for(int index = 0; index <= heightIndex; index++) 
     System.out.print(hashMap.get(index).getValue()); 
    System.out.println(); 
} 

Esta solución hace un buen trabajo en cuanto a la gestión de memoria (Utiliza un solo HashMap cuyo tamaño nunca excederá la altura del árbol) y ofrece mucha flexibilidad (solo reemplace los valores de impresión con lo que necesite).

NOTA: Conocer la altura del árbol por adelantado le permitirá usar un simple Array en lugar de un Map.

Answer 4

1, Encuentra nodo hoja
2, hasta el recorrido desde el nodo hoja

public void printPath(N n) { 
     if (n == null) 
      return; 
     if (n.left == null && n.right == null) { 
      do { 
       System.out.print(n.value); 
       System.out.print(" "); 
      } while ((n = n.parent) != null); 
      System.out.println(""); 
      return; 
     } 
     printPath(n.left); 
     printPath(n.right); 
    } 

printPath (raíz);