LABORATORIO DE ESTRUCTURAS DE DATOS

PRÁCTICA Nº 6: 1 sesión

(del 8 al 12 de Mayo de 2000)

Árboles de decisión
0. Objetivo

Manipulación y familiarización con árboles binarios.

Escribir una unidad genérica en Turbo Pascal de tratamiento de árboles binarios.

Escribir un programa en Turbo Pascal que haga uso de la unidad genérica antes escrita

1. Árboles de decisión

Los árboles de decisión permiten representar el conjunto de todas las soluciones alternativas a un problema. De alguna manera, representan una clasificación de las soluciones en función de una serie de características.

Por ejemplo, si se plantea el problema de una clasificación animal, se podrían considerar características de los animales tales como: ¿Es terrestre?, ¿Es mamífero?, ¿Vuela?, ¿Es carnívoro?, etc. En ese caso, para realizar la clasificación, es posible utilizar un árbol binario de decisión que esté planteado de forma que se indique si el animal posee o no una determinada característica.

Ejemplo:

Como se puede ver en este ejemplo, los animales ocupan siempre los nodos terminales del árbol, mientras que las características (o preguntas) son nodos interiores del árbol.

2. Unidad para la especificación de la estructura de datos "Árbol Binario"

En primer lugar escribieremos una unidad genérica de manipulación de árboles binarios, teniendo en cuenta que la información que contendran los nodos del árbol serán siempre cadenas de caracteres de a lo sumo 25 caracteres.

Las operaciones que deberemos incluir en la unidad serán:

Procedure IniciarArbol ( arb: Arbol );

Function ArbolVacio ( arb: Arbol ): Boolean;

Function HijoIzq ( arb: Arbol; Var izq: Arbol ): Boolean;

Function HijoDer ( arb: Arbol; Var der: Arbol ): Boolean;

Function Informacion ( arb: Arbol; Var x : Valor ): Boolean;

Function HacerArbol ( arb: Arbol; x: Valor; arb: Arbol ): Arbol;

Tal como se vieron en clase.

3. Trabajo con Árboles

En esta práctica se pide manipular un árbol de decisión que sigue el esquema del ejemplo anteriormente expuesto.

- En primer lugar, se pide generar el árbol binario de decisión cuya estructura está almacenada en el archivo 'animales.arb'. Se trata de un archivo texto en el que el árbol se ha almacenado según el siguiente formato: cada línea representa la información de un nodo del árbol (la longitud máxima de una línea es 25 caracteres), si la información es '.' significa que el árbol correspondiente debe estar vacío, se ha empleado el criterio Prefijo para el recorrido del árbol.

- En segundo lugar, se trataría de que fuera posible recorrer el árbol interaccionando con el usuario del programa de la siguiente manera: comenzando por el nodo raíz, si el nodo es no terminal entonces interpretar la información del nodo como una pregunta a realizar al usuario, en función de la respuesta a dicha pregunta avanzar al siguiente nodo (se supone que los subárboles izquierdos corresponden a respuestas afirmativas y los derechos a respuestas negativas). Este proceso se repite hasta alcanzar un nodo terminal, en cuyo caso se indicará el nombre del animal que cumple todas las características que ha indicado el usuario.

4. Entrega de programas

Al finalizar la sesión de prácticas se entregarán al profesor dos programas en Turbo Pascal llamados: ‘U_Arb.pas’ y ‘Animal.pas’ que cumpla los requisitos reseñados en el enunciado de la práctica.

ENTREGA DE PROGRAMAS: Al finalizar la sesión de prácticas correspondiente.