Árbol de expresiones binarias - Enciclopedia

Un árbol de expresiones binarias es un tipo específico de árbol binario utilizado para representar expresiones. Dos tipos comunes de expresiones que puede representar un árbol de expresiones binarias son las algebraicas y las booleanas. Estos árboles pueden representar expresiones que contienen tanto operadores unarios como binarios.

Al igual que cualquier árbol binario, cada nodo de un árbol de expresiones binarias tiene cero, uno o dos hijos. Esta estructura restringida simplifica el procesamiento de los árboles de expresiones.

Construcción de un árbol de expresiones

= Ejemplo =
La entrada en notación postfix es: a b + c d e + * *
Dado que los primeros dos símbolos son operandos, se crean árboles de un nodo y los punteros a ellos se apilan en una pila. Por conveniencia, la pila se expandirá de izquierda a derecha.

El siguiente símbolo es un '+'. Se extraen los dos punteros a los árboles, se forma un nuevo árbol y se apila un puntero a él.

Continuando, se leen c, d y e. Se crea un árbol de un nodo para cada uno y se apila un puntero al correspondiente árbol.

Seguidamente, se lee un '+'. Se fusionan los últimos dos árboles.

Luego, se lee un '*'. Se extraen los dos últimos punteros de los árboles y se forma un nuevo árbol con '*' como raíz.

Finalmente, se lee el último símbolo. Se fusionan los dos árboles y se mantiene un puntero al árbol final en la pila.

Expresiones algebraicas

Los árboles de expresiones algebraicas representan expresiones que contienen números, variables y operadores unarios y binarios. Algunos de los operadores comunes son × (multiplicación), ÷ (división), + (adición), − (sustracción), ^ (potenciación) y - (negación). Los operadores están contenidos en los nodos internos del árbol, con los números y las variables en los nodos hoja. Los nodos de los operadores binarios tienen dos nodos hijos, y los operadores unarios tienen un nodo hijo.

Expresiones booleanas

Las expresiones booleanas se representan de manera muy similar a las algebraicas, la única diferencia es el valor específico y los operadores utilizados. Las expresiones booleanas utilizan verdadero y falso como valores constantes, y los operadores incluyen:


∧

(AND),

∨

(OR),

¬

(NOT).

Ver también
Expresión (matemáticas)
Término (lógica)
Gramática contextualmente libre
Árbol de análisis sintáctico
Árbol de sintaxis abstracta

Referencias