ESTRUCTURA DE DATOS
UNIDAD 4
CASOS PRÁCTICOS
13.1. Explicar por qué cada una de las siguientes estructuras no es un árbol binario:
13.2. Considérese el árbol siguiente,
a) ¿Cuál es su altura?
b) ¿Está el árbol equilibrado? ¿Por qué?
c) Listar todos los nodos hoja.
d) ¿Cuál es el predecesor inmediato (padre) del nodo U?
e) Listar los hijos del nodo R.
f) Listar los sucesores del nodo R.
13.3. Para cada una de las siguientes listas de letras,
a) dibujar el árbol binario de búsqueda que se construye cuando las letras se insertan
en el orden dado,
b) realizar recorridos enorden, preorden y postorden del árbol y mostrar la secuencia
de letras que resultan en cada caso.
(i) M, Y, T, E, R (iii) R, E, M, Y, T
(ii) T, Y, M, E, R (iv) C, O, R, N, F, L, A, K, E, S
13.4. En el árbol del Ejercicio 13.2, recorrer cada árbol utilizando los órdenes
siguientes: NDI, DNI, DIN.
13.5. Dibujar los árboles binarios que representan las siguientes expresiones:
a) (A+B)/(C-D)
b) A+B+C/D
c) A-(B-(C-D)/(E+F))
d) (A+B)*((C+D)/(E+F))
e) (A-B)/((C*D)-(E/F))
13.6. El recorrido preorden de un cierto árbol binario produce ADFGHKLPQRWZ
y el recorrido enorden produce GFHKDLAWRQPZ. Dibujar el árbol binario.
13.7. Escribir un método recursivo que cuente las hojas de un árbol binario.
13.8. Escribir un método que determine el número de nodos que se encuentran en el
nivel n de un árbol binario.
13.9. Escribir un método que tome un árbol como entrada y devuelva el número de
hijos del árbol.
13.10. Escribir un método booleano al que se le pase una referencia a un árbol binario
y devuelva verdadero (true) si el árbol es completo y falso (false) en caso contrario.
13.11. Se dispone de un árbol binario de elementos de tipo entero. Escribir métodos
que calculen:
a) La suma de sus elementos.
b) La suma de sus elementos que son múltiplos de 3.
13.12. Diseñar un método iterativo que encuentre el número de nodos hoja en un árbol
binario.
13.13. En un árbol de búsqueda cuyo campo clave es de tipo entero, escribir un
método que devuelva el número de nodos cuya clave se encuentra en el rango [x1,
x2].
13.14. Diseñar un método que visite los nodos del árbol por niveles; primero el nivel 0,
después los nodos del nivel 1, y del nivel 2 y así hasta el último nivel.
14.1. Dibujar el árbol binario de búsqueda equilibrado que se produce con las claves:
14, 6, 24, 35, 59, 17, 21, 32, 4, 7, 15 y 22.
14.2. Dada la secuencia de claves enteras: 100, 29, 71, 82, 48, 39, 101, 22, 46, 17, 3,
20, 25, 10, dibujar el árbol AVL correspondiente. Eliminar claves consecutivamente
hasta encontrar un nodo que viole la condición de equilibrio y cuya restauración sea
con una rotación doble.
14.3. En el árbol construido en el Ejercicio 14.1 eliminar el nodo raíz. Hacerlo tantas
veces como sea necesario hasta que se desequilibre un nodo y haya que aplicar una
rotación simple.
14.4. Encontrar una secuencia de n claves que al ser insertadas en un árbol binario de
búsqueda vacío permiten aplicar las cuatro rutinas de rotación: II, ID, DD, DI.
14.5. Dibujar el árbol equilibrado después de insertar en orden creciente 31 (25 – 1)
elementos del 11 al 46.
14.6. ¿Cuál es el número mínimo de nodos de un árbol binario de búsqueda
equilibrado de altura 10?
14.7. Escribir el método recursivo buscarMin() de forma que devuelva el nodo de clave
mínima de un árbol de búsqueda equilibrado.
14.8. Dibujar un árbol AVL de altura 6 con el criterio del peor de los casos; es decir,
aquel en el que cada nodo tenga como factor de equilibrio ± 1.
14.9. En el árbol equilibrado formado en el Ejercicio 14.8, eliminar una de las hojas
menos profundas. Representar las operaciones necesarias para restablecer el
equilibrio.
14.10. Escribir el método recursivo buscarMax() que devuelva el nodo de clave
máxima de un árbol de búsqueda equilibrado.
14.11. Escribir los métodos buscarMin() y buscarMax() en un árbol de búsqueda
equilibrado de manera iterativa.
