LABORATORIO DE ESTRUCTURAS DE DATOS PRÁCTICAS CURSO 1996-97 1º INGENIERÍA INFORMÁTICA

PRÁCTICA Nº 7: una sesión

(Semana del 19 al 23 de Mayo de 1997)

ÁRBOLES DE DECISIÓN

1. PLANTEAMIENTO DEL PROBLEMA

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.

2. REALIZACIÓN DE LA PRÁCTICA

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

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