Universidad Carlos III de Madrid

Un árbol BSTree contiene la referencia a su nodo raíz.

Un nodo BSNode contiene la clave de comparación, la información a almacenar y las referencias a los nodos que forman los subárboles izquierdo y derecho.

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

Proporciona un constructor, sin parámetros, para la clase BSTree que inicialice un árbol vacío (es decir, con la raíz igual a null).Proporciona un constructor para la clase auxiliar BSNode. 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 a null. Para cada clase, proporciona los métodos get y set necesarios para acceder a sus atributos.

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

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

Programa el método public void insert(Comparable key, 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.

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

Programa la clase DirectoryEntry que almacena los datos asociados a cada entrada de la agenda: Nombre, Apellidos, Dirección, Teléfono, Móvil and Correo electrónico.

Programa la clase Directory, 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

Agrega a la clase Directory el método void insert(DirectoryEntry data) 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 Directory el método void insert() que introduce una nueva entrada en la agenda con los datos que se introduzcan por teclado.

Agrega a la clase Directory el método DirectoryEntry search(String fullName) que permite recuperar los datos de una determinada entrada a partir del nombre completo (apellidos y nombre).

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

Programa la clase MonticuloBinario que representa un montículo binario, tal como se ha definido previamente, utilizando internamente un Vector para almacenar los datos. Define los atributos de la clase y proporciona un constructor que inicializa un montículo vacío (no recibe parámetros). Observa que cada elemento del montículo almacena dos datos: la prioridad del elemento y el objeto almacenado. Programa la clase auxiliar ElementoColaPrioridad que encapsula esta información

Agrega a la clase MonticuloBinario los siguientes métodos: int tamaño(); , que devuelve el número de elementos y boolean isVacio(); , que indica si está vacío el árbol

Agrega a la clase MonticuloBinario el método void insertar(int prioridad, Object info); que almacena un nuevo el elemento manteniendo las propiedades de estructura y orden del montículo.

Para insertar un elemento X en el montículo, primero debemos añadir un nuevo nodo al árbol. Este nodo debe agregarse al final de la estructura para garantizar que continúa siendo completo. Una vez agregado el nuevo elemento en la última posición, hay que comprobar que se mantiene la propiedad de ordenación del montículo. Para ello, hay que comprobar si el nuevo hijo es mayor que su padre. En ese caso, el montículo está ordenado y termina el proceso. Si el nuevo dato es menor que el almacenado en el nodo padre, hay que intercambiarlos y repetir el proceso de comprobación hasta que el dato llegue a un nodo en que se cumpla la propiedad del montículo (padre menor o igual que hijo) o bien a la raíz.

Agrega a la clase MonticuloBinario el método Object extraer(); que devuelve el objeto almacenado en la raíz, es decir, con mayor prioridad, y reorganiza el montículo de modo que se mantengan sus propiedades de estructura y orden. Recuerda que las prioridades más altas se corresponden con los valores más pequeños, siendo 1 la prioridad máxima.

Devolver el objeto buscado es trivial, puesto que las propiedades del montículo garantizan que se encuentra en la raíz.

La dificultad de este método consiste en reorganizar posteriormente la estructura, puesto que el nodo raíz puede tener dos hijos. Para ello hay que realizar el proceso inverso al "reflotamiento" realizado al insertar, "hundiendo" el "hueco" generado hasta la posición adecuada.

Para ocupar el lugar que ha quedado vacío, hay que seleccionar el menor de los dos hijos del nodo (si existen). El elemento hijo pasa a ocupar la posición del padre, de modo que el hueco baja un nivel. El proceso se repite sucesivamente hasta llegar a una hoja (un nodo que no tenga hijos).

El árbol debe seguir siendo completo, de modo que el último elemento pasa a la posición en que ha quedado el hueco.

Agrega a la clase MonticuloBinario el método print() , que imprime por pantalla los elementos almacenados junto con su prioridad. Los elementos deben presentarse en orden según su posición en el montículo.

Un nodo NodoBB contiene la clave de comparación, la información a almacenar y las referencias a los subárboles izquierdo y derecho.

Modifica la definición de la clase MonticuloBinario de modo que implemente el interfaz ColaConPrioridad .

					interface ColaConPrioridad {

    static int PRIORIDAD_MAXIMA = 1;

    /**
     * Insertar el objeto indicado en la posición adecuada de la cola 
     * según su prioridad.
     * La prioridad se indica mediante un número natural (> 0).
     * Cuanto mayor es dicho número, menor es la prioridad del elemento 
     * asociado. El valor 1 corresponde a los elementos con prioridad máxima.
     */
    void insertar(int prioridad, Object info);

    /**
     * Extrae el objeto con mayor prioridad de la cola 
     * (es decir, aquél cuya prioridad tenga valor mínimo)
     * En el caso de que varios elementos tengan la misma prioridad, 
     * se devuelve el primero que se introdujo (FIFO).
     * Si la cola está vacía, devuelve null.
     */
    Object extraer();

    /**
     * Devuelve el número de elementos de la cola
     */
    int tamaño();

    /**
     * Indica si la cola está vacía.
     */
    boolean isVacio();

}

				

Utilizando la clase MonticuloBinario desarrollada en los apartados anteriores, completa la clase GestorColaImpresion que gestiona los trabajos a imprimir mediante una cola con prioridad:

					public class  GestorColaImpresion {

    ColaConPrioridad cola;

    /**
     * Inicializa el gestor, vacío.
     */
    public GestorColaImpresion() {
        // completar
    }

    /**
     * Agrega un nuevo trabajo de impresión, con la prioridad indicada.
     */
    public void imprimir(int prioridad, String fichero) {
        // completar
    }

    /**
     * Procesa (saca por impresora) el primer trabajo de la cola, con prioridad máxima, 
     * reorganizando adecuadamente la estructura de datos. 
     */
    public void procesar() {
        // completar
    }

    // NOTA: en versiones previas de este enunciado se incluía un
    // método llamado eliminarTrabajo(). Se trataba de un error en el
    // enunciado, dado que no tenía sentido su implementación.
				

Observa que el atributo que almacena la cola se declara de tipo interfaz ColaConPrioridad . La justificación es que el código sea lo más genérico posible. De este modo, si en algún momento se decide utilizar otra implementación de la cola en vez de un montículo, los cambios serán mínimos. Mantén esta filosofía en el código que desarrolles utilizando siempre que sea posible el tipo definido por el interfaz y evitando (en la medida de lo posible) las referencias a la clase que lo implementa.