Download Estructuras de Datos II Boletín nº 3 Árboles

Estructuras de Datos II
(I.T. Informática de Gestión y Sistemas)
Boletín nº 3
Árboles
I. Árboles Binarios y Árboles Binarios de Búsqueda
1. Diseñar una función que, dados dos árboles binarios A y B, determine si son idénticos
o no.
2. Suponiendo que los nodos del árbol almacenan enteros, construir una función que
calcule la suma de sus elementos.
3. Diseñar una función que, dado un árbol binario A, realice una copia simétrica B del
mismo.
4. Diseñar una función que visualice los nodos que están en el nivel n de un árbol
binario.
5. Diseñar una función que, dado un árbol binario, devuelva verdadero si el árbol es
completo y falso en otro caso. Suponemos que el árbol vacío es completo.
SOLUCIÓN 1
template <typename T>
bool completo (const Arbin<T>& a)
inicio
si (a.esVacio( )) entonces devuelve verdad
sino
si ( a.subIzq( ).esVacio( ) Ù a.subDer( ).esVacio( )) entonces devuelve verdad
// es hoja
sino
si (a.subIzq( ).esVacio( ) Ú a.subDer( ).esVacio( )) entonces devuelve falso
// tiene un solo hijo
sino
// tiene 2 hijos no vacíos
devuelve a.subIzq( ).altura( ) == a.subDer( ).altura( ) Ù
completo(a.subIzq( )) Ù completo(a.subDer( ))
fsi
fin;
Esta solución, aunque funciona correctamente, no es eficiente puesto que hay que
calcular la altura del árbol en cada llamada recursiva, haciendo que el algoritmo sea
de orden cuadrático (O(n)). La siguiente solución también resuelve el problema y es
de orden lineal.
Estructuras de Datos II
Curso 2005/06
SOLUCIÓN 2
template <typename T>
bool completo (const Arbin<T>& a)
var
int altura
fvar
inicio
altura = a.altura( )
completo (a, altura)
fin;
template <typename T>
bool completo (const Arbin<T>& a, int altura)
inicio
si (a.esVacio( )) entonces devuelve verdad
sino
// es hoja y está en el nivel más bajo
si ( a.subIzq( ).esVacio( ) Ù a.subDer( ).esVacio( ) Ù altura == 0) entonces devuelve verdad
sino
si (a.subIzq( ).esVacio( ) Ú a.subDer( ).esVacio( )) entonces devuelve falso
// tiene un solo hijo
sino
// tiene 2 hijos no vacíos
devuelve completo(a.subIzq( ), altura - 1) Ù completo(a.subDer( ) altura -1)
fsi
fin;
6. Diseñar una función que indique si un árbol binario es un árbol de búsqueda (ABB).
7. Se define por frontera de un árbol binario la secuencia formada por los elementos
almacenados en las hojas de un árbol binario, tomados de izquierda a derecha.
Diseñar una función que, dado un árbol binario y una lista vacía pasados como
parámetros, devuelva en dicha lista la frontera del árbol.
8. Diseñar una función booleana que, dados un árbol binario y un camino expresado en
forma de lista, determine si existe dicho camino en el árbol, teniendo en cuenta que el
camino debe comenzar necesariamente en la raíz. Por ejemplo, para el árbol de la
figura existen los caminos "m-q-t" y "m-d", pero no existen los caminos "r-q-t" ni "d-k".
m
q
s
Universidad de Huelva
d
t
k
Página 2
Estructuras de Datos II
Curso 2005/06
9. Diseñar una función que indique si un árbol binario está equilibrado.
10. Diseñar una función booleana que indique si dos árboles binarios A y B tienen la
misma forma en cuanto a la distribución de sus nodos.
11. Diseñar una función que visualice el contenido de un árbol binario por niveles.
Primero el nivel 0, después los nodos del nivel 1, los del nivel 2 y así hasta el último
nivel.
12. Diseñar una función que visualice los nodos de un árbol binario de búsqueda
ordenados descendentemente.
13. Diseñar una función booleana que devuelva verdad si los árboles a y b tienen al
menos 2 nodos con la misma información y falso en caso contrario.
La sintaxis de la función es:
dosComunes (const Arbin<T>& a, const Arbin<T>& b, int cont)
El parámetro cont sirve para llevar el control del número de nodos comunes
II. Árboles Binarios de Búsqueda Equilibrados (AVL)
14. Mostrar el resultado de insertar 20, 16, 44, 57, 93, 32, 65, 19, 8 y 17 en un árbol
AVL inicialmente vacío.
15. Dibujar el árbol AVL que resulta a partir de la siguiente entrada de datos: 35, 18, 9,
58, 14, 49, 51, 67, 60.
16. Dibujar el árbol AVL que resulta a partir de la siguiente entrada de datos: 24, 14, 6,
35, 59, 17, 21, 32, 4, 7, 15, 22.
17. Dibujar el árbol AVL que resulta de realizar las siguientes inserciones: 13, 7, 21,
15, 27, 18, 4, 11, 30. A continuación eliminar los elementos: 13, 4, 15.
III. Montículos
18. Mostrar el resultado de insertar los elementos 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4,
11, 13 y 2, uno a uno, en un montículo de mínimos inicialmente vacío. Una vez
construido el montículo, dibuja los montículos resultantes de eliminar, uno a uno,
cuatro elementos del mismo.
Universidad de Huelva
Página 3
Estructuras de Datos II
Curso 2005/06
IV. Árboles Generales
19. Diseñar una función para la clase árbol general que devuelva el número de nodos
que forman el árbol.
20. Diseñar una función para la clase árbol general que calcule el grado del árbol. El
grado de un árbol es el máximo de los grados de sus nodos.
21. Diseñar una función para la clase árbol general que devuelva en una lista el
resultado del recorrido en anchura del árbol.
22. Diseñar una función que, dado un árbol general, devuelva el número de hojas de
dicho árbol.
23. Diseñar una función booleana que, dados dos árboles generales, determine si
tienen la misma estructura. Por ejemplo, los árboles generales que siguen tienen la
misma estructura, aunque, como puede observarse, no coincidan los valores que
se almacenan en los nodos.
t
q
b
w
k
s
f
f
g
v
g
k
q
ñ
V. Árboles B
24. Dibujar el árbol B de orden 5 que resulta después de insertar al árbol B de la figura
los datos siguientes: 60, 3, 12, 23, 51, 80, 14, 59, 15, 9, 13, 1.
25
7
2
5
6
19
10 12 16
Universidad de Huelva
47 76
20 21 22 24
31 43 44
50 52 60 69
84
Página 4
98
Estructuras de Datos II
Curso 2005/06
25. Dibujar el árbol B de orden 5 que resulta a partir de la siguiente entrada de datos:
C, S, D, T, A, M, P, I, B, W, N, G, U, R, K, E, H, O, L, J.
26. Dibujar el árbol B de orden 5 que resulta de realizar las siguientes inserciones: 1,
7, 6, 2, 11, 4, 8, 13, 10, 5, 19, 9, 18, 24, 3, 12, 14, 20 y 21. A continuación eliminar
los elementos: 8, 10 y 6.
27. En un árbol B de orden 3 inicialmente vacío, insertar la siguiente secuencia de
claves: 40, 80, 75, 60, 21, 65, 15, 8, 6, 90, 100 y 62. Del árbol resultante, eliminar
la siguiente secuencia de claves: 60, 6 y 80
Universidad de Huelva
Página 5