Árbol de expresiones binarias

Un árbol de expresiones binarias es un tipo específico de árbol binario que se utiliza para representar expresiones . Dos tipos comunes de expresiones que puede representar un árbol de expresiones binarias son las algebraicas ^{[ 1 ]} y las booleanas . Estos árboles pueden representar expresiones que contienen operadores tanto unarios como binarios . ^{[ 1 ]}

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 posfija es: ab + cde + * * Dado que los dos primeros símbolos son operandos, se crean árboles de un nodo y se insertan punteros a ellos en una pila. Para mayor comodidad, la pila crecerá de izquierda a derecha.

El siguiente símbolo es un '+'. Este símbolo elimina los dos punteros a los árboles, se forma un nuevo árbol y se agrega un puntero a este a 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.

A continuación, 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 un puntero al árbol final en la pila. ^{[ 2 ]}

Pasos para construir un árbol de expresiones ab + cde + * *

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 ), + ( suma ), − ( resta ), ^ ( exponenciación ) y - ( negación ). Los operadores se encuentran en los nodos internos del árbol, mientras que los números y las variables están en los nodos hoja . ^{[ 1 ]} Los nodos de operadores binarios tienen dos nodos hijos , y los operadores unarios tienen un nodo hijo.

expresiones booleanas

{\displaystyle \lor } — Árbol de expresiones booleanas binarias equivalente a ((verdadero $\lor$ FALSO) $\land$ $\neg$ FALSO) $\lor$ (verdadero $\lor$ FALSO))

Las expresiones booleanas se representan de forma muy similar a las expresiones algebraicas, siendo la única diferencia los valores y operadores específicos utilizados. Las expresiones booleanas utilizan verdadero y falso como valores constantes, y los operadores incluyen: $\land$ ( Y ), $\lor$ ( O ), $\neg$ ( NO ).

Véase también

Referencias

1 2 3 Bruno R. Preiss (1998). "Árboles de expresiones" . Archivado del original el 19 de enero de 2017. Recuperado el 20 de diciembre de 2010 .
↑ Gopal, Arpita. Estructuras de datos ampliadas . PHI Learning, 2010, pág. 353.

[brpreiss-1] 1 2 3 Bruno R. Preiss (1998). "Árboles de expresiones" . Archivado del original el 19 de enero de 2017. Recuperado el 20 de diciembre de 2010 .

[Gopal2010.353-2] Gopal, Arpita. Estructuras de datos ampliadas . PHI Learning, 2010, pág. 353.

[ 1 ]

[ 2 ]