Unidad III ESTRUCTURAS NO LINEALES

Definicion:

Estructura de Datos No Lineales:

 

• Se caracteriza por no existir una relación de sus elementos es decir que un elemento puede estar con cero uno o mas elementos.
• Las estructuras no lineales de datos mas general son los árboles donde no existe ninguna relación de orden Predefinida.
• Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos y tablas de contenido

Clasificación (altura, número de nodos)

 

Orden: es el número potencial de hijos que puede tener cada elemento de árbol.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.

 

Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol.

 

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.

Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodode un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar dealtura de ramas. ,

 

 

Si un grafo tiene un vértice Uo que solo contiene una diferente de Uo−U1 (a sí mismo) entonces es un árbol.

Altura = 3 (el nivel mas grande)

raíz = que no tiene padre (inicial)

padre = que tiene hijo(s)

hoja = no tiene hijo(s), tiene padre

Árbol ordenado: tiene nivel, los hijos de izquierda a derecha.

n-árbol: cuando cada padre tiene a lo más n hijos

árbol binario: cada padre tiene a lo más 2 hijos

Recursividad:

La recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una función desde la misma función. Como ejemplo útil se puede presentar el cálculo de números factoriales. Él factorial de 0 es, por definición,

Por ejemplo, para calcular fib (6), puede aplicarse la definición de manera recursiva para obtener:

Fib (6) = fib (4) + fib (5) = fib (2) + fib (3) + fib (5) = fib (0) + fib (1) + fib (3) + fib (5) = 0 + 1 fib (3) + fib (5)

 

 

Como ejemplo de cadena recursiva consideremos el siguiente grupo de definiciones:

 

•  Una expresión es un término seguido por un signo mas seguido por un término, o un término solo
• Un término es un factor seguido por un asterisco seguido por un factor, o un factor solo.
• Un factor es una letra o una expresión encerrada entre paréntesis.

 

 

Longitud de Camino Interno:

Se define la longitud de camino de nodo X como el número de arcos que se deben de recorrer  para llegar desde la raíz hasta el nodo  X. Por definición la raíz tiene longitud de camino 1, sus  descendientes directos longitud de camino 2 y así sucesivamente. Considerando la siguiente figura.

La longitud de camino interno (LCI) del árbol es la suma de las longitudes de camino de todos los  nodos del árbol. Se calcula de la siguiente fórmula:

Longitud de camino externo

Para definir la longitud de camino externo de un árbol es necesario definir los conceptos de árbol extendido y nodo especial.Un árbol extendido es aquel en el que el número de hijos de cada nodo es igual al grado del árbol. Si alguno de los nodos del  árbol no cumple con esta condición entonces debe incorporarse al  mismo tantos nodos especiales como se requiera para llegar a cumplirla.

 

 

 

 

La longitud de camino externo (LCE) de un árbol es la suma de las longitudes de camino de todos 

los nodos especiales del árbol. Se calcula de la siguiente forma:

LCE= 1 ∗ 2 + 1 ∗ 3 + 11 ∗ 4 + 12 ∗ 5 = 109