Download Práctico Árboles Binarios de Búsqueda 1. Dibujar - Itsp

Práctico Árboles Binarios de Búsqueda
1. Dibujar el árbol binario de búsqueda siguiente:
i)
6, 9, 13, 14, 15, 17, 20, 26, 64, 72
ii) 3,1,4,6,9,2,5,7
iii) 5,2,4,3,7,9,6,1
2. De los árboles anteriores, indicar para cada uno el resultado de recorrerlo postorden,
preorden e inorden.
3. El recorrido en preorden de un determinado árbol binario es: GEAIBMCLDFKJH y en
inorden IABEGLDCFMKHJ .Resolver:
i)
Dibujar el árbol binario.
ii) Dar el recorrido en postorden.
iii) Eliminar el elemento B, el D y el M y volver a dibujar el árbol luego de cada
borrado.
4. Implementar un árbol binario de búsqueda con sus operaciones básicas.
5. Crear un procedimiento/función que cuente cuántos nodos hay.
6. Crear un procedimiento/función que cuente cuántos niveles hay.
7. Crear un procedimiento/función que me indique si un nodo es hoja.
8. Crear un procedimiento/función que cuente cuántas hojas hay.
9. Crear un procedimiento/función que me indique si un árbol binario está completo.
Total de nodos en un árbol binario completo: 2n-1. Siendo n: nivel.
10. Crear un procedimiento/función que me indique si un valor x dado por el usuario se
encuentra en el árbol.
11. Dado un árbol de búsqueda binario H cargado con los datos de las habitaciones de un
hotel y con los siguientes datos: número de habitación, tipo de habitación, estado.
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:
i)
Búsqueda: Dado el número de una habitación devuelve el Estado. El estado de una
habitación puede ser disponible u ocupado.
ii) 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.
iii) 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.
12. En una Distribuidora de productos informáticos, 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 opciones:
i)
Generar árbol: Debe permitir generar un árbol de búsqueda binaria llamado
Índice, con nodos que contienen los siguientes datos: códigoProducto,
punteroProducto. Cada nodo debe generarse a partir de los datos de la lista de
productos. La lista contiene los datos código, descripción, 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.
ii) 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.
iii) Eliminar un producto: ingresar un código de producto y mostrar los datos del
producto. Eliminar el producto, sólo 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.
iv) 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.