Buscar este blog

16 de enero de 2010


RECORRIDO DE ÁRBOLES BINARIOS
Existen tres modos estándar de recorrer un árbol binario T de raíz R. estos tres algoritmos denominados Preorden, inorden y postorden, son así:
Presorden:           (1) procesar  la raíz R
                                   (2) Recorrer el subárbol izquierdo de R en preorden
                                   (3) Recorrer el subárbol derecho de R en preorden
     Inorden
(1) recorrer el subárbol izquierdo de R en inorden
                        (2) procesar la raíz R
                        (3) recorrer el subárbol derecho de R en inorden
Postorden
(1) recorrer el subárbol izquierdo de R en postorden
                        (2) procesar la raíz R
                        (3) recorrer el subárbol derecho de R en postorden
    
Observe que cada algoritmo contiene los mismos tres pasos y que el subárbol izquierdo de R siempre se recorre antes que el subárbol derecho. La diferencia entre los algoritmos es el momento en que se procesa la raíz R. específicamente en e algoritmo <
>, la raíz R se procesa antes de recorrer l0os
árboles; en el algoritmo <>, la raíz R se procesa entre los dos
recorridos de los subárboles; y en le algoritmo <>, la raíz
se procesa tras recorrer los subárboles.
Los tres algoritmos se denominan a veces, respectivamente, recorrido nodo-izquierdo-nodo-derecha (de ingles, LNR) y recorrido izquierdo-derecho-nodo (LRN, del ingles).

No hay comentarios:

Publicar un comentario