Universidad Carlos III de Madrid

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

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

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

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

Practicar los recorridos sobre árboles binarios.

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.

Profundizar en el manejo de estructuras de datos árboles.

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

Profundizar en el manejo de estructuras de datos árboles.

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

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

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

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.

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

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.

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

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 :

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

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

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

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