ejemplo de recorrido in

Ejemplo de recorrido In-orden: 

Supongan tenemos el árbol binario: 

Imprimiremos los elementos recorriéndolo In-Orden. Dado que esto es un procedimiento recursivo, tendremos que ir anotando lo que nos va quedando pendiente en cada llamado. Recuerden que el recorrido En-orden es así: 

Recorro el subárbol izquierdo.  Recorro la raíz.  Recorro el subárbol derecho.

Iremos llamando a llamado numerándolos. En cada ejemplo pondré en verde lo siguiente a realizar, en rojo lo que va quedando pendiente y en azul lo que ya hemos realizado. 

Llamado 1: Tengo el árbol de raíz 20 (el dibujo anterior). Entonces tenemos que hacer esto: 

** Debemos recorrer el subárbol izquierdo (el de raíz 1), lo cual es el Llamado 2. ** Imprimimos el número 20 (nuestra raíz actual). Esto queda pendiente hasta que terminemos de recorrer el subárbol izquierdo. ** Debemos recorrer el subárbol derecho (el de raíz 21). Esto quedará pendiente hasta que imprimamos el número 20. 

Llamado 2: Tenemos el subárbol de raíz 1: 

** Debemos recorrer el subárbol izquierdo (raíz 0). Este será el Llamado 3. ** Imprimimos el número 1 (raíz actual). 

** Debemos recorrer el subárbol derecho (raíz 6). 

Llamado 3: Tenemos el subárbol de raíz 0: 

** Debemos recorrer el subárbol izquierdo (vacío). Llamado 4. ** Imprimimos el número 0 (raíz actual). ** Debemos recorrer el subárbol derecho (vacío). 

Llamado 4: Tenemos un árbol vacío, por lo tanto no hay nada por hacer así que volvemos hacia el Llamado 3 a ver que teníamos pendiente. 

Llamado 3: Tenemos el subárbol de raíz 0: 

** Debemos recorrer el subárbol izquierdo (vacío). Llamado 4. ** Imprimimos el número 0 (raíz actual). ** Debemos recorrer el subárbol derecho (vacío). Llamado 5. 

Como ya hemos cumplido la primera instrucción de este llamado, ahora vamos a la segunda que consta simplemente de imprimir un 0, entonces la salida de nuestro programa será por ahora: 

Código:

0

Cumplido eso, vamos al Llamado 5. 

Llamado 5: Tenemos un árbol vacío. Tampoco hay nada por hacer. Volvemos al Llamado 3. 

Llamado 3: Hemos cumplido todas las instrucciones de este llamado. Como su invocación había sido hecha desde el Llamado 2, volvemos hacia él. 

** Debemos recorrer el subárbol izquierdo (vacío). Llamado 4. ** Imprimimos el número 0 (raíz actual). ** Debemos recorrer el subárbol derecho (vacío). Llamado 5. 

Llamado 2: Volvemos a tener el árbol de raíz 1: 

** Debemos recorrer el subárbol izquierdo (raíz 0). Este será el Llamado 3. ** Imprimimos el número 1 (raíz actual). ** Debemos recorrer el subárbol derecho (raíz 6). Llamado 6. 

Ahora debemos imprimir la raíz del árbol, es decir el 1. Con eso nuestra salida queda ahora: 

Código:

0 1

Hecho eso debemos ahora ir a la tercera instrucción de este llamado, recorrer el árbol de raíz 6. 

Llamado 6: Tenemos el árbol de raíz 6: 

Al igual que en el llamado 3, cuando solo teníamos el nodo 0, este llamado acabará por imprimir el 6 en pantalla, quedando nuestra salida así: 

Código:

0 1 6

Como este llamado fue hecho desde el llamado 2 debemos volver a él. 

Llamado 2: Hemos realizado todas las instrucciones de este llamado: ** Debemos recorrer el subárbol izquierdo (raíz 0). Este será el Llamado 3. ** Imprimimos el número 1 (raíz actual). ** Debemos recorrer el subárbol derecho (raíz 6). Llamado 6. 

Hecho eso, como este llamado fue realizado desde el llamado 1, volvemos a él. 

Llamado 1: Tenemos nuevamente el árbol de raíz 20. Las instrucciones están así: ** Debemos recorrer el subárbol izquierdo (el de raíz 1), lo cual es el Llamado 2. ** Imprimimos el número 20 (nuestra raíz actual). Esto queda pendiente hasta que terminemos de recorrer el subárbol izquierdo. ** Debemos recorrer el subárbol derecho (el de raíz 21). Esto quedará pendiente hasta que imprimamos el número 20. 

De este modo ahora debemos imprimir el 20, quedando nuestra salida así: 

Código:

0 1 6 20

Nuestras instrucciones están así: 

** Debemos recorrer el subárbol izquierdo (el de raíz 1), lo cual es el Llamado 2. ** Imprimimos el número 20 (nuestra raíz actual). Esto queda pendiente hasta que terminemos de recorrer el subárbol izquierdo. ** Debemos recorrer el subárbol derecho (el de raíz 21). Esto quedará pendiente hasta que imprimamos el número 20. 

Para realizar la última instrucción de este llamado tendríamos un nuevo llamado el cual derivaría en nuevos llamados a su vez. Lo que quiero es que noten que la salida ha ido quedando ordenada de menor a mayor, y así acabaríamos por imprimir todo el árbol.