Postorder and binary tree inorder without recursion - JAVA [closed]

-3

Is there any way to make an inorder and bidder path of a binary tree without using recursion?

    
asked by parachutes94 13.12.2018 в 00:38
source

1 answer

-2

If you can, for example, using iterations and a stack.

The pseudo-code to perform the in-order route would be like this:

  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

A test run would be like this:

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.

The output result is as expected:

4,2,5,1,3

Using this same technique you can do any route in the tree.

    
answered by 13.12.2018 / 01:46
source