Home UC3M Universidad Carlos III de Madrid - Departamento de Ingeniería Telemática Home IT
Localización | Personal | Docencia | Investigación | Novedades | Intranet  

Práctica 6.- Árboles (I)

Datos de la práctica

Fecha 29 de abril de 2008
Conceptos Árboles

Contenidos

Ejercicio 1.- Árbol binario de búsqueda

Un árbol binario de búsqueda es un árbol binario ordenado de modo que para cada nodo n, todas las claves de los nodos del subárbol izquierdo son menores que la clave de n y todas las del subárbol derecho son mayores (supondremos que no existen repeticiones).

En esta práctica implementaremos un árbol binario de búsqueda mediante las clases ArbolBB (que representa el árbol) y la clase auxiliar NodoBB, de modo que:

tal como se representa en la figura siguiente.

Observa que con esta estructura, un árbol vacío es aquél que tiene su nodo raíz a null, pero el objeto árbol en sí no es null

Apartado 1: estructura

Define los atributos de las clases ArbolBB y NodoBB, de acuerdo a la estructura representada en la figura anterior.

Apartado 2: constructores y accesores

Proporciona un constructor, sin parámetros, para la clase ArbolBB que inicialice un árbol vacío (es decir, con la raíz igual a null).

Proporciona un constructor para la clase auxiliar NodoBB. Este constructor debe recibir como parámetros la clave de búsqueda asociada ese nodo y la información a almacenar. Los subárboles hijos, izquierdo y derecho, del nodo se inicializarán como árboles vacíos. Es decir, con sus respectivos nodos raíz a null.

Para cada clase, proporciona los métodos get y set necesarios para acceder a sus atributos.

Apartado 3: árbol vacío

Programa el método boolean isVacio() que comprueba si el árbol está vacío.

Apartado 4: búsqueda

Programa el método public Object buscar(Comparable clave) que devuelve el objeto almacenado en el nodo cuya clave asociada coincide con la que se pasa como parámetro.

Apartado 5: inserción

Programa el método public void insertar(Comparable clave, Object info) que introduce un nuevo dato en el árbol. Para ello, debe crear un nuevo nodo en el lugar apropiado, que contenga la clave y el objeto que se pasan como parámetros. Si el árbol ya contiene un nodo con la clave indicada, se sobreescribe la información almacenada en el objeto.

Ejercicio 2.- Recorrido pre-orden

Programa el método void mostrarPreOrden() que presenta por salida estándar todas las entradas del árbol, siguiendo el recorrido pre-orden.

Ejercicio 3.- Ejemplo de aplicación: agenda

En este ejercicio vamos a implementar una agenda de direcciones utilizando un árbol binario de búsqueda para facilitar las búsquedas.

Apartado 1

Programa la clase EntradaAgenda que almacena los datos asociados a cada entrada de la agenda:

Apartado 2

Programa la clase Agenda, que utiliza un árbol binario de búsqueda para almacenar los datos de una agenda electrónica. La clave de búsqueda por la que se ordenan los datos de la agenda es el nombre completo, según el formato: Apellidos, Nombre

Apartado 3

Agrega a la clase Agenda el método void insertar(EntradaAgenda datos) que introduce los datos que se pasan como parámetros en la agenda. Recuerda que debes concatenar los apellidos y el nombre para generar la clave de búsqueda asociada.

Agrega a la clase Agenda el método void insertar() que introduce una nueva entrada en la agenda con los datos que se introduzcan por teclado.

Apartado 4

Agrega a la clase Agenda el método EntradaAgenda buscar(String nombreCompleto) que permite recuperar los datos de una determinada entrada a partir del nombre completo (apellidos y nombre).

Apartado 5

Programa el método void mostrarOrdenado() que presenta el contenido de la agenda por salida estándar, en orden alfabético (recorrido in-orden).

Soluciones