Vista previa del material en texto
ALGORITMOS Y ESTRUCTURAS DE DATOS UNIDAD VIII : ESTRUCTURAS DE DATOS NO LINEALES. CONTENIDO: Estructuras de datos no lineales: Grafos y Árboles. Definiciones. Ciclos. Árboles binarios. No lineales Las estructuras dinámicas lineales de datos tienen grandes ventajas, sin embargo tienen un punto débil, son listas secuenciales, están dispuestas de modo que es necesario moverse a través de ellas una posición a la vez. Las estructuras de datos no lineales tienen la característica que cada elemento puede tener diferentes siguientes elementos. Árbol Es una estructura de datos muy utilizada porque se adapta a la representación natural de informaciones homogéneas organizadas y de una gran comodidad y rapidez de manipulación. Se usan para representar datos con una relación jerárquica entre sus elementos, como son árboles genealógicos, organigramas, llamadas a subprogramas, entre otros. Características Cada elemento del árbol se denomina nodo. Existe un nodo especial: nodo raíz. Los nodos sin ramificaciones se llaman terminal u hoja. Cada nodo apunta a uno o más nodos. A un nodo le apunto sólo un nodo. Grado: número de descendientes directos de un nodo. Representación Ejemplo: organigrama Árboles binarios Los árboles de grado 2 representan una de las estructuras más importantes conocida como árboles binarios. En los árboles binarios todos sus nodos excepto los del último nivel, tienen dos hijos: el subárbol izquierdo y el subárbol derecho. Grafos Si en los árboles eliminamos la restricción de que un nodo sólo puede ser apuntado por un solo nodo obtenemos un grafo. Un grafo tiene una gran número de aplicaciones, por ej.: red de caminos, red de enlaces aéreos, entre otros. Representación Ejemplo: conexiones aéreas Ciclo Un ciclo es una trayectoria, secuencia de una o más aristas que conectan a 2 nodos, que se dan las siguientes condiciones: Ninguna arista puede aparecer más de una vez en una secuencia El nodo inicial de la trayectoria es el mismo que el nodo final. Estructura de ciclo
