Estructuras no lineales

Estructuras No Lineales - Presentation Transcript
1. Estructuras no lineales Autor: Angélica Nicolás González anicolas_gonzalez@hotmail.com
2. 4.1 Árboles. 4.1.1 Definición. 4.1.2 Representación en memoria de árboles. 4.1.2.1 Árboles generales. 4.1.2.2 Árboles binarios. 4.1.3 Recorridos en un árbol binario. 4.1.3.1 Preorden. 4.1.3.2 Inorden. 4.1.3.3 Postorden. 4.1.4 Balanceo de árbolesbinarios. 4.1.5 Clases para la implementación de árboles. 4.2 Grafos. 4.2.1 Definición. 4.2.2 Tipos de grafos. 4.2.3 Representación de grafos en memoria. 4.2.4 Clases para la implementación de grafos.
3. Definición
4. Árbol
o Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos.
o También se suele dar una definición recursiva: un árbol es una estructura encompuesta por un dato y varios árboles.
o Esto son definiciones simples. Pero las características que implican no lo son tanto.
5. * Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'. * Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de'B', 'C' y 'D'.
6. En cuanto a la posición dentro del árbol:
o Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'.
o Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y'O'.
o Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'.
7.
o Un árbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama árbol completo .
8. características delárbol, en relación a su tamaño
o Orden : es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos , si puede apuntar a tres será de orden tres , etc.
o Grado : el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos.
9.
o Nivel : se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3.
oAltura : la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc.
10. Árboles generales
o Intuitivamente el concepto deárbol implica una estructura en la que los datos se organizan de modo que los elementos de información están relacionados entre si a través de ramas. El árbol genealógico es el ejemplo típico más representativo del concepto de árbol general.
11. Árboles binarios
o Es un árbol en el que ningún nodo puede tener mas de dos subárboles. En un árbol binario, cada nodo puede tener cero, uno o doshijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.
12. Operaciones en árboles binarios
o Determinar su altura
o Determinar su número de elementos
o Hacer una copia
o Visualizar el árbol binario en pantalla o en impresora
o Determinar si dos árboles binarios son idénticos
o Borrar (eliminar el árbol)
o Si es un árbol...