DEDA_U3_EA_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: Evidencia
Ciudad de México, Marzo del 2023
Diseño: DL-CPL
Contenido
INSTRUCCIONES	3
INTRODUCCIÓN	3
DESARROLLO DE LA ACTIVIDAD	4
CONCLUSION	5
REFERENCIAS BIBLIOGRÁFICAS	6
INSTRUCCIONES
1. Haciendo uso de la plantilla oficial de entrega de 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 los árboles, específicamente:
a. Diferencias entre los árboles y los árboles binarios.
b. Métodos disponibles para recorrer un árbol binario
i. Recorrido en preorden
ii. Recorrido en inorden
iii. Recorrido en posorden
3. Explica de forma clara, con ideas propias y solidas el siguiente planteamiento e incluye por lo menos 2 citas textuales en los contenidos.
a. ¿Cuáles son las diferencias entre los árboles y los árboles generales? (explica 4)
b. ¿En qué situaciones específicas se prioriza la implementación de un árbol binario sobre un árbol general?
c. ¿Cuál es la utilidad del recorrido de un árbol binario? 
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 permite recorrer los nodos del árbol mediante el recorrido en preorden, incluso si el árbol aún no se encuentra lleno. 
f. El programa permite recorrer los nodos del árbol mediane el recorrido en inorden, incluso si el árbol aún no se encuentra lleno. 
g. El programa permite recorrer los nodos del árbol mediante el recorrido en posorden, incluso si el árbol aún no se encuentra lleno. 
5. Crea una carpeta compartida en OneDrive de tu cuenta institucional, para colocar ahí el código fuente del programa desarrollado y genera un enlace de la carpeta para compartir, configurando los permisos para que el docente pueda acceder a su contenido, y pega el enlace en el formato plantilla de entrega, en la sección desarrollo de la actividad.
6. Redacta 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 formato de entrega de la actividad para conocer aspectos particulares del producto a entregar.
8. Envía la actividad a tu docente en línea para recibir retroalimentación mediante la herramienta Tarea.
CASO DE ESTUDIO
La aplicación debe cumplir con las siguientes características:
1. Al iniciar la aplicación se debe 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.
5. La opción 4 del menú (recorrido en inorden) 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.
6. La opción 5 del menú (recorrido en posorden) 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.
7. Al utilizar cualquiera de las tres opciones de recorrido del árbol binario, se deberá 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.
8. El recorrido del árbol debe funciona aun si el árbol aun no se encuentra lleno. Es decir, el único requisito para que esta función esté operativa es que el árbol haya sido creado.
9. La opción 6 del menú (salir) finalizará el programa.
10. El programa deberá ser escrito en lenguaje C++
11. El código fuente entregado por el estudiante deberá contener comentarios que expliquen las diversas funcionalidades que se implementan.
INTRODUCCIÓN
Se realizará una investigación acerca de las diferencias entre los árboles y los árboles binarios, así como de los métodos disponibles para recorrer un árbol binario. También se explicará la diferencia entre árboles y árboles generales, en qué situaciones es conveniente implementar un árbol binario y cuál es la utilidad del recorrido de un árbol binario. La razón por la cual se va a realizar este contenido es para profundizar en el conocimiento de una estructura de datos muy importante en programación y matemáticas. Los árboles son utilizados para representar relaciones jerárquicas entre elementos, permitiendo realizar búsquedas y ordenamientos de manera eficiente. Además, su uso no se limita a la programación, sino que también son utilizados en áreas como la biología y la teoría de grafos.
También se explicará la diferencia entre árboles y árboles generales, situaciones en las que es conveniente implementar un árbol binario y la utilidad del recorrido de un árbol binario.
DESARROLLO DE LA ACTIVIDAD
a. Diferencias entre los árboles y los árboles binarios:
Los árboles son una estructura de datos en la que un nodo raíz tiene uno o varios nodos hijos, y cada uno de estos nodos puede tener a su vez sus propios hijos. Los árboles binarios son un tipo especial de árbol en el que cada nodo puede tener un máximo de dos hijos. Esto significa que cada nodo tiene un hijo izquierdo y un hijo derecho, y que estos hijos son distintos entre sí.
b. Métodos disponibles para recorrer un árbol binario:
Existen tres métodos principales para recorrer un árbol binario:
i. Recorrido en preorden: En este método, se visita primero la raíz, luego el subárbol izquierdo y finalmente el subárbol derecho.
ii. Recorrido en inorden: En este método, se visita primero el subárbol izquierdo, luego la raíz y finalmente el subárbol derecho.
iii. Recorrido en posorden: Se visita primero el subárbol izquierdo, luego el subárbol derecho y finalmente la raíz.
c. ¿Cuáles son las diferencias entre los árboles y los árboles generales?
Los árboles y los árboles generales son estructuras de datos no lineales que se utilizan en informática y matemáticas para representar relaciones jerárquicas entre elementos. Sin embargo, hay algunas diferencias clave entre ellos:
1. En un árbol general, cada nodo puede tener un número arbitrario de hijos, mientrasque en un árbol, cada nodo puede tener como máximo un hijo padre y varios hijos hijos.
2. En un árbol general, no hay restricciones sobre la ubicación de los nodos, mientras que en un árbol, los nodos se organizan de manera jerárquica.
3. En un árbol general, no hay una raíz definida, mientras que en un árbol, hay un nodo raíz que es el nodo superior del árbol.
4. En un árbol general, no hay restricciones en el orden en que se visitan los nodos, mientras que en un árbol, los nodos se visitan en un orden específico, como en un recorrido en preorden, postorden o inorden.
Un ejemplo de árbol general es un árbol de directorios en un sistema de archivos, donde cada carpeta puede contener cualquier cantidad de subcarpetas y archivos.
Como dijo el autor Mark Allen Weiss en su libro "Estructuras de datos y algoritmos en Java": "Un árbol es una estructura de datos en la que cada elemento se llama nodo y cada nodo puede tener cero o más nodos secundarios".
d. ¿En qué situaciones específicas se prioriza la implementación de un árbol binario sobre un árbol general?
La elección entre implementar un árbol binario o un árbol general dependerá en gran medida del problema que se esté tratando de resolver. Sin embargo, hay algunas situaciones específicas en las que se puede priorizar la implementación de un árbol binario sobre un árbol general. Por ejemplo:
Cuando la estructura de datos es necesaria para representar una relación de orden, como en el caso de un árbol de búsqueda binario.
Cuando se desea una implementación más eficiente de ciertos algoritmos, como el ordenamiento rápido (quicksort) o la búsqueda binaria, que requieren una estructura de datos ordenada y jerárquica.
e. ¿Cuál es la utilidad del recorrido de un árbol binario?
El recorrido de un árbol binario es una operación fundamental que se utiliza para visitar cada uno de los nodos de un árbol en un orden específico. Esto permite realizar diversas tareas, como buscar un valor específico en el árbol, imprimir los nodos en un orden determinado, o evaluar una expresión aritmética o lógica.
Según Shaffer (2012), "el recorrido de un árbol binario es una operación fundamental en la que cada nodo se visita exactamente una vez, y se realiza en un orden específico determinado por el tipo de recorrido que se utilice" (p. 272). Además, Weiss (2014) menciona que "el recorrido de árboles binarios es una tarea esencial en la mayoría de las aplicaciones de árboles, ya que permite procesar de forma eficiente la información almacenada en ellos" (p. 473).
1. Al iniciar la aplicación se debe 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.
5. La opción 4 del menú (recorrido en inorden) 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.
6. La opción 5 del menú (recorrido en posorden) 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.
7. Al utilizar cualquiera de las tres opciones de recorrido del árbol binario, se deberá 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.
8. El recorrido del árbol debe funciona aun si el árbol aun no se encuentra lleno. Es decir, el único requisito para que esta función esté operativa es que el árbol haya sido creado.
9. La opción 6 del menú (salir) finalizará el programa.
10. El programa deberá ser escrito en lenguaje C++
11. 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/ElUAxMyzk3JOt4CYVXxVKcIBFhAPJmGbJjxFX1oQlTB6Xg?e=yKLyti
CONCLUSION
Se concluye que en esta actividad pude comprender mas acerca de los árboles, específicamente en las diferencias entre los árboles y los árboles binarios, así como en los métodos disponibles para recorrer un árbol binario y su importancia e implementación. Y gracias a la actividad del caso de estudio en el cual se debía crear una aplicación en C++ que permitiera crear un árbol binario de búsqueda, insertar nodos en él, y recorrer sus nodos mediante los recorridos en preorden, inorden y posorden. De igual forma me permitió adquirir nuevos conocimientos en cuanto a la estructura y funcionalidad de los árboles binarios de búsqueda, así como en la programación de aplicaciones que involucren esta estructura de datos y de igual forma se aprendió acerca de los diferentes métodos para recorrer los nodos de un árbol binario y su importancia en la solución de problemas específicos.
Considero que es muy importante el trabajo practico de desarrollo de la aplicación ya que permite lograr comprender y entender la lógica de las estructuras y cómo funcionan con base en la teoría estudiada, personalmente creo que este tema puede ser clave en mi carrera como ingeniero en desarrollador de software, por lo que de forma general, la actividad resultó en una experiencia valiosa y útil.
REFERENCIAS BIBLIOGRÁFICAS
Shaffer, C. A. (2012). Data structures and algorithm analysis in Java (3rd ed.). Dover Publications.
Weiss, M. A. (2014). Data structures and algorithm analysis in Java (3rd ed.). Pearson.