Download árboles con expresiones

Expresiones con árboles
*
n1
n2
árboles con expresiones
Estructura de Datos
+
n3
+
n4
n5
n6
n7
a
b
a
c
Árbol de expresiones
con etiquetas
Expresiones con árboles
Expresiones con árboles
En la lámina anterior n1,n2, n3, …,n7 son los nombres de
los nodos
Las reglas para representar una expresión mediante un
árbol etiquetado son estas:
! 1. Cada hoja está etiquetada con un operando y sólo
consta de ese operando. Por ejemplo el nodo n4
representa la expresión a.
! 2. Cada nodo interior n está etiquetado con un operador.
Supóngase que n está etiquetado con el operador binario
x, como + o *, y que el hijo izquierdo de n representa la
expresión E1, y el hijo derecho la expresión E2. Entonces n
representa la expresión (E1)x(E2
). Los paréntesis se
(E1)x(E2).
pueden quitar si no son necesarios.
Expresiones con árboles
! Por ejemplo, el nodo n2 tiene el operador + como etiqueta,
y sus hijos izquierdo y derecho representan las
expresiones a y b, respectivamente. Por tanto, n2
representa (a)+(b), o más simple, a+b.
a+b. El nodo n1
representa (a+b
)*(a+c
a+c),
), puesto que * es la etiqueta de n1, y
(a+b)*(
a+b y a+c son las correspondientes expresiones
representadas por n2 y n3.
Expresiones con árboles
OTRO EJEMPLO:
q
! En la anterior figura se mostró una expresión y su
representación de árbol.
+
X
A
B
produce la cadena q+ABsenC*X+YZ.
q+ABsenC*X+YZ. Ésta es la versión
prefija de la expresión.
! El recorrido general de orden produce la cadena
AB+CsenXYZ+*q,
AB+CsenXYZ+*q, la cual es la versión posfija de la
expresión.
+
C
q(A + B), sen ( C ), X * ( Y + Z )
! Un recorrido general del árbol en orden previo (preorden
(preorden))
*
sen
Y
Z
1
Expresiones con árboles
Expresiones con árboles
+
+
*
+
Orden Previo:
+*AB+*CDE
En orden:
AB*CD*E++
*
*
A
+
A
Orden Previo:
+*AB+*CDE
En Orden:
A*B+C*D+E
*
E
B
B
Orden Posterior: B A D C E * + * +
C
D
C
Orden Posterior: A B * C D * E + +
Expresiones con árboles
! En este ejemplo se pretende evaluar una expresión cuyos
operandos son todos constantes. Primero declararemos al nodo
árbol.
#define OPERADOR 0
#define OPERANDO 1
struct nodoarbol{
nodoarbol{
short int utype;
utype; /*operador u operando*/
union{
union{
char opera[10];
float val;
val;
} info;
info;
struct nodoarbol *hijo;
struct nodoarbol *sig;
sig;
};
typedef nodoarbol *NODOPTR;
E
D
Expresiones con árboles
! Suponiendo que contamos con una función llamada apply(p),
apply(p), la
cual acepta un apuntador a un árbol de expresiones que contiene
un operador único y sus operandos numéricos, y retorna el
resultado de aplicar el operador a sus operandos.
! Ahora bien, se presenta un procedimiento recursivo reemplaza que
acepta un apuntador a un árbol de expresión y sustituye el árbol
con un nodo de árbol que contiene el resultado numérico de la
evaluación de la expresión
void reemplaza(NODOPTR p)
{
float valor;
NODEPTR q, r;
Expresiones con árboles
if(pif(p->utype==OPERADOR){
utype==OPERADOR){ //el árbol tiene un operador
q = p//como su raiz
p->hijo;
while(q!
while(q!=NULL)
=NULL)
reemplaza(q);
reemplaza(q); //reemplaza
q = qq->sig;
sig;
} //fin de while
//aplicar el operador en la raíz a los
//operandos en los subárboles
valor=apply(p);
valor=apply(p);
//sustituir el operador por resultado
p->utype=OPERANDO;
utype=OPERANDO;
p->val=valor;
val=valor;
//liberar todos los subárboles
q = pp->hijo;
p->hijo = NULL;
while(q!
while(q!=NULL){
=NULL){
r = q;
q = qq->sig;
sig;
free(r);
free(r);
} //fin de while
} //fin de if
} //fin de reemplaza
! La función evalua_arbol se escribe de modo siguiente:
float evalua_arbol(NODOPTR p)
{
NODOPTR q;
reemplaza(p);
reemplaza(p);
return(preturn(p->val)
val)
free(p);
free(p);
}
2
bibliografia
! Estructura de Datos y Algoritmos
Alfred V. Aho,
Aho, Jhon E. Hopcroft,
Hopcroft, Jeffrey D.Ullman
! Estructura de Datos en C y C++
Tenenbaum,
Tenenbaum, Langsam,
Langsam, Augenstein
3