Arboles

RECORRIDO EN ARBOLES
Orlando Arboleda Molina
´ Escuela de Ingenier´a de Sistemas y Computacion de ı La Universidad del Valle

16 de septiembre de 2008

Contenido

´ Recorrido en arboles ´ Definicion Recorrido en Preorden Recorrido en Inorden Recorrido en Postorden ´ Expresion infija ´ Expresion prefija ´ Expresion postfija

Contenido

´ Recorrido en arboles ´ Definicion Recorrido enPreorden Recorrido en Inorden Recorrido en Postorden ´ Expresion infija ´ Expresion prefija ´ Expresion postfija

´ Recorrido en arboles

´ Los arboles ordenados con ra´z se utilizan frecuentemente ı ´ para almacenar la informacion. Necesitamos procedimientos ( algoritmos de recorrido de un ´ ´ arbol ) que permitan visitar cada uno de los vertices para acceder a los datos. ´ Los 3 algoritmos derecorrido de un arbol mas conocidos son: Recorrido en preorden. Recorrido en inorden. Recorrido en postorden.

Contenido

´ Recorrido en arboles ´ Definicion Recorrido en Preorden Recorrido en Inorden Recorrido en Postorden ´ Expresion infija ´ Expresion prefija ´ Expresion postfija

Recorrido en Preorden
´ Sea T un arbol ordenado con ra´z r . ı ´ Si T consta solo de r , entonces r es elrecorrido preorden de T . ´ Sino, suponga que T1 , T2 , . . . , Tn son los subarboles en r listados de izquierda a derecha en T . El recorrido en preorden inicia visitando r , continua recorriendo T1 en preorden, luego T2 , en preorden, y as´ sucesivamente hasta recorrer Tn en ı preorden. Procedimiento Preorden ( T : arbol ordenado con raiz) r = raiz de T mostrar (r ) Para cada hijo c de r de izquierda aderecha T (c) = subarbol con c como su raiz Preorden(T (c)) Fin Para Fin Procedimiento

Recorrido en Preorden (2)

´ Figura: Ejemplo de un arbol

´ Ejemplo: El recorrido en Preorden del arbol de ejemplo es: a, b, e, f, l, m, g, c, h, i, d, j, n, o,k, p, q.

Contenido

´ Recorrido en arboles ´ Definicion Recorrido en Preorden Recorrido en Inorden Recorrido en Postorden ´ Expresion infija´ Expresion prefija ´ Expresion postfija

Recorrido en Inorden

´ Sea T un arbol ordenado con ra´z r . ı ´ Si T consta solo de r , entonces r es el recorrido en inorden de T. ´ Sino, suponga que T1 , T2 , . . . , Tn son los subarboles en r listados de izquierda a derecha en T . El recorrido en inorden inicia recorriendo T1 en inorden y continua visitando r , a ´ ´ continuacion recorre T2 eninorden, luego T3 , en inorden, y asi sucesivamente hasta recorer Tn en inorden.

Recorrido en Inorden (2)
Procedimiento Inorden ( T : arbol ordenado con raiz) r = raiz de T Si r es una hoja mostrar (r ) Sino l = primer hijo de r de izquierda a derecha T (l) = subarbol de raiz l Inorden (T (l)) mostrar (T (l)) Para cada hijo c de r excepto para l y de izquierda a derecha T (c) = subarbol de raiz cInorden(T (c)) Fin Para Fin Si Fin Procedimiento

Recorrido en Inorden (3)

´ Figura: Ejemplo de un arbol

´ Ejemplo: El recorrido en Inorden del arbol de ejemplo es: e, b, l, f, m, g, a, h, c, i, n , j , o, d, p , k, q.

Contenido

´ Recorrido en arboles ´ Definicion Recorrido en Preorden Recorrido en Inorden Recorrido en Postorden ´ Expresion infija ´ Expresion prefija ´ Expresionpostfija

Recorrido en Postorden
´ Sea T un arbol ordenado con ra´z r . ı ´ Si T consta solo de r , entonces r es el recorrido en postorden de T . ´ Sino, suponga que T1 , T2 , . . . , Tn son los subarboles en r listados de izquierda a derecha en T . El recorrido en postorden inicia recorriendo T1 en postorden, luego recorre T2 en postorden y as´ sucesivamente hasta recorrer Tn en postorden ı yfinaliza visitando r . Procedimiento Postorden ( T : arbol ordenado con raiz ) r = raiz de T Para cada hijo c de r de izquierda a derecha T (c) = subarbol de raiz c Postorden(T (c)) Fin Para mostrar (r ) Fin Procedimiento

Recorrido en Postorden (2)

´ Figura: Ejemplo de un arbol

´ Ejemplo: El recorrido en Postorden del arbol de ejemplo es: e, l, m, f, g, b, h, i, c, n, o, j, p, q, k, d, a....