Universidad Carlos III de Madrid

A continuación se muestra la interfaz BTree que usará en esta práctica.

public interface BTree<E> {
    static final int LEFT = 0;
    static final int RIGHT = 1;

    boolean isEmpty();

    E getInfo() throws BTreeException;
    BTree<E> getLeft() throws BTreeException;
    BTree<E> getRight() throws BTreeException;

    void insert(BTree<E> tree, int side) throws BTreeException;
    BTree<E> extract(int side) throws BTreeException;

    String toStringPreOrder();
    String toStringInOrder();
    String toStringPostOrder();
    String toString(); // pre-order

    int size();
    int height();

    boolean equals(BTree<E> tree);
    boolean find(BTree<E> tree);
}

Añada comentarios a la interfaz explicando para qué sirven sus atributos. Explique también qué hace y para qué sirve cada método, sus argumentos de entrada y sus valores de retorno. Explique también en qué condiciones se lanzan excepciones.

Suponga que trabaja para el departamento de desarrollo de una agencia de viajes. La agencia oferta una serie de vuelos a diferentes ciudades del mundo. En cada ciudad el cliente puede elegir entre dos destinos diferentes, aunque por motivos climatológicos, algunos de estos viajes están cerrados.

Suponga también que su departamento ya dispone de una implementación de la interfaz del apartado anterior, y se llama LBTree (Linked Binary Tree). Le piden hacer una aplicación para gestionar la oferta de viajes anteriormente explicada.

Responda (en papel) a las siguientes preguntas sobre la aplicación, suponiendo que se tiene un árbol de viajes como el de la siguiente figura:

Cuando haya respondido a las preguntas por escrito, sigua leyendo.

Programe (también en papel) el método main de esta aplicación que crea el árbol de la figura e imprime por salida estándar las respuestas a las preguntas anteriores.

Puede suponer que los elementos almacenados en el árbol son Strings, que contienen el nombre de las ciudades y que la clase LBTree tiene dos constructores: LBTree(E info) y LBTree().

Preste especial atención al manejo de excepciones y a introducir correctamente unos árboles en otros para que el resultado sea como el de la figura.

A continuación se muestra un ejemplo de ejecución de esta aplicación:

     Warning: SPOILERS BELLOW!


















; java Cities
Madrid tree size = 11
Madrid tree = Madrid Paris Brussels Hanoi Kiev Berlin Lima Moscow Prague Seoul Taipei 
Moscow tree size = 4
Moscow tree = Seoul Taipei Prague Moscow 

Programe la clase LBTree<E> que implemente la interfaz BTree, la clase LBNode<E> que la acompaña y la clase BTreeException.

Empieze por la clase BTreeException, que hereda de Exception y simplemente tiene un constructor que recibe un mensaje, de tipo String.

A continuación programe la clase LBNode<E> partiendo de la siguiente plantilla:

  class LBNode<E> {

    /* your attributes here */

    LBNode(E info, BTree<E> left, BTree<E> right) {
        /* your code here */
    }

    E getInfo() {
        /* your code here */
    }

    void setInfo(E info) {
        /* your code here */
    }

    BTree<E> getLeft() {
        /* your code here */
    }

    void setLeft(BTree<E> left) {
        /* your code here */
    }

    BTree<E> getRight() {
        /* your code here */
    }

    void setRight(BTree<E> right) {
        /* your code here */
    }
}

Termine por programar la clase LBTree<E>, que debe tener dos constructores:

Puede probar su práctica con la clase LBTreeTest.java, que realiza pruebas exhaustivas de cada uno de los métodos de la clase LBTree.

Para entender los errores que le descubrirá esta clase, tendrá primeramente que entender cómo funciona el ćodigo de las pruebas.

A continuación se muestra un ejemplo de ejecución de esta clase, suponiendo que se dispone de una implementación correcta de LBTree:

; java LBTreeTest 
testing isEmpty: OK
testing getInfo: OK
testing insert: OK
testing getLeft: OK
testing getRight: OK
testing extract: OK
testing toStringPreOrder: OK
testing toStringInOrder: OK
testing toStringPostOrder: OK
testing toString: OK
testing size: OK
testing height: OK
testing equals: OK
testing find: OK

Volviendo al ejemplo de la agencia de viajes. Suponga que otro departamento de su empresa usa una implementación diferente de BTree, que ellos llaman ABTree, ya que sus nodos (que ellos llaman ABnode) utilizan un array para almacenar los subárboles, en lugar de usar referencias como usted.

La raíz de sus árboles, es por tanto una referencia a ABNode, que además se llama "wurzel" (en lugar de "root", ya que este otro departamento está en Alemania).

Responda a las siguientes preguntas razonadamente:

Estudiar otro tipo de árboles más genéricos que los binarios, proponiendo un ejemplo concreto de aplicación: los sistemas de ficheros. Se pretende que los alumnos aprendan a generalizar las operaciones que han visto en el caso de árboles binarios para aplicarlas al caso de árboles N-arios.

Hasta ahora hemos trabajado con árboles binarios, pero no son el único tipo de árbol existente. En algunas ocasiones necesitamos árboles más flexibles que nos permitan tener, por cada nodo, un número N de nodos hijo que no tiene por qué ser exactamente dos, y que puede ser diferente para cada nodo. Esta estructura de datos es lo que se conoce como árbol N-ario y se muestra en la figura 1 . Cada nodo del árbol contiene una referencia a la información que se quiere almacenar ( info ), y un conjunto de referencias a los nodos hijo ( children ). Para acceder a todos los nodos del árbol tan sólo necesitamos una referencia a su nodo raíz ( root ), tal y como ocurría en el caso de árboles binarios.

En este ejercicio vamos a ver un ejemplo en el que se necesitan árboles N-arios: los sistemas de ficheros. Supongamos que tenemos el siguiente sistema de ficheros (también conocido como árbol de directorios):

C:
  |_Archivos de programa
    |_Eclipse
    |_Java
  |_Mis documentos
    |_Imagenes
    |_Musica
    |_Videos
  |_ProgSis
    |_Proyecto
      |_Modulo1
      |_Modulo2

Tal y como su nombre indica, todos los directorios o carpetas (en nuestro caso, para simplificar, vamos a ignorar los archivos) se organizan en forma de árbol: existe un nodo raíz (C:) que contiene varias carpetas, cada una de las cuales contiene a su vez más carpetas, y así sucesivamente. Para crear y manejar este sitema de ficheros, vamos a tomar la estructura genérica mostrada en la figura 1 , y la vamos a particularizar para adaptarla al caso que nos ocupa. Los nodos de la imagen serán nuestras carpetas. Cada carpeta está representada mediante un objeto de tipo Folder. Cada uno de estos objetos posee dos atributos:

Para representar el sistema de ficheros, haremos uso de una clase FileSystem que desempeña el papel de árbol, puesto que es la que contiene una referencia al nodo raíz (atributo root de tipo Folder ), desde el cual se puede acceder al resto de carpetas (nodos) del sistema de ficheros.

La figura 2 representa el sistema de ficheros del ejemplo previo representado mediante los objetos Java que vamos a manejar.

Para facilitar la realización de este ejercicio, se proporciona parte de la clase Folder , así como la estructura de la clase FileSystem, que se pueden descargar en los siguientes enlaces :

En primer lugar, se va a practicar el uso de objetos de la clase ArrayList, para lo que se pide implementar los siguientes métodos de la clase Folder :

Antes de seguir avanzando asegúrate de que los métodos funcionan correctamente. Para ello, crea una clase FileSystemTest.java para comprobar el funcionamiento.

Una vez tenemos claro cómo funcionan los objetos de tipo Folder y cómo recorrer el objeto de la clase ArrayList que contiene los subdirectorios (nodos hijo) de cada carpeta, nos centraremos en el sistema de ficheros en sí. Para ello se pide implementar los siguientes métodos de la clase FileSystem (además de realizar las pruebas necesarias para comprobar su correcto funcionamiento con la clase FileSystemTest que creaste previamente):