DEDA_U3_A3_ALMM

Vista previa del material en texto

Universidad Abierta y a Distancia
de México
División de Ciencias Exactas, Ingeniería y Tecnología
Desarrollo de software
Semestre: 2023-1
Asignatura: Estructura de datos
Unidad de aprendizaje: 3
Actividad: 3
Ciudad de México, Marzo del 2023
Diseño: DL-CPL
Contenido
INSTRUCCIONES	3
CASO DE ESTUDIO	4
INTRODUCCIÓN	13
DESARROLLO DE LA ACTIVIDAD	14
CARPETA	16
CONCLUSION	16
REFERENCIAS BIBLIOGRÁFICAS	17
INSTRUCCIONES
1. Haciendo uso de la plantilla de entrega actividades que nuestra universidad te proporcionó, redacta la introducción en un mínimo de 100 y máximo 150 palabras de propia autoría, describiendo la finalidad del contenido a realizar (¿Qué se va a realizar?, ¿Para qué se va a realizar?, ¿Cómo se va a realizar?) 
2. Investiga en un mínimo de tres fuentes de información confiables (Google Académico, Mendeley, Zotero, Redalyc, LatinIndex) acerca de las siguientes operaciones a realizar en un árbol binario:
a. 
	
	
	
b. Operaciones
c. Creación 
d. Recorrido 
e. Búsqueda
f. Inserción
3. 
4. Examina el caso de estudio y crea en el lenguaje C++ la aplicación solicitada. Para que el programa sea funcional a las siguientes especificaciones: 
a. El programa muestra el menú solicitado para acceder a las distintas operaciones de un árbol binario. 
b. El programa crea un nuevo árbol binario a partir de una raíz dada por el usuario, previa validación de que el elemento raíz cumple con los requisitos planteados en el caso de estudio. 
c. El programa permite insertar hasta un máximo de 10 elementos al árbol binario y estos son números enteros no repetidos entre el 1 y el 25.
d. Los elementos insertados, se organizan dentro de la estructura de acuerdo con las reglas de los árboles binarios de búsqueda. 
e. El programa imprime en pantalla los elementos que integran el árbol binario aún si el árbol no se encuentra lleno.
f. Los elementos impresos en pantalla durante el recorrido del árbol se organizarán siguiendo el recorrido en preorden. 
g. El programa permite realizar búsquedas dentro del árbol indicando si el elemento buscado se encuentra o no dentro del árbol.
h. El programa permite eliminar un nodo sin incumplir los principios que definen un árbol binario de búsqueda.
5. Crea una carpeta compartida en OneDrive de tu cuenta institucional, coloca ahí el archivo fuente del programa diseñado y genera el enlace que dé acceso a la carpeta, configurando los permisos necesarios para que tu docente pueda acceder a su contenido. Coloca el enlace de la carpeta compartida en la sección de desarrollo, dentro del formato de entrega (plantilla) de actividades. 
6. Describe una conclusión (entre un mínimo de 150 y máximo 200 palabras de propia autoría), donde expliques cuáles fueron los aprendizajes adquiridos, las experiencias, y la importancia que representó el desarrollo de los contenidos de esta actividad
7. Consulta el instrumento de evaluación y el formato de entrega de la actividad para conocer aspectos particulares del producto a entregar.
CASO DE ESTUDIO
Se desea crear una aplicación que implemente las principales operaciones de un árbol binario: creación, inserción, recorrido, búsqueda y borrado.
La aplicación debe cumplir con las siguientes características:
1. Al iniciar la aplicación deberá mostrar el siguiente menú:
2. La opción 1 del menú (Crear árbol) deberá inicializar la raíz del árbol con el valor que ingrese el usuario.
a. La raíz del árbol puede ser un numero entero entre el 1 y el 25.
3. La opción 2 del menú (Insertar valor) deberá solicitar el valor a ingresar para posteriormente insertarlo en donde corresponde en el árbol binario de búsqueda.}
a. El valor no puede ser un igual al valor de la raíz o alguno otro ingresado previamente.
b. El valor por insertar debe ser un numero entero entre el 1 y el 25
c. Se permitirá insertar hasta un máximo de 10 nodos en el árbol, sin contar la raíz dentro de esos 10 nodos
d. Al insertar un nuevo nodo, el programa deberá imprimir un mensaje de confirmación en el que además, indique quien es el padre del nodo recién insertado.
e. Una vez que se hayan insertado 10 valores, ya no se permitirán nuevas inserciones.
4. La opción 3 del menú (recorrido en preorden) realizará un recorrido a través del árbol binario creado a partir de los valores insertados y los imprimirá en pantalla separados por una coma.
a. Al utilizar esta opción del menú se validará que el árbol se haya creado previamente. En caso de que el árbol aún no se haya creado, se indicará a través de un mensaje impreso en pantalla.
b. El recorrido del árbol debe funcionar aun si el árbol aún no se encuentra lleno. Es decir, el único requisito para que esta función esté operativa es que el árbol haya sido creado.
5. La opción 4 del menú (búsqueda de un elemento) solicitará el valor que se desea buscar y el programa deberá indicar si se encuentra o no dentro del árbol.
6. La opción 5 del menú (borrar nodo) debe eliminar un elemento del árbol.
a. El programa deberá solicitar el elemento que se desea eliminar.
b. Al eliminar un nodo, se deberán respetar los principios que rigen los árboles binarios de búsqueda, es decir, realizar las acciones pertinentes si:
i. El elemento a borrar es una hoja (terminal).
ii. El elemento a borrar tiene un solo descendiente.
iii. El elemento a borrar tiene dos descendientes.
c. Si el elemento que se desea eliminar no se encuentra en el árbol, el programa deberá imprimir un mensaje de salida en el cual se indique al usuario que el elemento no ha sido encontrado.
d. Una vez que un nodo se haya eliminado del árbol, se deberá mostrar un mensaje de confirmación y se imprimirá en pantalla la estructura del árbol utilizando el método de recorrido en preorden, con los elementos separados por comas (,).
7. La opción 6 del menú (salir) finalizará el programa.
8. El programa deberá ser escrito en lenguaje C++
9. El código fuente entregado por el estudiante deberá contener comentarios que expliquen las diversas funcionalidades que se implementan.
INTRODUCCIÓN
En esta actividad se desarrollará una aplicación en lenguaje C++ que permita la implementación de las operaciones básicas en un árbol binario: creación, inserción, recorrido, búsqueda y borrado. La aplicación debe cumplir con las especificaciones detalladas en el caso de estudio, que establecen la creación de un menú con las opciones mencionadas, validaciones en los valores ingresados y el número máximo de nodos permitidos, así como la impresión de los elementos del árbol en preorden.
En primer lugar, se realizará una investigación en al menos tres fuentes confiables sobre las operaciones de creación, recorrido, búsqueda, inserción y eliminación de nodos en un árbol binario. Posteriormente, se examinará el caso de estudio para implementar la aplicación en lenguaje C++.
DESARROLLO DE LA ACTIVIDAD
1. Al iniciar la aplicación deberá mostrar el siguiente menú:
2. La opción 1 del menú (Crear árbol) deberá inicializar la raíz del árbol con el valor que ingrese el usuario.
a. La raíz del árbol puede ser un numero entero entre el 1 y el 25.
3. La opción 2 del menú (Insertar valor) deberá solicitar el valor a ingresar para posteriormente insertarlo en donde corresponde en el árbol binario de búsqueda.}
a. El valor no puede ser un igual al valor de la raíz o alguno otro ingresado previamente.
b. El valor por insertar debe ser un numero entero entre el 1 y el 25
c. Se permitirá insertar hasta un máximo de 10 nodos en el árbol, sin contar la raíz dentro de esos 10 nodos
d. Al insertar un nuevo nodo, el programa deberá imprimir un mensaje de confirmación en el que además, indique quien es el padre del nodo recién insertado.
e. Una vez que se hayan insertado 10 valores, ya no se permitirán nuevas inserciones.
4. La opción 3 del menú (recorrido en preorden) realizará un recorrido a través del árbol binario creado a partir de los valores insertados y los imprimirá en pantalla separados por una coma.
a. Al utilizar esta opción del menú se validará que el árbol se haya creado previamente. En caso deque el árbol aún no se haya creado, se indicará a través de un mensaje impreso en pantalla.
b. El recorrido del árbol debe funcionar aun si el árbol aún no se encuentra lleno. Es decir, el único requisito para que esta función esté operativa es que el árbol haya sido creado.
5. La opción 4 del menú (búsqueda de un elemento) solicitará el valor que se desea buscar y el programa deberá indicar si se encuentra o no dentro del árbol.
6. La opción 5 del menú (borrar nodo) debe eliminar un elemento del árbol.
a. El programa deberá solicitar el elemento que se desea eliminar.
b. Al eliminar un nodo, se deberán respetar los principios que rigen los árboles binarios de búsqueda, es decir, realizar las acciones pertinentes si:
i. El elemento a borrar es una hoja (terminal).
ii. El elemento a borrar tiene un solo descendiente.
iii. El elemento a borrar tiene dos descendientes.
c. Si el elemento que se desea eliminar no se encuentra en el árbol, el programa deberá imprimir un mensaje de salida en el cual se indique al usuario que el elemento no ha sido encontrado.
d. Una vez que un nodo se haya eliminado del árbol, se deberá mostrar un mensaje de confirmación y se imprimirá en pantalla la estructura del árbol utilizando el método de recorrido en preorden, con los elementos separados por comas (,).
7. La opción 6 del menú (salir) finalizará el programa.
8. El programa deberá ser escrito en lenguaje C++
9. El código fuente entregado por el estudiante deberá contener comentarios que expliquen las diversas funcionalidades que se implementan.
CARPETA
https://unadmex-my.sharepoint.com/:f:/g/personal/medinalejandro_nube_unadmexico_mx/Eu89GACxdwpBtLDK3LdCHEMBy7YrhuAxhNrj-XVbQ6T_UA?e=922rcc
CONCLUSION
En esta actividad de programación de árboles binarios, el proceso más complicado es la implementación de las operaciones de búsqueda y eliminación, ya que se deben mantener las propiedades de un árbol binario de búsqueda en todo momento. La búsqueda requiere recorrer el árbol de manera ordenada para encontrar un valor específico, y la eliminación implica reorganizar el árbol para asegurarse de que se mantengan las propiedades de búsqueda.
La aplicación de los conocimientos teóricos de los árboles binarios en la programación también es un desafío importante. Es necesario comprender cómo funcionan los árboles binarios y cómo se aplican las reglas de búsqueda para implementar la lógica necesaria en la programación del árbol.
En general, esta actividad es una excelente oportunidad para adquirir conocimientos prácticos en programación y comprender la aplicación de los árboles binarios. Es importante realizar una investigación adecuada y dedicar tiempo a la programación para lograr una implementación funcional y exitosa de las operaciones requeridas.
REFERENCIAS BIBLIOGRÁFICAS
Weiss, M. A. (2014). Data structures and algorithm analysis in C++. Pearson Education India.
Drozdek, A. (2019). Data structures and algorithms in C++. Cengage Learning.
Sedgewick, R., & Wayne, K. (2011). Algorithms (4th Edition). Addison-Wesley Professional.