Tecnolgico de Estudios Superiores de Jocotitlan

Lenguajes y Autmatas 2

Erika Cortez Nazar

Arboles de expresiones

Juan Carlos Cruz Molina

Luis Enrique Lpez Nieto

Juan pablo Snchez Crisstomo

Hugo Dvila Carrillo

Presentan

Un rbol es un conjunto finito de nodos.

Es una estructura jerrquica aplicable sobre una coleccin de elemento u objetos llamados nodos; uno de los cuales es conocido como raz.

DEFINICION

Los rboles representan las estructuras no lineales y dinmicas, de una expresin.

No lineales, puesto que a cada elemento del rbol pueden seguirle varios elementos.

Dinmicas, puesto que la estructura del rbol puede cambiar durante la ejecucin del programa.

CARACTERISTICAS

Se utilizan para representar expresiones en memoria, esencialmente en compiladores de lenguajes de programacin

Ejemplo: a + b

Arboles de expresiones

+

a b

Expresin: (A+B)

Los parntesis no se almacenan en el rbol pero estn implicados en la forma del rbol.

Si se supone que todos los operadores tienen dos operandos, se puede representar una expresin por un rbol binario cuya raz contiene un operador

CONSTRUCCION DE RBOLES DE EXPRESION

+

a b

Cada hoja esta etiquetada con su propio operando y solo consta de ese operando, por ejemplo n1 representa el operando a, de la expresin (a+b)

n2

n1 n3

Recorrer un rbol binario significa visitar los nodos del rbol en forma sistemtica, de tal manera que todos los nodos del mismo sean visitados una sola vez.

Tipos de recorridos de rbol

Existen tres formas diferentes de efectuar el recorrido (todos de forma recursiva) los cuales son:

Recorrido en Pre orden

Recorrido en In orden

Recorrido en Pos orden

Recorrido de arboles binarios

Visitar raz (escribir la informacin del nodo).

Recorrer el subrbol izquierdo en pre orden.

Recorrer el subrbol derecho en pre orden.

Recorrido en Pre orden

Recorrer el subrbol izquierdo en In orden

Visitar raz (procesar el valor en el nodo).

Recorrer el subrbol derecho en In orden

RECORRIDO EN INORDEN

Recorrer el subrbol izquierdo en Pos orden

Recorrer el subrbol derecho en Pos orden

Visitar raz (procesar el valor en el nodo).

RECORRIDO EN POSORDEN