Arboles

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 formasistemá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:

RECORRIDOPREORDEN: 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 aestos 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.

[pic]

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

ALGORITMO
El algoritmorealiza 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 tipopuntero.

1. si NODO ≠ NULL
entonces
Visitar el NODO { Escribir NODO^.INFO}

Regresar a PREORDEN con NODO^.IZQ
{Llamada recursiva a preorden con la ramaizquierda 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...