Análisis y Diseño de Algoritmos                                                                                                      

Prof: Ing. Victor Garro

Asistente: Marco Elizondo Vargas

 

Árboles

 

Tipos de recorridos sobre Árboles

 

Recorridos en Profundidad: se alejan cuanto antes de la raíz.

 

Tipo de Recorrido	Secuencia de nodos
Pre Orden	{ 5; 3; 1; 4; 8; 6; 9 }
Post Orden	{ 1; 4; 3; 6; 9; 8; 5 }
Orden Central	{ 1; 3; 4; 5; 6; 8; 9 }

 

Recorridos en Amplitud: trata consecutivamente los nodos que se encuentran al mismo nivel

 

Tipo de Recorrido	Secuencia de nodos
Amplitud	{ 5; 3; 8; 1; 4; 6; 9 }

 

 

Codificación

Recorridos en Profundidad: Son todos recursivos y requieren una pila para su implementación.

 

PREORDEN: procesar primero el subárbol izquierdo, luego el subárbol derecho y luego la raíz. 

 

Procedure PreOrden ( a: TArbol );

begin

if a <> nil then

begin

writeln ( a^.Clave ); (* Procesar Raíz *)

PreOrden ( a^.Izq );

PreOrden ( a^.Der )

end

end;

 

 

POSTORDEN: procesar primero el subárbol izquierdo, luego el subárbol derecho y luego la raíz.

 

Procedure PostOrden ( a: TArbol );

begin

if a<> nil then

begin

PostOrden ( a^.Izq );

PostOrden ( a^.Der );

writeln( a^.Clave ) (* Procesar Raíz *)

end

end;

 

 

ORDEN CENTRAL: procesar primero el subárbol izquierdo, luego la raíz y luego el subárbol derecho.

 

Procedure OrdenCentral ( a: TArbol );

begin

if a<> nil then

begin

OrdenCentral ( a^.Izq );

writeln ( a^.Clave ); (* Procesar Raíz *)

OrdenCentral ( a^.Der )

end

end;

 

Recorridos en Amplitud: Es imprescindible la utilización de una cola y no está aconsejada la recursividad.

 

Procedure Amplitud ( a: TArbol );

(* Se utiliza una cola para efectuar un recorrido por niveles *)

var Cola: TCola;

Aux: TArbol;

begin

InicializarCola ( Cola );

Encolar ( Cola, a ); (* raíz del árbol original*)

while Not Vacia ( Cola ) do

begin

Desencolar ( Cola, Aux );

if Aux<> NIL then

begin

writeln ( Aux^.Clave );

Encolar ( Cola, Aux^.Izq ); (* subárbol izquierdo *)

Encolar ( Cola, Aux^.Der ) (* subárbol derecho *)

end

end;

 

Características y Utilidades de los Recorridos.

PREORDEN: Se va a utilizar siempre que queramos comprobar alguna propiedad del árbol ( p.ej.: localizar elementos ).

ORDENCENTRAL: Se utiliza siempre que nos pidan algo relativo a la posición relativa de las claves o algo que tenga que ver con el orden de las claves ( p.ej.: ¿Cuál es la 3ª clave?).

POSTORDEN: Se utiliza poco. Su principal utilidad consiste en liberar la memoria ocupada por un árbol.

AMPLITUD: Se utiliza siempre que nos pidan operaciones cuyo tratamiento se haga por niveles.