Deda_u3_a1_esjm.docx

Universidad Nacional Abierta y a Distancia de México

Asignatura: Estructura de Datos

Unidad 1: Estructura de Datos

Actividad: 1

Relación entre algoritmos y estructuras de datos.

Alumno:

Esteban Jiménez Martínez

Matricula: ES172006340 Grupo: DS-DEDA-1901-B1-001 FECHA: 27-01-.2019

Actividades para el foro

[1] Dado el siguiente árbol indicar los recorridos inorder, preorder y postorder, etiquetando cada nodo recorrido con un número.

Preorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay que Realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz: 1. Visite la raíz 2. Atraviese el sub-árbol izquierdo 3. Atraviese el sub-árbol derecho

Recorrido ;

0697812534

Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo: 1. Atraviese el sub-árbol izquierdo 2. Visite la raíz 3. Atraviese el sub-árbol derecho

Recorrido: 9678052341

Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo: 1. Atraviese el sub-árbol izquierdo 2. Atraviese el sub-árbol derecho 3. Visite la raíz

Recorrido: 9876543210

[2] Comentar las principales realizaciones que existen para un árbol: estática y dinámica/TAD indicando sus ventajas y desventajas, estructura (TAD) árbol. Un árbol es una estructura de datos homogénea, dinámica y no lineal, en la que cada nodo (elemento) puede tener varios nodos posteriores, pero sólo puede tener un nodo anterior. Estructura Estática A.-)El tamaño ocupado en memoria se define con anterioridad a la ejecución del programa. B.-)Su dimensión es fija y no puede modificarse durante la ejecución del programa C.-)la memoria queda reservada desde el inicio aunque no se utilice en la ejecución del programa. Estructura Dinámica A.- )Puede crecer o decrecer durante la ejecución dependiendo de las necesidades de la aplicación. B.-)No tienen limitaciones en su tamaño, salvo la memoria disponible en la computadora.

[3] Investigar tres aplicaciones de los arboles dentro del software y la computación, distintas a las mencionadas en este foro. (Ejemplo: Arboles sintácticos de expresiones formales) a.- Pueden usarse para para representar la información en una estructura jerárquica b.- Los árboles pueden procesarse en forma recursiva y son muy adaptables a pruebas matemáticas. c.- LA estructura jerárquica es muy usada en la práctica. Por ejemplo, los libros son a menudo organizados como una sucesión de capítulos cada uno de los cuales son una sucesión de secciones que puede tener subdivisiones, y así sucesivamente.

[4] Proporcionar un ejemplo de un árbol binario lleno, árbol binario de búsqueda, un árbol binario completo, un árbol de expresiones, un árbol balanceado. Árbol binario lleno Un árbol binario completo que contiene 2n nodos a nivel n es un árbol lleno. Un árbol lleno es un árbol binario que tiene el máximo número de entradas para su altura. Esto sucede cuando el último nivel está lleno.

Árbol Binario de Búsqueda Un árbol binario de búsqueda es aquel en que, dado un nodo, todos los datos del subárbol izquierdo son menores que los datos de ese nodo, mientras que todos los datos del subárbol derecho son mayores que sus propios datos.

Se denominan árboles binarios de búsqueda, debido a que se puede buscar en ellos un término utilizando un algoritmo de búsqueda binaria similar al empleado en arrays.

Árbol Binario completo Un árbol binario completo de profundidad n es un árbol en el que para cada nivel, del 0 al nivel n-1, tiene un conjunto lleno de nodos, y todos los nodos hoja a nivel n ocupan las posiciones más a la izquierda del árbol.

Árbol de Expresiones Una aplicación muy importante de los árboles binarios son los árboles de expresiones. Una expresión es una secuencia de tokens (componentes de léxicos que siguen unas reglas establecidas). Un token puede ser un operando o bien un operador.

Un árbol de expresión es un árbol binario con las siguientes propiedades: 1. Cada hoja es un operando. 2. Los nodos raíz y los nodos internos son operadores. 3. Los subárboles son subexpresiones cuyo nodo raíz es un operador.

Árbol Balanceado Un árbol binario se encuentra balanceado si la diferencia en la altura de los dos subárboles de cualquier nodo en el árbol es cero o uno.

[5] ¿Es un camino un árbol? ¿Cómo reconoces un árbol? es decir ¿Qué cualidades lo caracterizan como gráfica (matemáticas discretas)? Un Árbol es un camino a través del cual se hacen diferentes tipos de recorridos inorder, preorder y postorder para busqueda de datos. Los arboles tienen características muy específicas, hablando de árboles binarios tienen un nodo raíz, un sub árbol camino izquierdo y un sub árbol derecho con elementos como los que se especifican en la relación siguiente. Un árbol es una estructura de datos homogénea, dinámica y no lineal, en la que cada nodo (elemento) puede tener varios nodos posteriores, pero sólo puede tener un nodo anterior.

Estructura de un Árbol Nodos: Se le llama Nodo a cada elemento que contiene un Árbol. Nodo Raíz: Se refiere al primer nodo de un Árbol, Solo un nodo del Árbol puede ser la Raíz. Nodo Padre: Se utiliza este término para llamar a todos aquellos nodos que tiene al menos un hijo. Nodo Hijo: Los hijos son todos aquellos nodos que tiene un padre.

Nodo Hermano: Los nodos hermanos son aquellos nodos que comparte a un mismo padre en común dentro de la estructura. Nodo Hoja: Son todos aquellos nodos que no tienen hijos, los cuales siempre se encuentran en los extremos de la estructura. Nodo Rama: Estos son todos aquellos nodos que no son la raíz y que además tiene al menos un hijo.

Referencias

Aguilar, L. J. (2007). Fundamentos de Programacion, Algoritmos, estructuras de datos y objetos. España: McGrowHill. Quetglás, G. M. (1995). Fundamentos de Informatica y Proframacion. España. Tamassia, G. (2010). Estructura de datos y algoritmos. CECSA. UnAMD. (2018). Unidad 3 Almacenamiento. Mexico: UnADM.