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).

Crea la clase NTree basándote en la definición recursiva anterior. Programa un constructor sin parámetros que inicialice un árbol vacío. Programa un constructor adicional que reciba como parámetro el elemento (de la clase Object) a almacenar en el nodo raíz.

Crea la clase NNode basándote en la definición recursiva anterior, que encapsule la información a almacenar en el nodo y un Vector con las referencias a los hijos. Programa un constructor que reciba como parámetro el elemento (de la clase Object) a almacenar en el nodo. Programa también los correspondientes métodos accesores (get y set).

Programa el método size que devuelve el tamaño (número de nodos) del árbol.

Programa el método preorder que imprime los elementos del árbol siguiendo un recorrido preorden.

Necesitarás métodos auxiliares para construir y recorrer el árbol, como int getNumberOfChildren(), void addChild(NNode child), void addChildAt(int index, NNode child), NNode getChildAt(int index), y otros.

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 PriorityQueue {

  static int MAX_PRIORITY = 1;

  /**
   * Insert the indicated object in the correct position in the queue, depending
   * on its priority. Priority is declared with a natural number (> 0). The
   * bigger is this number, the lower is the element priority associated with
   * the number. The value 1 corresponds to elements with maximum priority.
   */
  void insert(int priority, Object info);

  /**
   * Extract the object with highest priority out of the queue (that is, the one
   * with the minimum priority) In case that several elements have the same high
   * priority, the first introduced (FIFO) will be returned. If queue is empty,
   * null is returned.
   */
  Object extract();

  /**
   * Returns the number of elements in the queue.
   */
  int size();

  /**
   * Indicates if the queue is empty.
   */
  boolean isEmpty();

}

				

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 PrintQueueManager {

  PriorityQueue queue;

  /**
   * Initialize the manager, empty.
   */
  public PrintQueueManager() {
    // to be completed by the student
  }

  /**
   * Adds a new work to print, with the indicated priority. *
   */
  public void print(int priority, String file) {
    // to be completed by the student

  }

  /**
   * Processes (prints out of the printer) the first work of the queue, with the
   * highest priority, reorganizing the data structure.
   */
  public void process() {
    // to be completed by the student
  }
}

				

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.