sistemas operativos

Guía resuelta de Ejercicios: Árboles.
1. El recorrido en postorden de un ABB que contiene caracteres es:
DMLCTAISRUNOKB
Y en inorden es:
DMATLCBIKUSRON
A) Dibujar el arbol binario.
B) Dar elrecorrido en preorden.
C) Diseñar una funcion
void postorden(string preorden, string inorden)
Que dada la secuencia en preorden y en inorden de un árbol binario, imprima la secuencia en
postorden.2. Se tiene un arbol AVL vacío que se le insertan, en orden, los siguientes elementos:
3, 2, 18, 5, 20, 90, 77, 40, 34, 12
A) Dibuje la disposición final del arbol AVL e indique el número derotaciones que fueron
realizadas.
B) Dibuje la disposición final de un ABB, al que se le inserta esta misma secuencia de números.
C) Justifique la eficiencia en este tipo de casos, de un AVL sobre un ABB.Use de referencia las
disposiciones de las preguntas A y B.

Desarrollo:
1.A) Para poder deducir el arbol binario que tiene esos recorridos, se debe recordar que dado un
inorden y un pre opostorden, existe un único arbol binario que cumple ambos recorridos.
Por lo tanto dibujaremos una tabla donde en la vertical tendremos el postorden, de abajo hacia
arriba, y en la horizontal tendremosel inorden:

Secuencia en
Postorden

B
X
K
X
O
X
N
X
U
X
R
X
S
X
I
X
A
X
T
X
C
X
L
X
M
X
D X
D M A T L C B I K U S R O N

Secuencia en Inorden
Nos damos cuenta deque existe solo una casilla por cada letra donde fila y columna coinciden.
Pero qué hacemos con esto? Construimos el árbol. La marca de más arriba será la raíz del árbol y
con eso tenemos el primernodo. Los hijos de ese nodo serán, para las sub-tablas izquierda y
derecha, el nodo que esté más alto, y los hijos de esos nodos serán a su vez los nodos más altos de
las sub-tablas acotadas por lasraíces ya obtenidas. En el diagrama pintamos de un color los nodos
de un mismo nivel. El orden de los colores es: amarillo, azul, rojo, verde, plomo, blanco.
Dibujando el árbol binario construido:...