Download ASIGNATURA :: Programació nn TRABAJO PRÁCTICO Nº 5

FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIAS
CARRERA: Profesorado en Informática
ASIGNATURA: 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: Profesorado en Informática
ASIGNATURA: 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: Profesorado en Informática
ASIGNATURA: 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: Profesorado en Informática
ASIGNATURA: 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: Profesorado en Informática
ASIGNATURA: 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