Universidad Carlos III de Madrid

Ingeniería de Telecomunicación

Enero-Mayo 2010 / January-May 2010

Árboles

Lab Section1. Sesión 2 (laboratorio): Árboles (I)

Exercise Section1.1. Árbol binario: implementación

Objetivo

Instruir al alumno en la implementación y utilización de árboles binarios.

Ejercicio

En este ejercicio se utilizará la definición recursiva de árbol para diseñar una clase Java que implemente un árbol binario. De acuerdo a la definición, un árbol binario es, o bien vacío o consta de un elemento raíz y, a lo sumo, dos árboles hijo (izquierdo y/o derecho).

Nota

Recuerda que se necesitan dos clases, BTree y BNode, para poder modelar adecuadamente el árbol vacío.

  • Crea la clase BTree 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 BNode basándote en la definición recursiva anterior, que encapsule la información a almacenar en el nodo y las referencias a los hijos izquierdo y derecho. Programa un constructor que reciba como parámetro el elemento (de la clase Object) a almacenar en el nodo (e inicializa sus hijos a null). Programa también los correspondientes métodos accesores (get y set).

  • Programa la clase excepción BTreeException, con un constructor que reciba un mensaje, de tipo String.

Exercise Section1.2. Inserción y borrado de elementos en un árbol binario

Objetivo

Entrenar al alumno en los métodos de inserción y borrado en árboles binarios.

Ejercicio

Dado un árbol binario implementar los métodos que permitan insertar un subárbol en el árbol y extraer un subárbol del mismo.

  • Programa el método void insert(BNode tree, int side) throws BTreeException en la clase BNode, que permite añadir el subárbol que se pasa por parámetro en el lado correspondiente. Si ya existe el subárbol, el método lanzará una BTreeException con el mensaje de eror correspondiente.

    Declara, en la clase BNode, las constantes de clase LEFT_SIDE y RIGHT_SIDE necesarias. Si se introduce un lado incorrecto, o hay un subárbol no vacío en el lado indicado, debe lanzarse la excepción BTreeException.

  • Programa el método BNode extract(int side) throws BTreeException, que extrae y elimina el subárbol del lado que se le pasa como parámetro. En caso de que el lado no sea correcto, el método lanzará una BTreeException con el mensaje de error correspondiente.

Exercise Section1.3. Recorridos en árboles binarios.

Objetivo

Practicar los recorridos sobre árboles binarios.

Ejercicio

Dado el árbol binario BTree del ejercicio anterior, programa los recorridos (Pre-Orden, In-Orden, Post-Orden) que permitan recorrer, de forma recursiva, el árbol.

  • Programa el método void printPreOrder() que recorra el árbol en pre-orden, imprimiendo en pantalla el elemento contenido en cada nodo.

  • Programa el método void printInOrder() que recorra el árbol en in-orden, imprimiendo en pantalla el elemento contenido en cada nodo.

  • Programa el método void printPostOrder() que recorra el árbol en post-orden, imprimiendo en pantalla el elemento contenido en cada nodo.

Exercise Section1.4. Altura de un árbol

Objetivo

Profundizar en el manejo de estructuras de datos árboles.

Ejercicio

Dado un árbol binario, BTree, implementar un método en éste que devuelva la altura del mismo.

Exercise Section1.5. Tamaño de un árbol

Objetivo

Profundizar en el manejo de estructuras de datos árboles.

Ejercicio

Dado un árbol binario, BTree, implementar un método en éste que devuelva el número de nodos que tiene.

Exercise Section1.6. Utilización de un árbol binario

Objetivo

Instruir al alumno en la utilización de árboles binarios.

Ejercicio

En este ejercicio debes utilizar las clases BTree y BNode programadas en los ejercicios anteriores. Para ello, debes programar una clase TongueTwister (Trabalenguas), que en su método main cree un árbol con la siguiente estructura:

               Tres
                |
       --------------------
       |                  |
    tristes             tigres
       |
  ------------
  |          |
  |          |
comían     trigo
  • Imprime el árbol binario usando los métodos programados en el anterior ejercicio. Comprueba que el orden en que aparecen los elementos en pantalla sea el correcto.

  • Haz los cambios que necesites, en la estructura del árbol binario, para que, imprimiendo en pre-orden, aparezca en pantalla "Tres tristes tigres comían trigo".

Homework Section2. Actividades para casa

Exercise Section2.1. Árboles N-arios y sistemas de ficheros

Objetivo

Estudiar otro tipo de árboles más genéricos que los binarios, proponiéndo 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.

Árboles N-arios y sistemas de ficheros

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.

Figura 1. Representación gráfica de un árbol N-ario

Representación gráfica de un árbol N-ario

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:

  • name es un atributo de tipo String que almacena el nombre de la carpeta

  • subdirectories es un atributo de tipo Vector que almacena los subdirectorios (objetos de tipo Folder ) que contiene la carpeta.

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.

Figura 2. Representación gráfica de un sistema de ficheros modelado con objetos Java

Representación gráfica de un sistema de ficheros modelado con objetos Java


Ejercicio

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 Vector (si no sabes cómo usarla, consulta el API) , para lo que se pide implementar los siguientes métodos de la clase Folder :

  1. public Folder addSubdirectory(String folderName) : añade una nueva carpeta, con nombre folderName , a la colección de subdirectorios y devuelve una referencia a la misma.

  2. public void printSubdirectories() : imprime en pantalla el nombre de todos los subdirectorios de la carpeta en el formato: subdirectorio1 subdirectorio2 ... subdirectorioN. Sólo se imprimirán los subdirectorios, sin tener en cuenta los subdirectorios que pudiera tener cada uno de éstos.

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 Vector 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 se creaste previamente):

  1. public Folder searchFolder(Folder root, String folderName) : busca la carpeta cuyo nombre es folderName en todo el árbol. Si la carpeta existe, se devuelve una referencia a la misma, o null en caso contrario. Pista: este método es recursivo ya que, para cada carpeta, hay que recorrer todos sus subdirectorios, los subdirectorios de éstos y así sucesivamente hasta cubrir todo el árbol. Tal vez sea útil utilizar un método auxiliar private Folder searchFolder(Folder root, String folderName) , donde root será el nodo raíz de cada subárbol sobre el que se vaya a hacer la búsqueda de la carpeta especificada.

  2. public Folder addNewFolder(String parentFolderName, String newFolderName): crea una nueva carpeta de nombre newFolderName , y la añade como subdirectorio de la carpeta cuyo nombre es parentFolderName . Si ya existe una carpeta en el sistema de ficheros con el nombre newFolderName , o si la carpeta parentFolderName no existe, no se debe hacer nada y se devuelve null . En caso contrario, se crea y añade la nueva carpeta y se devuelve una referencia a la misma.

  3. public void printFileSystem() : imprime la estructura del sistema de ficheros con el siguiente formato:

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

    Pista: este método es también recursivo. Además, el número de espacios en blanco antes de cada nombre tiene mucho que ver con el nivel del árbol en el que se encuentra la carpeta. Tal vez pueda ser útil crear un método auxiliar private void printFileSystem(Folder root, int level) con el que se harán las llamadas recursivas.

Exercise Section2.2. Problema de examen para trabajar con Árboles Binarios.

Objetivo

Estudiar una posible aplicación de árboles binarios para resolver expresiones sencillas.

Problema de examen

Una expresión es una determinada combinación de operadores y operandos que se evalúan para obtener un resultado particular. La forma más habitual de escribir una expresión es la conocida como "infija" en la que el orden de la combinación de los anteriores es: primer operando, operador y segundo operando. A continuación, se muestra un ejemplo de expresión infija (sin uso de paréntesis para mayor sencillez):

a-b*c+d

Sin embargo, existe otro tipo de notación que la anterior expresión, más conocida como "postfija", en la que cambia el orden de la combinación a: primer operando, segundo operando y operador, es decir, que el operador pasa al final de la combinación. Según esta regla, la expresión infija inicial se transforma en la siguiente expresión postfija equivalente:

abc*-d+

Las expresiones postfijas tienen muchas ventajas a la hora de su posterior tratamiento informático ya que, por ejemplo, no requieren del uso de paréntesis para ser evaluadas y, además, dicha evaluación se puede realizar mediante algoritmos sencillos como se comprobará en este problema. Teniendo en cuenta que cualquier expresión infija tiene su equivalente en notación postfija, esto proporciona una gran versatilidad y agilidad a la hora de plantear y resolver el problema de la evaluación de expresiones.

Otra de las grandes ventajas de las expresiones postfijas es que pueden representarse en forma de un Arbol de Sintaxis Abstracta (AST). Un AST es un árbol binario cuyas hojas contienen los caracteres asociados a los operandos (a,b,c,d...) y el resto de nodos contienen los caracteres asociados a los operadores (+,-,*,/). El árbol binario AST de la anterior expresión postfija se muestra a continuación:

Mediante el uso de esta representación de la expresión postfija en forma de árbol binario AST, la evaluación de la misma se reduce a realizar un sencillo algoritmo de recorrido recursivo en POSTORDEN del mismo y usando una estructura auxiliar de datos para almacenar los resultados intermedios del procesamiento de los nodos en el recorrido del mismo. Tanto para la creación como para la evaluación del árbol binario AST, las estructuras necesarias serán DOS PILAS AUXILIARES respectivas de datos: una pila de nodos binarios y una pila de valores decimales(float) que permitirán crear la estructura de los nodos del árbol así como almacenar los resultados de las operaciones intermedias de la evaluación del mismo. Por último, para evaluar numéricamente la expresión, será necesaria una tabla adicional que almacene los valores numéricos de los operandos de la expresión, para lo que se usará una tabla HASH auxiliar.

El interfaz Operator contiene todos los operadores posibles que intervienen en las expresiones (para simplificar el problema, solo se consideran operadores binarios):

public interface Operator {

  public static final char SUM = '+';
  public static final char SUBTRACTION = '-';
  public static final char PRODUCT = '*';
  public static final char DIVISION = '/';

}

La clase PostfixExprEvaluator implementa el anterior interfaz y contiene el árbol binario AST asociado a la expresión, además de las estructuras de datos necesarias para crear el árbol y evaluar la expresión postfija. En este caso, serán dos PILAS de datos auxiliares para almacenar tanto nodos como valores intermedios. La declaración de la clase es la siguiente:

public class PostfixExprEvaluator implements Operator {

  Node postfixASTTree = null; // The root node of the AST postfix expression tree

  Stack stackNodes = null; // Auxiliary stack to store the nodes of the AST tree

  Stack stackResults = null; //Auxiliary stack to store the intermediate results

Nota

El objeto que implementa una pila es el que se proporciona en el JDK(java.util.Stack) y cuyos métodos para apilar y des-apilar datos se declaran a continuación:

public Object push(Object item); // Stack data on top of the stack

public Object pop(); // Unstack data from the top of the stack

La clase Node representa el nodo binario del árbol AST y almacena cada carácter(char) de la expresión postfija que puede ser tanto un operador(+,-,*,/) o un operando(a, b, c, d...):

class Node {
    char value = '\0'; // The character (either an operand or a operator)
    
    Node left = null;  // The reference to the left child node of the binary tree
    Node der = null; // The reference to the right child node of the binary tree
Ejercicio 1: Creación del Arbol de Sintaxis Abstracta (AST).

Para crear el árbol binario AST que guardará la expresión postfija se necesita una PILA de Nodos binarios(Node) que servirá para construir el árbol binario a medida que se procesan sus elementos. La siguiente figura muestra el proceso general:

El procedimiento para crear el árbol binario AST es el siguiente:

  • Para cada uno de los caracteres de la expresión postfija hacer lo siguiente:

    • Si el carácter analizado es un operando (a,b,c,d...), crea un nuevo nodo binario sin hijos que contenga el carácter y apílalo en la PILA.

    • Si el elemento analizado es un operador(+,-,*,/) , crea un nuevo nodo binario de la siguiente manera:

      • Extrae dos nodos binarios de la PILA.

        • El primer elemento extraído de la PILA será el hijo DERECHO del nuevo nodo binario.

        • El segundo elemento extraído de la PILA es el hijo IZQUIERDO del nuevo nodo binario.

      • El dato que almacenará el nuevo nodo binario será el carácter que representa el operador.

      • Una vez creado el nuevo nodo binario, apílalo en la PILA.

  • Por último, devuelve el nodo raíz del árbol binario AST creado y que es precisamente el que se obtiene de desapilar el único nodo binario restante que queda en la PILA.

Implementa el siguiente método de la clase PostfixExprEvaluator que permite crear el árbol binario AST a partir de una expresión postfija de acuerdo al anterior procedimiento:

Node createPostfixTree( String sPostfix ) throws Exception

Ejercicio 2: Recorrido y evaluación del Arbol de Sintaxis Abstracta (AST).

Una expresión postfija se puede evaluar fácilmente mediante el uso de un recorrido en POSTORDEN del arbol binario AST asociado e implementado en el ejercicio anterior. Para ello, también será necesario tener dos estructuras de datos auxiliares: una PILA y un DICCIONARIO de VALORES, tal y como se muestra en la siguiente figura:

Nota

El DICCIONARIO de valores contiene los valores enteros correspondientes de los operandos(a,b,c,d....). Para ello, se ha decidido usar un objeto de tipo Hashtable que proporciona el JDK (java.util.Hashtable) y que permite mapear una serie de claves con sus valores correspondientes. En este caso, la clave será el carácter asociado al operando. Para obtener el valor entero asociado a un operando, usa el siguiente método de la clase, donde key es el carácter(char) asociado al mismo.

public Object get(Object key)  //Returns the value to which the specified key is mapped in this hashtable. 

El procedimento para conseguir la evaluación del árbol binario AST se basa en hacer un recorrido en POSTORDEN del mismo realizando el siguiente proceso en cada nodo binario del árbol:

  1. Si el nodo a evaluar es un operando (a,b,c,d....)

    • Apilar en la PILA de resultados el valor entero (int) del operando que se obtiene previamente del DICCIONARIO de VALORES auxiliar.

  2. Si el nodo a evaluar es un operador binario (+,-,*,/)

    • Des-apilar dos valores de la PILA de resultados, calcular el resultado de aplicar el operador a dichos valores y, por último, apilar dicho resultado de nuevo en la PILA de Resultados.

Implementa el siguiente método RECURSIVO de la clase Node que implementa el recorrido en POSTORDEN del árbol binario AST de acuerdo al anterior procedimiento:

void processNode( Hashtable values, Stack stackResults ) throws Exception