Estructuras Dinámicas No Lineales

ESTRUCTURAS DINÁMICAS NO LINEALES
Son aquellas que ocupan bloques de memoria no continuos/lineales. Para lidiar con el problema de la fragmentación y, sobre todo del crecimiento dinámico. Los bloques deben estar enlazados unos con otros para poder “navegar” por la estructura, es decir, tener acceso a otro(s) dato(s) a partir de l actual.
1. Arboles
2.1 Definición
Un árbol es unaestructura de datos ramificada (no lineal) que puede representarse como un conjunto de nodos enlazados entre sí por medio de ramas. La información contenida en un nodo puede ser de cualquier tipo simple o estructura de datos.

Una definición formal es la siguiente:
Un árbol es una estructura de datos base que cumple una de estas dos condiciones:
* Es una estructura vacía, o
* Es un nodode tipo base que tiene de 0 a N subárboles disjuntos entre sí.

2.2 Idea principal
Al nodo base, que debe ser único, se le denomina raíz y se establece el convenio de representarlo gráficamente en la parte superior.
En un árbol se representa una relación jerárquica a partir del nodo raíz en sentido vertical descendente, definiendo niveles 1. El nivel del nodo raíz es 1.
Desde la raíz sepuede llegar a cualquier nodo progresando por las ramas y atravesando los sucesivos niveles estableciendo así un camino. En la figura 4.1. el nodo 7 está a nivel 3 y la secuencia de nodos 4, 8 y 11 constituye un (sub)camino.
Se dice que un nodo es antecesor de otro cuando ambos forman parte de un camino y el primero se encuentra en un nivel superior (numeración más baja) al del segundo(numeración más alta). En el ejemplo anterior el nodo 4 es antecesor del 11. Por el contrario, el nodo 11 es descendiente del 4.
La relación entre dos nodos separados de forma inmediata por una rama se denomina padre/hijo. En el ejemplo de la figura 4.1., el nodo 5 es hijo del nodo 2 y, recíprocamente, el nodo 2 es padre del nodo 5. En un árbol un padre puede tener varios hijos pero un hijo solo puedetener un padre.
Se denomina grado al número de hijos de un nodo.
Se dice que un nodo es hoja cuando no tiene descendientes (grado 0).
2.3 Características
Se establecen los siguientes atributos para un árbol:
* Altura / profundidad / nivel: La mayor altura / profundidad / nivel de sus nodos.
* Amplitud / Anchura: El número de nodos del nivel más poblado
* Grado: el mayor de losgrados de los nodos. En el ejemplo, 3 (nodos 1 y 4).
Finalmente, indicar que se dice que un árbol es completo cuando todos sus nodos (excepto las hojas) tienen el mismo grado y los diferentes niveles están poblados por completo.
2.4 Aplicaciones
Un ejemplo de estructura en árbol es el sistema de directorios y ficheros de un sistema operativo. Aunque en este caso se trata de árboles connodos de dos tipos, nodos directorio y nodos fichero, podríamos considerar que los nodos hoja son ficheros y los nodos rama son directorios.
Otro ejemplo podría ser la tabla de contenido de un libro, por ejemplo de este mismo curso, dividido en capítulos, y cada uno de ellos en subcapítulos. Aunque el libro sea algo lineal, como una lista, en el que cada capítulo sigue al anterior, también esposible acceder a cualquier punto de él a través de la tabla de contenido.
También se suelen organizar en forma de árbol los organigramas de mando en empresas o en el ejército, y los árboles genealógicos.
2.5 Implementación

2.6 Ventajas
Son muy útiles para la búsqueda y recuperación de información.
2.7 Desventajas

2. Grafos
3.8 Definición
Un grafo es unaestructura de datos, en concreto un tipo abstracto de datos (TAD), que consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos.
Informalmente se define como G = (V, E), siendo los elementos de V los vértices, y los elementos de E, las aristas (edges en inglés). Formalmente, un grafo, G, se define como un par ordenado, G =...