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 puede representar un árbol de expresiones binarias son algebraicas [1] y booleanas . Estos árboles pueden representar expresiones que contienen operadores unarios y binarios . [1]
Cada nodo de un árbol binario y, por tanto, de un árbol de expresión binaria, tiene cero, uno o dos hijos. Esta estructura restringida simplifica el procesamiento de árboles de expresión.
Descripción general
Las hojas de un árbol de expresión binaria son operandos, como constantes o nombres de variables, y los otros nodos contienen operadores. Estos árboles en particular resultan ser binarios, porque todas las operaciones son binarias, y aunque este es el caso más simple, es posible que los nodos tengan más de dos hijos. También es posible que un nodo tenga un solo hijo, como es el caso del operador menos unario. Un árbol de expresión, T , puede evaluarse aplicando el operador en la raíz a los valores obtenidos evaluando recursivamente los subárboles izquierdo y derecho. [2]
El recorrido
Se puede producir una expresión algebraica a partir de un árbol de expresión binaria produciendo recursivamente una expresión izquierda entre paréntesis, luego imprimiendo el operador en la raíz y finalmente produciendo de forma recursiva una expresión derecha entre paréntesis. Esta estrategia general (izquierda, nodo, derecha) se conoce como recorrido en orden . Una estrategia de recorrido alternativa es imprimir de forma recursiva el subárbol izquierdo, el subárbol derecho y luego el operador. Esta estrategia de recorrido se conoce generalmente como recorrido posterior a la orden . Una tercera estrategia es imprimir primero el operador y luego imprimir de forma recursiva el subárbol izquierdo y derecho conocido como recorrido de preorden. [2]
Estos tres recorridos estándar de profundidad primero son representaciones de los tres formatos de expresión diferentes: infijo, sufijo y prefijo. Una expresión infija es producida por el recorrido de orden, una expresión de sufijo es producida por el recorrido de orden posterior y una expresión de prefijo es producida por el recorrido de orden previa. [3]
Infijo transversal
Cuando se imprime una expresión infija, se debe agregar un paréntesis de apertura y cierre al principio y al final de cada expresión. Como cada subárbol representa una subexpresión, se imprime un paréntesis de apertura al principio y el paréntesis de cierre se imprime después de procesar todos sus hijos.
Pseudocódigo:
Algoritmo infijo ( árbol ) / * Imprime la expresión infijo para un árbol de expresión. Pre: árbol es un puntero a un árbol de expresión de la publicación: la expresión infija ha sido impreso * / si ( árbol no se vacía ) si ( árbol símbolo es el operador ) de impresión ( abierta entre paréntesis ) final si infija ( árbol de la izquierda subárbol ) de impresión ( árbol símbolo ) infija ( árbol de la derecha subárbol ) si ( árbol símbolo es el operador ) de impresión ( cerca paréntesis ) final si final si final infija
Recorrido de sufijo
La expresión de sufijo está formada por el recorrido de postorder básico de cualquier árbol binario. No requiere paréntesis.
Pseudocódigo:
Postfijo de algoritmo ( árbol ) / * Imprime la expresión de sufijo para un árbol de expresión. Pre: árbol es un puntero a un árbol de expresión de la publicación: la expresión de sufijo se ha impreso * / si ( árbol de no vaciar ) postfix ( árbol de la izquierda subárbol ) postfix ( árbol de la derecha subárbol ) de impresión ( árbol simbólico ) final si final de sufijo
Prefijo transversal
Pseudocódigo:
Prefijo de algoritmo ( árbol ) / * Imprime la expresión de prefijo para un árbol de expresión. Pre: árbol es un puntero a un árbol de expresión de la publicación: la expresión prefijo ha sido impreso * / si ( árbol de no vaciar ) de impresión ( árbol simbólico ) prefijo ( árbol de la izquierda subárbol ) prefijo ( árbol de la derecha subárbol ) final si final prefijo
Construcción de un árbol de expresión
La construcción del árbol se lleva a cabo leyendo la expresión de sufijo un símbolo a la vez. Si el símbolo es un operando, se crea un árbol de un nodo y su puntero se inserta en una pila . Si el símbolo es un operador, los punteros a dos árboles T1 y T2 se extraen de la pila y se forma un nuevo árbol cuya raíz es el operador y cuyos hijos izquierdo y derecho apuntan a T2 y T1 respectivamente. A continuación, se envía un puntero a este nuevo árbol a la pila. [4]
Ejemplo
La entrada en notación postfija es: ab + cde + * * Dado que los dos primeros símbolos son operandos, se crean árboles de un nodo y los apuntadores a ellos se colocan en una pila. Por conveniencia, 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 empuja un puntero hacia él en la pila.
A continuación, se leen c, dye. Se crea un árbol de un nodo para cada uno y se inserta un puntero al árbol correspondiente en la pila.
Continuando, se lee un '+' y fusiona los dos últimos árboles.
Ahora, se lee un '*'. Se abren los dos últimos punteros de á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 un puntero al árbol final permanece en la pila. [5]
Expresiones algebraicas
Los árboles de expresión algebraica 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 variables en los nodos hoja . [1] Los nodos de los operadores binarios tienen dos nodos secundarios y los operadores unarios tienen un nodo secundario.
Expresiones booleanas
Las expresiones booleanas se representan de manera muy similar a las expresiones algebraicas, siendo la única diferencia los valores y operadores específicos utilizados. Las expresiones booleanas usan verdadero y falso como valores constantes, y los operadores incluyen( Y ),( O ),( NO ).
Ver también
Referencias
- ↑ a b c Bruno R. Preiss (1998). "Árboles de expresión" . Archivado desde el original el 19 de enero de 2017 . Consultado el 20 de diciembre de 2010 .
- ^ a b Gopal, Arpita. Ampliación de estructuras de datos . PHI Learning, 2010, pág. 352.
- ^ Richard F. Gilberg y Behrouz A. Forouzan. Estructuras de datos: Un Enfoque Pseudocódigo con C . Thomson Course Technology, 2005, pág. 280.
- ^ Mark Allen Weiss, Estructuras de datos y análisis de algoritmos en C, segunda edición , publicaciones de Addison Wesley
- ^ Gopal, Arpita. Ampliación de estructuras de datos . PHI Learning, 2010, pág. 353.