arboles 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 operandoy 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 noson 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 n2y 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 laversió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...