RECORRIDO DE LOS ARBOLES BINARIOS

RECORRIDO EN ARBOLES BINARIOS

Una de las operaciones mas importantes a realizar en un árbol binario es el recorrido de los mismos, recorrer significa visitar los nodos del árbol en forma sistemática, de tal manera que todos los nodos del mismo sean visitados una sola vez.

Existen 3 formas diferentes  de efectuar el recorrido y todas ellas de naturaleza recursiva, estas son:

RECORRIDO PREORDEN: En el que se procesa el nodo y después se procesan recursivamente sus hijos.

RECORRIDO POSTORDEN: Donde el nodo dado se procesa después de haber procesado recursivamente a sus hijos.

RECORRIDO INORDEN: En este se procesa recursivamente el hijo izquierdo, luego se procesa el nodo actual y finalmente se procesa  recursivamente el hijo derecho.

Hay un último recorrido que implementa a estos 3.

RECORRIDI POR NIVELES: Este recorrido procesa los nodos comenzando en la raíz y avanzando de forma descendente y de izquierda a derecha.

RECORRIDO PREORDEN

• VISITAR LA RAIZ
• RECORRER EL SUBARBOL IZQUIERDO
• RECORRER EL SUBARBOL DERECHO

Recorrido en preorden: consiste en visitar el nodo actual (visitar puede ser simplemente mostrar la clave del nodo por pantalla), y después visitar el subárbol izquierdo y una vez visitado, visitar el subárbol derecho. Es un proceso recursivo por naturaleza.

                                           PREORDEN: A-B-D-E-C-F-G

ALGORITMO

El algoritmo realiza el recorrido preorden en un árbol binario.

NODO es un dato de tipo puntero.

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 NODO ≠ NULL

entonces

      Visitar  el NODO { Escribir NODO^.INFO}

      Regresar a PREORDEN con NODO^.IZQ

      {Llamada recursiva a preorden  con la rama izquierda del nodo en cuestión}

     Regresa a PREORDEN  con NODO^.DER

     {Llamada recursiva a preorden  con la rama derecha del nodo en cuestión}

2. Fin del condicional del paso I

CODIGO

void preorden(tArbol *a)

{

  if (a != NULL) {

    Visitar(a);             //Realiza una operación en nodo

    preorden(a->hIzquierdo);

    preorden(a->hDerecho);

  }

}