arboles

Árboles de Expresion

Los árboles de expresiones representan el código de nivel del lenguaje en forma de datos. Los datos se almacenan en una estructura con forma de árbol. Cada nodo del árbol de expresión representa una expresión, por ejemplo, una llamada al método o una operación binaria, como x < y.
En la ilustración siguiente se muestra un ejemplo de una expresión y su representación enforma de un árbol de expresión. Las diferentes partes de la expresión tienen un color distinto para hacerlas coincidir con el nodo correspondiente del árbol de expresión. También se muestran los diferentes tipos de los nodos del árbol de expresión.
REGLAS PARA LA CONSTRUCCION DE ARBOLES DE EXPRESION
Para contruir el árbol de expresiones que represente nuestra expresión matemática es necesarioconstruir primero la misma expresión pero en la notación polaca correspondiente y a partir de esta es que se construye el árbol. El algoritmo usado para transformar una expresión infija a prefija es explicado a continuación.
Sea A una expresión infija cualquiera, formada por operadores, paréntesis (izquierdos y derechos) y operandos, también se usará una pila para los operadores. El procedimientoseguido es el siguiente:
Se lee un elemento de A, si este es un operador o un paréntesis izquierdo, entonces se actúa según la regla I y si es un operando entonces se envía directamente a la expresión de notación polaca. Si el elemento leído de A es un paréntesis derecho, entonces se desapilarán elementos de la pila de operadores hasta encontrar el correspodiente paréntesis izquierdo. Cadaelemento desapilado pasa a formar parte de la notación polaca, excepto los paréntesis. Cuando no queden elementos en A, entonces se desapilan operadores de la pila, hasta que esta quede vacía.
Regla I:
Existe un orden de prioridad para los operadores, que de menor a mayor es el siguiente: suma (+) y resta (-), multiplicación (*) y división (/), exponenciación (^), operadores unarios. El paréntesisizquierdo lo trataremos como un operador (aunque no lo es) cuyo orden de prioridad es el mayor de todos cuando se quiera apilar y el menor de todos cuando esté en la cima de la pila.
Cuando se intente apilar algún operador se hará lo siguiente: si es un operador unario entonces se apila, si es un operador binario, se comparará su prioridad con el último insertado en la pila (el de la cima), sisu prioridad es mayor, entonces se apilará. Si ocurre lo contrario (su prioridad es menor o igual) entonces el operador de la cima de la pila se desapilará y pasará a formar parte de la notación polaca. Se volverá a intentar apilar el operador siguiendo la misma regla, hasta que se pueda apilar, si la pila queda vacía también se apila. El paréntesis izquierdo siempre se apilará y no podrá serdesapilado por ningún operador y por tanto no formará parte de la notación polaca inversa.
El siguiente ejemplo, ayudará a entender mejor lo dicho anteriomente. Sea la siguiente expresión infija: 2^sin(y+x)–ln(x).
En la siguiente tabla se muestra paso a paso la conversión a notación postfija. Se usa el color rojo para señalar los casos en que es necesario desapilar operadores de la pila.Construccion del árbol binario de expresiones
 
Una vez obtenida la expresión en notación postfija, se puede evaluar mediante el uso nuevamente de una pila. Sin embargo, en nuestro caso se trabaja con una árbol binario de expresiones, así que lo que se hace es construir el árbol. El algoritmo usado para construir el árbol no usa como tal la expresión postfija ya conformada, sino que el árbol se vaconstruyendo usando las mismas reglas con las que se construye la notación postfija, una pila para los operadores y otra para los nodos del árbol, ambas no son necesitadas al terminar el árbol. El algoritmo es el siguiente:
 
Se siguen las mismas reglas expuestas anteriormente usando la pila de operadores, pero cuando se encuentra un operando o un operador es desapilado, entonces se crea el nodo...