-3

Hay alguna forma de hacer un recorrido inorden y postorden de un arbol binario sin usar recursividad?

2
  • 2
    por favor revisa Cómo preguntar asi como preguntas ahorita es amplia basada en opiniones; por lo cual pudiera terminar cerrada
    – user75901
    el 12 dic. 2018 a las 23:42
  • Sí, la alternativa más común es usar ciclos y estructuras de control. el 12 dic. 2018 a las 23:58

1 respuesta 1

-2

Si se puede, por ejemplo, utilizando iteraciones y una pila.

El pseudo-código para realizar el recorrido in-order sería como este:

  1. Crear una pila vacía
  2. Tener a disposición el nodo raíz del arbol y asignarlo a la variable `actual`
  3. 
     3.1 Hacer `push` del nodo `actual` a la pila
     3.2 Asignar `actual.nodoIzquierdo` a `actual`
     3.3 repetir el paso 3 hasta que `actual` sea NULL
  4. Si `actual` es NULL y la pila no está vacía entonces
     4.1   Recuperar un elemento de la pila en la variable `temp` e imprimirlo.
     4.2   Asignar `temp.nodoDerecha` a la variable `actual` 
  5. Si `actual` es distinto de NULL o la pila no está vacía, ir al paso 3

Una corrida de prueba sería como esta:

Tenemos el árbol:

            1
          /   \
        2      3
      /  \
    4     5

1. creamos una pila vacía: pila = NULL
2. actual -> 1
3.                                               actual = 1
    3.1 pila.push(actual) => pila = 1
    3.2 actual -> 2

    3.1 pila.push(actual) => pila = 2, 1
    3.2 actual -> 4

    3.1 pila.push(actual) => pila = 4, 2, 1
    3.2 actual -> NULL
4.                                                actual = NULL
                                                  pila = 4, 2, 1
    4.1 temp = pila.pop(); => temp = 4, 
                                                  salida = 4
    4.2 actual -> NULL
5.                                                actual = NULL
                                                  pìla = 2, 1
    3.1 actual = NULL, no hace nada
4.                                                actual = NULL
                                                  pila = 2, 1
    4.1 temp = pila.pop(); => temp = 2 
                                                  salida = 4,2
    4.2 actual -> 5
5.                                                actual = 5
                                                  pìla = 1
    3.1 pila.push(actual) => pila = 5, 1
    3.2 actual -> NULL
4.                                                actual = NULL
                                                  pila = 5, 1
    4.1 temp = pila.pop(); => temp = 5 
                                                  salida = 4,2,5
    4.2 actual -> NULL
5.                                                actual = NULL
                                                  pìla = 1
    3.1 actual = NULL, no hace nada
4.                                                actual = NULL
                                                  pila = 1
    4.1 temp = pila.pop(); => temp = 1 
                                                  salida = 4,2,5,1
    4.2 actual -> 3
5.                                                actual = 3
                                                  pìla = (vacía)
    3.1 pila.push(actual) => pila = 3
    3.2 actual -> NULL
4.                                                actual = NULL
                                                  pila = 3
    4.1 temp = pila.pop(); => temp = 3 
                                                  salida = 4,2,5,1,3
    4.2 actual -> NULL
5.                                                actual = NULL
                                                  pìla = (vacía)
    Por tanto, termina el proceso.

El resultado en la salida es el esperado:

4,2,5,1,3

Utilizando esta misma técnica puedes hacer cualquier recorrido en el árbol.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.