1. Un árbol binario de búsqueda (o un árbol binario ordenado) es aquel en que, dado un nodo, todos los datos del subárbol izquierdo son menores que los datos de ese nodo, mientras que todos los datos del subárbol derecho son mayores que ese nodo. Se denomina árbol binario de búsqueda porque se puede buscar en ellos un término utilizando un algoritmo de búsqueda binaria. Dado el siguiente árbol binario de búsqueda realizar los recorridos enorden, preorden y postorden del árbol:
2. 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 las secuencias de las letras que resultan en cada caso.
M, Y, T, E, R
T, Y, M, E, R
R,E,M, Y, T
C, Q, R, N F, L, A, K, E S
3. Dibuja 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))
4. El recorrido preorden de un cierto árbol binario produce: ADFGHKLPQRWZ. Y el recorrido enorden produce: GFHKDLAWRQPZ. Dibujar el árbol binario.
5. Escribir un método recursivo que cuente las hojas de un árbol binario.
6. Escribir un método que determine el número de nodos que se encuentran en el nivel n de un árbol binario.
7. Escribir un método que tome un árbol como entrada y devuelva el número de descendientes del árbol.
8. 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.
9. Se dispone de un árbol binario de elementos 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
10. Diseñar un método iterativo que encuentre el número de nodos hoja en un árbol binario.
11. Escribir un método booleano identicos() que permita decir si dos árboles binarios son iguales.
12. Construir un método que encuentre el nodo máximo de un árbol binario.
13. Construir un método recursivo para escribir todos los nodos de un árbol binario de búsqueda cuyo campo clave sea mayor que un valor dado (el campo clave es de tipo entero).
14. Escribir un método que determine la altura de un nodo. Escribir un programa que cree un árbol binario con números generados aleatoriamente y muestre por pantalla:
a) La altura de cada nodo del árbol
b) La diferencia de alturas entre la ramas y derecha de cada nodo.
15. Diseñar métodos no recursivos que listen los nodos de un árbol inorden, preorden y postorden.
16. Diseñar un método que muestre los nodos de un árbol por niveles.
17. Un árbol binario de búsqueda puede implementarse con un array. La representación no enlazada correspondiente consiste en que para cualquier nodo del árbol almacenado en la posición i del array, si hijo izquierdo se encuentra en la posición 2*i y su hijo derecho en la posición 2*i+1. A partir de esta representación, diseñar los métodos con las operaciones correspondientes para gestionar interactivamente un árbol de números enteros.
18. Dado un árbol binario de búsqueda diseñar un método que liste los nodos del árbol ordenados descendentemente.
19. Escriba un programa que muestre o visualice por consola todos los nodos del árbol binario.
20. Escriba un applet que visualice gráficamente el árbol binario.
21. Dibujar el árbol de búsqueda equilibrado que se produce con las claves: 14, 6, 24, 35, 59, 17, 21, 32, 4, 7, 15 y 22.
22. Dada la secuencia de claves enteras: 100, 29, 71, 82, 48, 39, 101, 22, 46, 17, 3, 20, 25 y10, 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.
23. Encontrar una secuencia de n claves que al ser insertadas en un árbol binario de búsqueda vacío permiten aplicar los cuatro casos de rotaciones: II, ID, DD, DI.
24. Dado un archivo de texto, construya el árbol AVL con todas sus palabras y frecuencias. El archivo se debe llamar carta.txt. El programa debe tener un método que, dada una palabra, devuelva el número de veces que aparece en el texto. Proponer el diagrama de clases que solucione este problema.