Estructura de Datos - Estructuras no lineales

Tecnológico Nacional de México
Instituto Tecnológico Superior de Guasave
Ingeniería en Sistemas Computacionales
Estructura de Datos: AED-1026
Estructuras no lineales
Material de clase

1. Instituto Tecnológico Superior de Guasave Ingeniería en Sistemas Computacionales Estructura de Datos Unidad IV: Estructuras no Lineales Retícula ISIC-2010-224: Programa: AED-1026/2016 Itsguasave.edu.mx

2. Competencia de la Unidad Comprende y aplica estructuras no lineales para la solución de problemas. ESTRUCTURA DE DATOS

3. Estructuras NO Lineales A las estructuras de datos no lineales se les llama también estructuras de datos multi -enlazadas. Cada elemento o NODO puede estar enlazado a cualquier otro componentes. Se trata de estructuras de datos en las que cada elemento puede tener varios sucesores y/o varios predecesores. ESTRUCTURA DE DATOS

4. Árboles ESTRUCTURA DE DATOS

5. Árboles ESTRUCTURA DE DATOS

6. La estructura de un árbol se forma de  nodos  y  arcos  (línea que une dos nodos), el primero de los nodos del árbol recibe el nombre de  raíz , del cual se desprenden los nodos  interiores  y de éstos los nodos llamados  hoja , que son los nodos que se encuentran al final del árbol; todos ellos en conjunto forman un árbol. Además de comprender el concepto y la estructura de un árbol, debemos tomar en cuenta otros conceptos básicos que pueden ser útiles en el momento de construir o programar un árbol, estos conceptos los clasificaremos en tres rubros: Relación con otros nodos, Posición dentro del árbol y Tamaño del árbol ESTRUCTURA DE DATOS

7. En relación con otros nodos: Padre : es el nodo del cual se derivan otros nodos. Hijo : es el nodo que depende de otro. Hermano : es el nodo que se encuentra al lado del nodo hijo y que dependen del mismo nodo padre. En cuanto a la posición dentro del árbol: Raíz : es el primero de los nodos y el único que no contiene un padre. Hoja : es el nodo que se encuentra al final del árbol. Interior : nodos con uno o más subárboles; nodos que no son hojas. ESTRUCTURA DE DATOS

8. En relación a su tamaño: ESTRUCTURA DE DATOS

9. En relación a su tamaño: ESTRUCTURA DE DATOS

10. Un árbol binario sería un conjunto de 0 o más nodos en el cual existe un nodo raíz y cada uno de los nodos, incluido el raíz podrán tener 0, 1 o dos subárboles: Subárbol izquierdo y subárbol derecho. Cada nodo es como máximo de grado 2. ESTRUCTURA DE DATOS

11. Terminología ESTRUCTURA DE DATOS

12. ESTRUCTURA DE DATOS Terminología

13. ESTRUCTURA DE DATOS Terminología

14. ESTRUCTURA DE DATOS Terminología

15. ESTRUCTURA DE DATOS Terminología

16. ESTRUCTURA DE DATOS Terminología

17. TRABAJANDO CON ÁRBOLES BINARIOS Un árbol binario es una estructura recursiva. Cada nodo es el raíz de su propio subárbol y tiene hijos, que son raíces de árboles llamados los subárboles derecho e izquierdo del nodo, respectivamente. Un árbol binario se divide en tres subconjuntos disjuntos: ESTRUCTURA DE DATOS

18. RECORRIDO DE UN ÁRBOL BINARIO Para visualizar o consultar los datos almacenados en un árbol se necesita recorrer el árbol o visitar los nodos del mismo. Al contrario que las listas enlazadas, los árboles binarios no tienen realmente un primer valor, un segundo valor, tercer valor, etc. Se puede afirmar que el nodo raíz viene el primero, pero ¿quién viene a continuación? Existen diferentes métodos de recorrido de árbol ya que la mayoría de las aplicaciones binarias son bastante sensibles al orden en el que se visitan los nodos, de forma que será preciso elegir cuidadosamente el tipo de recorrido. ESTRUCTURA DE DATOS

19. RECORRIDO PREORDEN El recorrido preorden conlleva los siguientes pasos, en los que el nodo raíz va antes que los subárboles: Visitar el nodo raíz ( N ). Recorrer el subárbol izquierdo ( I ) en preorden . Recorrer el subárbol derecho ( D ) en preorden . Dado las características recursivas de los árboles, el algoritmo de recorrido tiene naturaleza recursiva. Primero se procesa la raíz, a continuación el subárbol izquierdo y a continuación el subárbol derecho. Para procesar el subárbol izquierdo se siguen los mismos pasos: raíz, subárbol izquierdo y subárbol derecho (proceso recursivo). Luego se hace lo mismo con el subárbol derecho. ESTRUCTURA DE DATOS

20. ESTRUCTURA DE DATOS Si utilizamos el recorrido preorden del árbol de la figura se visita primero el raíz (nodo A); a continuación, se visita el subárbol izquierdo de A, que consta de los nodos B, D y E. Dado que el subárbol es a su vez un árbol, se visitan los nodos utilizando el mismo preorden . Por consiguiente, se visita primero el nodo B, después D (izquierdo) y por último E (derecho ). A continuación, se visita subárbol derecho de A, que es un árbol que contiene los nodos C, F y G. De nuevo, siguiendo el mismo preorden , se visita primero el nodo C, a continuación F (izquierdo) y por último G (derecho).

21. Ejercicio : Realizar el recorrido en preorden del siguiente árbol binario. ESTRUCTURA DE DATOS

22. RECORRIDO ENORDEN El recorrido enorden ( inorder ) procesa primero el subárbol izquierdo, después el raíz y a continuación el subárbol derecho. El significado de en ( in ) es que la raíz se procesa entre los subárboles. Si el árbol no está vacío, el método implica los siguientes pasos: Recorrer el subárbol izquierdo ( I ) en enorden . Visitar el nodo raíz ( N ). Recorrer el subárbol derecho ( D ) en enorden . ESTRUCTURA DE DATOS

23. En el árbol de la figura ejemplo, los nodos se han numerado en el orden en que son visitados durante el recorrido enorden . El primer subárbol recorrido es el subárbol izquierdo del nodo raíz (árbol cuyo nodo contiene la letra B). Este subárbol es, a su vez, otro árbol con el nodo B como raíz, por lo que siguiendo el enorden , se visita primero D, a continuación B (nodo raíz) y por último E (derecha). Después, se visita el nodo raíz, A. Por último, se visita el subárbol derecho de A, siguiendo el enorden se visita primero F, después C (nodo raíz) y por último G. ESTRUCTURA DE DATOS

24. Ejercicio : Realizar el recorrido enorden del siguiente árbol binario. ESTRUCTURA DE DATOS

25. RECORRIDO POSTORDEN El recorrido postorden procesa el nodo raíz ( post ) después de que los subárboles izquierdo y derecho se han procesado. Se comienza situándose en la hoja más a la izquierda y se procesa. A continuación se procesa su subárbol derecho. Por último, se procesa el nodo raíz. Las etapas del algoritmo, si el árbol no está vacío, son: Recorrer el subárbol izquierdo ( I ) en postorden . Recorrer el subárbol derecho ( D ) en postorden . Visitar el nodo raíz ( N ). ESTRUCTURA DE DATOS

26. Si se utiliza el recorrido postorden del árbol ejemplo se visita primero el subárbol izquierdo de A. Este subárbol consta de los nodos B, D y E, y siguiendo el postorden , se visitará primero D (izquierdo), luego E (derecho) y, por último, B (nodo). A continuación, se visita el subárbol derecho de A que consta de los nodos C, F y G. Siguiendo el postorden para este árbol, se visita primero F (izquierdo), después G (derecho) y, por último, C (nodo). Finalmente se visita el nodo raíz A. ESTRUCTURA DE DATOS

27. Ejercicio : Realizar el recorrido postorden del siguiente árbol binario. ESTRUCTURA DE DATOS

28. El resultado para los 3 métodos es el siguiente: Preorden Postorden Enorden ESTRUCTURA DE DATOS

29. ÁRBOLES DESDE LA PROGRAMACIÓN CON MEMORIA DINÁMICA Y CLASES Para trabajar un árbol binario desde la programación es necesario crear una estructura que albergue la información y enlaces de los nodos, esto significa que nuestro árbol se trabajará por medio de memoria dinámica. Declaración la clase y variables tipo nodos: ESTRUCTURA DE DATOS

30. Estructura de la clase NODO ESTRUCTURA DE DATOS Estructura de la clase ARBOL

31. Módulo recursivo para insertar nodos en el árbol ESTRUCTURA DE DATOS

32. Recorrido Recursivo en PreOrden : ESTRUCTURA DE DATOS

33. Recorrido Recursivo en enOrden : ESTRUCTURA DE DATOS

34. Recorrido Recursivo en PostOrden : ESTRUCTURA DE DATOS

35. Ejercico : Enlazar los módulos vistos en clase en un solo programa y agregar a la rutina main () el llamado a los recorridos, preOrden , inOrden y postOrden . Entregar programa y código ya desarrollados. ESTRUCTURA DE DATOS

36. Grafos ESTRUCTURA DE DATOS

37. Un grafo G agrupa entes físico o conceptuales y las relaciones entre ellos. Por tanto, un grafo está formado por un conjunto de vértices o nodos V , que representan a los entes , y un conjunto de arcos A , que representan las relaciones entre vértices. Se representa con el par G = (V, A). La figura muestra un grafo G formado por los vértices V = {1,4,5,7,9} y el conjunto de arcos: A = {(1, 4), (4, 1), (5, 1), (1, 5), (7, 9), (9, 7), (7, 5), (5, 7), (4, 9), (9, 4)} ESTRUCTURA DE DATOS

38. Un arco o arista representa una relación entre dos nodos. Esta relación, al estar formada por dos nodos, se representa por (u, v) siendo u, v el par de nodos. El grafo es no dirigido si los arcos están formados por pares de nodos no ordenados, no apuntados; se representa con un segmento uniendo los nodos, u ⎯ v. ESTRUCTURA DE DATOS

39. Un grafo es dirigido, también denominado digrafo , si los pares de nodos que forman los arcos son ordenados; se representan con una flecha que indica la dirección de la relación, u --> v. El grafo de la sig. figura que consta de los vértices: V = {C, D, E, F, H}, y de los arcos A = {(C, D,), (D, F), (E, H), (H, E), (E, C)} forman el grafo dirigido G = {V, A} ESTRUCTURA DE DATOS ESTRUCTURA DE DATOS

40. En los modelos realizados con grafos, a veces, una relación entre dos nodos tiene asociada una magnitud , denominada factor de peso , en cuyo caso se dice que es un grafo valorado . Por ejemplo: los pueblos que forman una comarca junto a la relación entre un par de pueblos de estar unidos por un camino: esta relación tiene asociado el factor de peso, que es la distancia en kilómetros. La figura sig. muestra un grafo valorado en el que cada arco tiene asociado un peso que es la longitud entre dos nodos. ESTRUCTURA DE DATOS

41. Grado de entrada, grado de salida de un nodo El grado es una cualidad que se refiere a los nodos de un grafo. En un grafo no dirigido el grado de un nodo v , grado(v), es el número de arcos que contiene a v . En un grafo dirigido se distingue entre grado de entrada y grado de salida; grado de entrada de un nodo v , gradent (v) , es el número de arcos que llegan a v ; grado de salida de v , gradsal (v) , es el número de arcos que salen de v . ESTRUCTURA DE DATOS

42. Así, en el grafo no dirigido de la figura Comarcas, grado( Lupiana ) = 3. En el grafo dirigido de la figura Letras, gradent (E ) = 1 y el gradsal (E ) = 2. ESTRUCTURA DE DATOS

43. Camino Un camino P de longitud n desde el vértice v a v n en un grafo G , es la secuencia de n - 1 vértices v , v 1 , v 2 , ..., v n tal que ( v i , v i+1 ) Є A ( arcos ). Matemáticamente el camino se representa por P = (v , v 1 , v 2 ,..., v n ). En la sig. figura se pueden encontrar más de un camino; por ejemplo: P1 = (4, 6, 9, 7) es un camino de longitud 3. Otro de los caminos es P2 = (10, 11), que tiene de longitud 1. Por tanto, se puede afirmar que la longitud del camino es el número de arcos que lo forman. ESTRUCTURA DE DATOS

44. Un grafo no dirigido es conexo si existe un camino entre cualquier par de nodos que forman el grafo. En el caso de un grafo dirigido con esta propiedad se dice que es fuertemente conexo . Además, un grafo completo es aquél que tiene un arco para cualquier par de vértices. ESTRUCTURA DE DATOS

45. Ejercicio: Del siguiente ejemplo de grafo determine sus características de acuerdo a las definiciones ya vistas: Determine el conjunto V; Determine los arcos A; Determine si es dirigido o no dirigido Determine 3 caminos para llegar de Badajoz a Gerona y determine la longitud de cada camino. Determine el grado de los vértices Madrid, Murcia, Valladolid, Jaén, y Bilbao. ESTRUCTURA DE DATOS

46. Bibliografía Joyanes , Zahonero . Estructura de Datos en C++. McGraw Hill. Madrid, España. 2007. ISBN: 978-84-481-5645-9. ESTRUCTURA DE DATOS