Arboles de expresiones
Á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.
REGLAS PARA LA CONSTRUCCION DE ARBOLES DE EXPRESION
Para contruir el árbol de expresiones que represente
nuestra expresión matemática es necesario construir 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 procedimiento seguido 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. Cada elemento 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éntesis izquierdo
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), si su 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á ser desapilado por ningún operador y
por tanto no formará parte de la notación polaca inversa.
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 va construyendo
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 correspondiente y se actúa según la
regla II. Al finalizar el algoritmo solo debe quedar un nodo apilado en la
pila de nodos, el que constituye el nodo raíz de nuestro árbol de
expresiones.
Regla II.
Si el nodo corresponde a un operando, entonces se apila.
Si el nodo corresponde a una operador unario entonces se desapila un nodo de
la pila de nodos y es enlazado a la rama izquierda del nodo correspondiente
al operador unario y este último es apilado. Si el nodo corresponde a un
operador binario entonces dos nodos son desapilados de la pila de nodos, el
primero es enlazado a la rama derecha del nodo binario y el segundo a la rama
izquierda, nuevamente este nodo es apilado.
En el siguiente ejemplo se usa la misma expresión infija
anterior (2^sin(y+x) – ln (x)) para ilustrar el procedimiento para construir
el árbol:
Recorrido en preorden
En este tipo de recorrido se realiza cierta acción (quizás
simplemente imprimir por pantalla el valor de la clave de ese nodo) sobre el
nodo actual y posteriormente se trata el subárbol izquierdo y cuando se haya
concluido, el subárbol derecho. Otra forma para entender el recorrido con
este metodo seria seguir el orden: nodo raiz, nodo izquierda, nodo derecha.
En el árbol de la figura el recorrido en preorden sería:
2, 7, 2, 6, 5, 11, 5, 9 y 4.
void preorden(tArbol *a)
{
if (a != NULL) {
tratar(a); //Realiza
una operación en nodo
preorden(a->hIzquierdo);
preorden(a->hDerecho);
}
}
Implementación en pseudocódigo de forma iterativa:
push(s,NULL); //insertamos
en una pila (stack) el valor NULL, para asegurarnos de que esté vacía
push(s,raíz); //insertamos
el nodo raíz
MIENTRAS (s <> NULL) HACER
p =
pop(s); //sacamos
un elemento de la pila
tratar(p); //realizamos
operaciones sobre el nodo p
SI (D(p) <>
NULL) //preguntamos
si p tiene árbol derecho
ENTONCES
push(s,D(p));
FIN-SI
SI (I(p) <>
NULL) //preguntamos
si p tiene árbol izquierdo
ENTONCES
push(s,I(p));
FIN-SI
|
