FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIAS CARRERA: Licenciatura en Sistemas de Información

ASIGNATURA: Estructura de Datos y Programación TRABAJO PRÁCTICO Nº 5 Tema: Arboles. Objetivos: Que los alumnos logren…

       

Habilidad para identificar las distintas estructuras de tipo recursivas y capacidad para utilizar el concepto de recursión. Comprendan como funciona la estructura de datos dinámica árbol y reconozcan cuáles son sus operaciones básicas. Habilidad para aplicar diagramas UML básicos. Capacidad para resolver problemas usando las estructuras arbol y arbol de busqueda binaria. Capacidad para verificar la solución de algoritmos desarrollados usando POO Capacidad para usar, en forma eficiente, los distintos métodos de clasificación y de búsqueda. Destreza en el uso del entorno de desarrollo Netbeans y el lenguaje de programación Java. Capacidad para implementar correctamente las soluciones algorítmicas, en lenguaje de programación Java.

Fecha de presentación: 3 semanas a partir de la fecha del practico.

Consideraciones Generales:  Este trabajo práctico debe realizarse en forma individual.  La presentación implicará la entrega del material abrochado, o en una carpeta, contando con los siguientes ítems: o Carátula. Identificación completa del trabajo práctico con todos los datos del alumno y la asignatura, año, carrera, etc. o Desarrollo del práctico con hojas numeradas e identificadas, que deberá incluir:  Los algoritmos deben estar completamente desarrollados, de manera prolija, e incluyendo las descripciones necesarias para su mejor seguimiento (identificación, variables utlizadas y sus funciones, etc.), cumpliendo las indicaciones relativas a la diagramación estructurada y modular. o El Código de las aplicaciones solicitadas deberá enviarse al correo de la materia [email protected]. El nombre del código deberá estar conformado de acuerdo al siguiente esquema: carrera_ ApellidoNomdelAlumno_NumPrac_NumEjerc. Conceptos y definiciones Arbol General Definicion: Un arbol es un conjunto de uno o mas nodos tales que 1) Hay un nodo diseñado especialmente llamado raiz. 2) Los nodos restantes se dividen en n>= 0 conjuntos disyuntos t1, t2,.., tn en donde a cada uno de estos conjuntos en un arbol, se los denomina subarbol de la raiz. Arbol binario: un arbol binario es un conjunto finito de elementos que puede estar vacio o contener un elemento denominado Raiz del arbol y otros elementos divididos en 2 subconjuntos separados, cada uno de los cuales es en si un arbol binario. Esos 2 subconjuntos se denominan subarbol izquierdo y subarbol derecho original. Cada elemento del arbol se denomina nodo. A Hoja: nodo sin hijos Padre: A Hijo izquierdo: B Hijo derecho : C B C Hermanos: B y C Ancestros de B es A Descendiente: B es descendiente de A Nivel: es la longitud del camino que lo conecta a la raiz. La raiz del arbol tiene nivel 0 y el nivel de cualquier otro nodo en el arbol es uno mas que el nivel del padre. Altura: maximo nivel alcanzado por uno de sus nodos. El numero de ramas es el grado del nodo. Representacion del arbol a traves de un nodo. PI INFO PD Arbol binario completo: cuando tiene el maximo numero de nodos para su nivel. Cantidad de nodos: 2n -1 = 23 -1= 7 Pag.1 de 5

FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIAS CARRERA: Licenciatura en Sistemas de Información

ASIGNATURA: Estructura de Datos y Programación TRABAJO PRÁCTICO Nº 5 N= maximo nivel +1 Arbol binario casi completo:se encuentra lleno hasta el penultimo nivel y se esta llenando de izquierda a derecha en el ultimo nivel. Recorrido: pasar a traves del arbol visitando sus nodos una sola vez. En los arboles no hay un orden natural( no se puede determinar cual es el primero, el segundo o el ultimo). En profundidad de acuerdo al orden en que se visita: - Preorden: Raiz, Izquierda, Derecha. - Entreorden o simetrico: Izquierdo, Raiz, Derecho. - Postorden: Izquierdo, Derecho, Raiz. Arbol de busqueda binaria Un arbol binario de busqueda, es aquel que dado un nodo, todos los datos del subarbol derecho son mayores que los datos del nodo y los del subarbol izquierdo son menores. Operaciones: - Creacion, busqueda, insercion, eliminacion. Arboles balanceados: - Por su altura. - Por su peso. Resolver los siguientes problemas de tipo teórico, practico y experimental.

1. Dibujar un arbol binario casi completo de nivel 3 y realizar el seguimiento de cada uno de los recorridos (entreorden, postorden,preorden), para un mismo arbol (dibujar la pila). 2. Defina de manera formal e informal el TAD Arbol R de elementos enteros, determinando el método constructor y los métodos que permitan: a. Mostrar el árbol utilizando los recorridos: Entre-orden, Post-orden, Pre-orden. b. Recorrer el árbol R, usando recorrido entre-orden, e imprimir los nodos hojas. c. Recorrer el árbol R, usando recorrido entre-orden, e imprimir las cantidades de nodos que posean: (*) dos subarboles, (*) un solo subárbol y (*) los nodos hojas. d. Ingresar un elemento y buscarlo en el árbol R e informar si el elemento existe o no. e. Eliminar un elemento del árbol Raiz, contemplando todos los casos ( si es un nodo hoja, con un subárbol o con dos subarboles ).  Expresar el algoritmo solución en diagramas de flujo, para cada uno de los métodos.  Codificar y ejecutar el algoritmo solución en lenguaje Java, utilizando el entorno de desarrollo (IDE) Netbeans. 3. Crear la Aplicacion en Java, con las clases: a. ArbolApp, que implemente los métodos: - Generar : debe permitir ingresar un elemento y agregarlo al árbol, hasta que el operador decida no continuar. - Borrar : debe permitir ingresar un elemento y eliminarlo del árbol, hasta que el operador decida no continuar. - Imprimir: muestra la información de todos los nodos. b. Arbol, que implemente los siguientes métodos: - Crear: constructor del árbol en java seria Arbol(). - Insertar: agrega un nodo al árbol de búsqueda binaria. - Eliminar: desengancha un nodo del árbol y devuelve la dirección. c. Nodo, con los atributos Dato, PI y PD (puntero izquierdo, puntero derecho).  Expresar el algoritmo solución en diagramas de flujo, para cada uno de los métodos de las clases.  Codificar y ejecutar el algoritmo solución en lenguaje Java, utilizando el entorno de desarrollo (IDE) Netbeans. 4. Dado un árbol de búsqueda binario A no vacío: a. Eliminar todos los elementos pares. El árbol resultante debe mantener la condición de un árbol de búsqueda binario. El método retornará la cantidad de nodos eliminados. Pag.2 de 5

FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIAS CARRERA: Licenciatura en Sistemas de Información

ASIGNATURA: Estructura de Datos y Programación TRABAJO PRÁCTICO Nº 5 b. Obtener el nivel en que se encuentra el máximo valor de clave que existe en el árbol. Considere que la raíz de un árbol no vacío tiene el nivel 0.  Expresar el algoritmo solución en diagramas de flujo, para cada uno de los métodos.  Codificar y ejecutar el algoritmo solución en lenguaje Java, utilizando el entorno de desarrollo (IDE) Netbeans. 5. Dado un árbol de búsqueda binario H cargado con los datos de las habitaciones de un hotel y con la siguiente estructura de nodos: PI Numero Habitación Tipo de habitación Estado PD En donde el campo Estado tiene el valor 0 (habitación disponible), o 1 (habitación ocupada).  Expresar el algoritmo solución en diagramas de flujo, para cada uno de los métodos indicados a continuación. a. Método Búsqueda: Dado el número de una habitación devuelve el Estado. El estado de una habitación puede ser disponible u ocupado. b. Método Añadir: Ingresa los datos de una nueva habitación en el hotel. En el caso de que la habitación ya exista emitir un mensaje informando dicha situación. c. Método Mostrar: Dado un tipo de habitación visualiza la información contenida en el árbol en orden descendente por Número de habitación y muestra la cantidad de habitaciones disponibles considerando también dicho tipo de habitación.  Codificar y ejecutar los algoritmos solución en lenguaje Java, utilizando el entorno de desarrollo (IDE) Netbeans. . 6. En una Distribuidora de productos informaticos, se tiene un listado de productos desordenado, al cual se requiere acceder en forma frecuente. Para agilizar la búsqueda, se decide indexar la lista (generar un índice ordenado sobre la lista) utilizando para ello un Árbol de Búsqueda Binaria. Presentar un menú con las siguientes a. Generar árbol: Debe permitir generar opciones: un árbol de búsqueda binaria llamado Índice, con nodos del tipo: DISTRIBUIDORA INFO 12340-

Generar arbol Buscar un Producto Eliminar un Producto Agregar un Producto Salir Ingrese su opción:



PI

Codigo_Prod

Puntero_Prod

PD

Cada nodo debe generarse a partir de los datos de la lista de productos. La lista contiene los datos código, descripcion, precio, y stock del producto. Por cada nodo de la lista se genera un nodo en el árbol Índice, con el código y la dirección del nodo de la lista en el campo puntero_Prod. No debe haber claves iguales.

b. Buscar un producto: se ingresa un código de producto y se muestran los datos descripción, precio, y stock. La búsqueda se realiza en el árbol Índice y se accede a la lista a través del puntero_Prod. c. Eliminar un producto: ingresar un código de producto y mostrar los datos del producto. Eliminar el producto, solo si el campo Stock es igual a 0, caso contrario mostrar mensaje “No es posible la eliminación del producto”. Se debe eliminar de la lista productos y del árbol Índice. d. Agregar un producto: se ingresa el código del producto, si existe en la lista, se debe modificar el campo Stock, caso contrario se agregan en la lista los datos del producto, y se genera un nodo en el árbol Índice con el código y la dirección del puntero_Prod. Expresar el algoritmo solución en diagramas de flujo, para cada uno de los métodos de las clases. Pag.3 de 5

FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIAS CARRERA: Licenciatura en Sistemas de Información

ASIGNATURA: Estructura de Datos y Programación TRABAJO PRÁCTICO Nº 5 

Codifique y ejecute el algoritmo solución en lenguaje Java, utilizando el entorno de desarrollo (IDE) Netbeans.

7. El método de ordenamiento HeapSort, usa un apilamiento o montículo, que es un árbol binario casi completo, en donde el valor del padre es siempre mayor que el valor de sus hijos. Este árbol está representado secuencialmente. Se pide resolver el siguiente problema siguiendo este método: Dada las notas de los alumnos de la asignatura Programación, para los Parciales 1, 2 y 3, se pide ordenar los alumnos por orden decreciente de notas medias individuales. En el ANEXO se encuentra el código del Método de ordenamiento. Adaptelo para resolver el problema dado. Ejecutar y probar. 8. Después de leer en el libro “Estructura de Datos y Organización de Archivos”, de M.LOOMIS, el capitulo 14: Estructuras indexadas. Realice lo siguiente: a. Armar el Arbol de búsqueda de m-vias, con los siguientes valores : 28, 17, 43, 58, 72, 9. b. Considere la inserción de las claves: 61, 85, 47 y la eliminacion: 85, 17, 9. c. Para los mismos valores utilizados en el ítem anterior, arme el Arbol B de orden m. d. Considere la inserción de las claves: 41, 87, 90 y la eliminación de las claves: 17, 72, 28. e. Explique la inserción y eliminación utilizando graficos. f. ¿En cual de estos arboles la búsqueda es mas eficiente? Justifique su respuesta. g. Visite las paginas de Animación de los árboles: people.ksp.sk/~kuko/bak/ http://usuarios.multimania.es/arbolesbpro/animaciones.htm Compare con lo realizado en el ítem b y elabore una conclusión. 9. Dibuje el árbol AVL T que resulta de insertar las claves: 14, 6, 4, 24, 17, 35, 32, 59 partiendo de un árbol vacío. Eliminar la clave 4 e insertar la clave 63. Dibujar el árbol antes y después de cada operación que requiera un rebalanceo. Aplicar Rotación para equilibrar el árbol T, si fuera necesario. En el libro “Estructura de Datos”, Joyanes Aguilar - Zahonero Martínez. Capitulo 11, se encuentra el código para Arbol AVL. Adaptelo para generar el árbol T, ejecutar y probar el codigo.

Recursos Bibliograficos  JOYANES AGUILAR LUIS ZAHONERO MARTINEZ IGNACIO. “Estructuras de Datos en Java”. Mc Graw Hill -2008  JOYANES AGUILAR LUIS ZAHONERO MARTINEZ IGNACIO. “Programación en JAVA 2 - Algoritmos, Estructuras de Datos y Programación orientada a objetos”. Mc Graw Hill -2002  JOYANES AGUILAR LUIS ZAHONERO MARTINEZ IGNACIO. “Estructuras de

Datos”.Algoritmos, abstracción y objetos. Mc Graw Hill - 2008.  MARY S. LOOMIS.Estructura de Datos y Organización de Archivos.Hall Hispanoamericana S.A.. 1991.  CAIRO, OSVALDO. Estructura de datos. Mc Graw Hill – 2006

Recursos de Software  Entorno de Desarrollo NetBeans versión 7.1.  Java 2EE.

Pag.4 de 5

FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIAS CARRERA: Licenciatura en Sistemas de Información

ASIGNATURA: Estructura de Datos y Programación TRABAJO PRÁCTICO Nº 5 ANEXO // clase aplicacion--------------------------------------------------import java.util.Scanner; public class App { int A[]; Scanner ingreso = new Scanner(System.in); public App() { A = new int[10]; } public void cargarArreglo() { …..// completar codigo } public static int hijoIzquierdo(int i){ return 2 * i + 1; } public void Criba(int A[], int i, int n){ int hijo; int aux; for(aux = A[i]; hijoIzquierdo(i) < n; i = hijo) { hijo = hijoIzquierdo( i ); if( hijo != n - 1 && A[ hijo ]> A[ hijo + 1 ] ) hijo++; if( aux > A[ hijo ] ) A[ i ] = A[ hijo ]; else break; } // cierre del for A[ i ] = aux; } public void ordenacionHeapSort(int A[]) { for (int i =A.length/2; i >= 0; i--) { Criba(A, i, A.length); } for(int i = A.length - 1; i > 0; i--){ int aux = A[0]; A[0] = A[i]; A[i] = aux; Criba(A, 0, i); } } public void imprimir(int A[]){ ….. // completar codigo } //clase principal -----------------------------------------------------public class Principal { public static void main(String[] args) { App prueba = new App(); prueba.cargarArreglo(); System.out.println("\n\nDesordenado"); prueba.imprimir(prueba.A); prueba.ordenacionHeapSort(prueba.A); System.out.println("\n\nOrdenado"); prueba.imprimir(prueba.A); } }

Pag.5 de 5