Servelets En Java

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 árbolbinario 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 bool completo (const Arbin& a) inicio si (a.esVacio( )) entonces devuelveverdad 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 eseficiente 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 bool completo (const Arbin& a) var int altura fvar inicio altura = a.altura( ) completo (a, altura) fin;template bool completo (const Arbin& 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

qd

s

t

k

Universidad de Huelva

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& a, const Arbin& 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,...