Un árbol es un forma natural de representar la estructura de una expresión. Al contrario que otras notaciones, puede representar el cálculo de forma no ambigua. Por ejemplo, la expresión 1 + 2 * 3 es ambigua a no ser que sepamos que la multiplicación se realiza antes que la suma.
Éste árbol de expresión representa el mismo cálculo:
Los nodos de un árbol de expresión pueden ser operandos como 1 y 2 u operadores como + y *. Los operandos son nodos hojas; los nodos operadores contienen referencias a sus operandos. (Todos estos operadores son binarios, lo que significa que tienen exactamente dos operandos.)
Ası́ podemos construir este árbol:
Mirando la figura, no hay duda del orden de las operaciones; la multiplicación se realiza antes para calcular el segundo operando de la suma.
Los árboles de expresión tienen muchos usos. El ejemplo de este capı́tulo usa árboles para traducir expresiones a postfijo, prefijo e infijo. Árboles similares se usan dentro de los compiladores para analizar, optimizar y traducir programas.
Debe estar conectado para enviar un comentario.