Cruce iterativo a través del árbol para encontrar el tamaño

Question

Necesito encontrar el número de elementos en un árbol usando un algoritmo iterativo, pero el código me resulta conceptualmente muy difícil de escribir.

Mi enfoque es comenzar en el nodo raíz y visitar los nodos secundarios, luego los secundarios de estos nodos secundarios, y así sucesivamente.

Este es el código que he escrito, que trabaja para un pequeño árbol, pero no es una solución real, ya que había necesidad de añadir un bloque adicional para cada nivel de profundidad:

// Start the counter at 1 because the root node counts 
int size = 1; 

for(ITree child1 : root) { 
    size++; 
    for(ITree child2 : child1) { 
     size++; 
     for(ITree child3 : child2) { 
      size++; 
      for(ITree child4 : child3) { 
       size++; 
       for(ITree child5 : child4) { 
        size++; 
       } 
      } 
     } 
    } 
} 
return size; 

Answer 1

Conceptualmente , mantener una pila (LinkedList, etc.). Para cada niño (ahora, su hijo realiza un bucle), agregue a la pila. Continúa recorriendo la pila hasta que finalmente esté vacía.

Esto no ha sido probado, pero esto debería hacer exactamente lo que está buscando. Sólo estoy usando java.io.File en lugar de su "iTree", ya que es algo que pueda compilar en contra:

int sizeOfTree(File root){ 
    // Start the counter at 1 because the root node counts 

    int size = 1; 

    LinkedList<File> stack = new LinkedList<File>(); 
    stack.add(root); 

    while(!stack.isEmpty()){ 
     File f = stack.remove(); 
     for(File child : f.listFiles()){ 
      size++; 
      stack.add(child); 
     } 
    } 

    return size; 
} 

Answer 2

El uso de una estructura de datos recursiva

No es posible en la práctica para atravesar de manera iterativa un dato recursiva estructura, como un árbol con punteros; esto se debe al hecho de que los objetos "ocultan" sus elementos de datos subyacentes.

Uso de una estructura de datos diferente

Todos los árboles se pueden almacenar/implementan como a lineal, estructuras de datos de la matriz, en donde los índices pueden calcularse utilizando matemática exponencial:

Por ejemplo, un árbol de [0 , 1, 2, 3, nulo, 4, nulo] describiría un árbol con 0 en la raíz, donde 0 tenía hijos directos 1 y 2. Y luego 1 dejó al niño "3", y 2 dejó al niño "4" .

Por lo tanto, si almacena el árbol de esta manera, el número de elementos es, naturalmente, la cantidad de elementos no nulos en la matriz.

Más simple: almacene el árbol en una estructura lineal, y puede conocer la longitud en un momento dado sin tener que hacer ningún tipo de algoritmo de fantasía.

Answer 3

La palabra clave para su tarea es recursividad. Tree es una estructura recursiva clásica, por lo que debe escribir un método recursivo que acepte nodos raíz, cuente el tamaño de este nodo y luego se llame a sí mismo para todos los elementos secundarios. Aquí es pseudo código:

public int getSize(ITree root) { 
    return getSize(root, 0); 
} 

private int getSize(ITree node, int size) { 
    size++; 
    for(ITree child : node.children()) { 
     size += getSize(child, size) 
    } 
    return size; 
}