Un árbol de expresión binaria es un tipo específico de árbol binario que se utiliza para representar expresiones . Dos tipos comunes de expresiones que un árbol de expresión binaria puede representar son las algebraicas [1] y las booleanas . Estos árboles pueden representar expresiones que contienen operadores tanto unarios como binarios . [1]
Como cualquier árbol binario, cada nodo de un árbol de expresión binaria tiene cero, uno o dos hijos. Esta estructura restringida simplifica el procesamiento de los árboles de expresión.
La entrada en notación posfija es: ab + cde + * * Dado que los dos primeros símbolos son operandos, se crean árboles de un nodo y los punteros a ellos se colocan en una pila. Para mayor comodidad, la pila crecerá de izquierda a derecha.
El siguiente símbolo es un "+". Hace estallar los dos punteros a los árboles, se forma un nuevo árbol y se coloca un puntero a él en la pila.
A continuación, se leen c, d y e. Se crea un árbol de un nodo para cada uno y se inserta en la pila un puntero al árbol correspondiente.
Continuando, se lee un '+' y se fusionan los dos últimos árboles.
Ahora se lee un '*'. Se eliminan los dos últimos punteros del árbol y se forma un nuevo árbol con un '*' como raíz.
Finalmente, se lee el último símbolo. Los dos árboles se fusionan y queda en la pila un puntero al árbol final. [2]
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 ), + ( suma ), − ( resta ), ^ ( exponenciació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 . [1] Los nodos de los operadores binarios tienen dos nodos secundarios , y los operadores unarios tienen un nodo secundario.
Las expresiones booleanas se representan de forma muy similar a las expresiones algebraicas, la única diferencia son los valores y operadores específicos utilizados. Las expresiones booleanas utilizan verdadero y falso como valores constantes, y los operadores incluyen ( AND ), ( OR ), ( NOT ).
