Árboles de expresiones

¿Qué son los arboles de expresiones?

Los árboles de expresiones son estructuras de datos que definen código. Se basan en las mismas estructuras que usa un compilador para analizar el código y generar el resultado compilado.

Una expresión es una secuencia de tokens (componentes de léxicos que siguen unas reglas establecidas). Un token puede ser un operando o bien un operador.

Un árbol de expresión es un árbol binario con las siguientes propiedades:

1. Cada hoja es un operando.

2. Los nodos raíz y los nodos internos son operadores.

3. Los subárboles son subexpresiones cuyo nodo raíz es un operador.

Un árbol es una estructura de datos no lineal, en la que cada elemento (nodo) tiene un único elemento anterior denominado padre, y puede tener más de un elemento siguiente (hijos del nodo).

Los árboles representan las estructuras no lineales y dinámicas. No lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos. Dinámicas, puesto que la estructura árbol puede cambiar durante la ejecución del programa.

Relación entre nodos:

·        El que está por encima se llama padre y, el de abajo, hijo.

·        El nodo raíz es el que no tiene padre.

·        Los nodos hoja son aquellos que no tienen hijos.

·        Nodos hermanos son aquellos que comparten padre.

·        Un nodo interior es aquel que tiene hijos. En caso contrario, se dice que el nodo es exterior.

·        La profundidad de un nodo es el número de relaciones padre-hijo que hay que seguir entre el nodo y la raíz del árbol.

Tabla de árbol de expresiones

^	Izquierda - derecha
*   /	Izquierda - derecha
+   -	Izquierda - derecha

Ejercicio 1: 

3*5+6-7*8-4      =    -39

Ejercicio 2:   

 5+6*9-5*9+6+7*5      =     55

Ejercicio 3:

15-9*7/5+3+6/9*6    =    9.4

Ejercicio 4: 

11*6+5/9*6+4*7    =   97.3333

Ejercicio 5:

9+6*7/4-7*4/7-5      =     10.5

Ejercicio 6: 

15*6-4+3/7*3-4*6/9    =   84.61

Ejercicio 7:

6*4+9-3/2*8+4/7*4     =     23.28