5.2.4 Recorridos Sistematicos

Una vez que se crea el árbol binario, se pueden realizar otras operaciones sobre sus elementos: recorrer todos los nodos, insertar un nuevo nodo, eliminar alguno de los existentes o buscar un valor determinado.

Una de las operaciones más importantes que se realiza en un árbol binario es el recorrido de los mismos. Recorrer significa visitar los nodos del árbol en forma ordenada, de tal manera que todos los nodos del mismo sean visitados una sola vez. Existen tres formas diferentes de efectuar el recorrido y todas ellas de naturaleza recursiva; estas son:

a) Recorrido en preorden 
          Visitar la raíz
          Recorrer el subárbol izquierdo
          Recorrer el subárbol derecho

b) Recorrido en inorden
          Recorrer el subárbol izquierdo
          Visitar la raíz
          Recorrer el subárbol derecho

c) Recorrido en posorden
          Recorrer el subárbol izquierdo
          Recorrer el subárbol derecho
          Visitar la raíz

Se analizan a continuación los algoritmos que efectúan los diferentes tipos de recorridos en un árbol binario.

Recorrido Preorden

Preorden (APNODO)
Este algoritmo realiza el recorrido preorden de un árbol binario. APNODO es un dato de tipo ENLACE puntero a un nodo
INFO, IZQ y DER son campos del registro nodo. INFO es una variable de tipo carácter. IZQ  y DER son variables de tipo puntero

1. Si (APNODO ≠ NULO)
    entonces
          Visitar el APNODO Escribir NODO^.INFO
          Regresar a Preorden con APNODO^.IZQ
                    Llamada recursiva a Preorden con la rama izquierda del nodo en cuestión
          Regresar a Preorden con APNODO^.DER
                 Llamada recursiva a Preorden con la rama derecha del nodo en cuestión
2. Fin del condicional del paso 1

Nota: Cabe destacar que el termino visitar se puede reemplazar por cualquier otra instrucción valida, por ejemplo escribir, sumar o comparar la información del nodo. Note que esta aclaración se aplica también para los otros tipos de recorridos.

Recorrido Inorden 

Inorden (APNODO)
Este algoritmo realiza el recorrido inorden de un árbol binario. APNODO es un registro tipo ENLACE puntero a un nodo INFO, IZQ y DER son campos del registro nodo. INFO es una variable de tipo carácter. IZQ y DER son variables de tipo puntero

1. Si (APNODO ≠ NULO)
         entonces
                  Regresar a Inorden con APNODO^.IZQ
                   Llamada recursiva a Inorden con la rama izquierda del nodo en cuestión
                  Visitar el APNODO Escribir APNODO^.INFO
                  Regresar a Inorden con APNODO^.DER
                        Llamada recursiva a Inorden con la rama derecha del nodo en cuestión
2. Fin del condicional del paso 1

Recorrido Posorden

Posorden (APNODO)
 Este algoritmo realiza el recorrido posorden de un árbol binario.  APNODO es un dato tipo ENLACE puntero a un nodo INFO, IZQ y DER son campos del registro nodo.  INFO es una variable de tipo carácter. IZQ y DER son variables de tipo puntero

1. Si (APNODO ≠ NULO)
         entonces
                  Regresar a Posorden con APNODOMZQ
                    Llamada recursiva a Posorden con la rama izquierda del nodo en cuestión
                  Regresar a Posorden con APNODOA.DER
                       Llamada recursiva a Posorden con la rama derecha del nodo en cuestión
                  Visitar el APNODO Escribir APNODOMNFO
2. Fin del condicional del paso 1