Los árboles binarios se utilizan para almacenar expresiones aritméticas en memoria, esencialmente en compiladores de lenguajes de programación. 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.
Los paréntesis no se almacenan en el árbol pero están implicados en la forma del árbol, como puede apreciarse en la Figura 14:
La Figura 15 representa la expresión infija a * (b + c) + d junto a su árbol de expresión. El nombre de infija es debido a que los operadores se sitúan entre los operandos.
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.
Los árboles binarios se utilizan para representar expresiones en memoria, esencialmente en compiladores de lenguajes de programación. Se observa que los paréntesis de la expresión no aparecen en el árbol, pero están implicados en su forma, y esto resulta muy interesante para la evaluación de la expresión.
Si se supone que todos los operadores tienen dos operandos, se puede representar una expresión mediante un árbol binario cuya raíz contiene un operador y cuyos subárboles izquierdo y derecho son los operandos izquierdo y derecho, respectivamente. Cada operando puede ser una letra (x, y, a, b, etc.) o una subexpresión representada como un subárbol.
La Figura 16 muestra un árbol cuya raíz es el operador *,
su subárbol izquierdo representa la subexpresión (x + y)
y su subárbol derecho representa la subexpresión (a - b).
El nodo raíz del subárbol izquierdo contiene el operador (+) de la subexpresión izquierda y el nodo raíz del subárbol derecho contiene el operador (-) de la subexpresión derecha. Todos los operandos letras se almacenan en nodos hojas.
Utilizando el razonamiento anterior, la expresión (x * (y - z)) + (a - b) con paréntesis alrededor de las subexpresiones, forma el árbol binario de la Figura 16.
Ejemplos:
Bibliografia:
http://artemisa.unicauca.edu.co/~cardila/ED2__Arboles_Binarios_02.pdf
No hay comentarios:
Publicar un comentario