Estructuras No Lineales

Estructuras de Datos: presentación en PowerPoint sobre Estructuras No
Lineales
Estructuras no lineales
Concepto de árbol
Un árbol es una estructura de datos homogénea, dinámica y no lineal, en la que
cada nodo (elemento) puede tener varios nodos posteriores, pero sólo puede tener
un nodo anterior.
Un árbol es dinámico porque su estructura puede cambiar durante la ejecución de

un programa. Y no lineal, ya que cada nodo del árbol puede contener varios nodos
que dependan de él.
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
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, es un nodo que no es raíz ni hijo y se encuentre ellos.
En relación a su tamaño:
-Orden, es el número potencial de nodos hijos que tiene un nodo padre (orden 2).
-Grado, es el número máximo de hijos que tiene un nodo (grado 2).
-Nivel, es el número de arcos que deben ser recorridos para llegar a un
determinado nodo más uno (nivel 3).
-Altura, es el número de niveles que deben pasar para llegar al final del árbol o de
la ramificación (altura 3).
-Peso, es el número de nodos del árbol sin contar la raíz (peso 6).
-Camino, es la serie de nodos que tienes que pasar para llegar hasta un nodo.
-Longitud de camino, es el número de arcos más uno que debe cruzar para llegar
a un nodo.
-Rama, es el camino que se forma desde el nodo raíz hasta un nodo hoja.
Clasificación de árboles.
Los árboles se clasifican de la siguiente manera:
-Árboles Binarios
o Distintos
o Similares
o Equivalentes
o Equilibrado
o Completo
Árboles Multicaminos
oB
o B+
o B*
oR
o 2-4
Un árbol binario es una estructura de datos homogénea, dinámica y no lineal en

donde a cada nodo le pueden seguir como máximo dos nodos hijos (que pueden
estar vacíos), y cada hijo se designa ya sea como hijo izquierdo o como hijo
derecho.
Un árbol binario es distinto cuando su estructura es diferente a la de otros árboles

binarios.
Un árbol binario es similar cuando su estructura es idéntica a la de otros árboles

binarios, pero la información que guardan los nodos es diferente entre sí.
Un árbol binario es equivalente cuando su estructura e información de sus nodos
es idéntica a la de otros árboles binarios.
Un árbol binario es equilibrado es aquel que todos sus nodos cumplen con la
propiedad:
altura (subárbol izquierdo) – altura (subárbol derecho) <= 1
Ejemplo. Si usamos los árboles anteriores para determinar si son o no

equilibrados.
El primero tiene una altura izquierda de 2 y derecha 1, 2-1 <= 1, la condición es

verdadera, por lo tanto es un árbol equilibrado.
El segundo tiene una altura izquierda de 2 y derecha 0, 2-0 <= 1, la condición es

falsa, por lo tanto es un árbol no equilibrado.
Un árbol binario es completo cuando todos sus nodos excepto los del último nivel,
tienen dos hijos y todas las hojas están en el mismo nivel. Para calcular el número
de nodos de un árbol completo se aplica la fórmula:
Número de nodos = 2altura - 1
Ejemplo. La altura de este árbol anterior es 3, aplicando la fórmula del número de

nodos seria.
Número de nodos = 23 – 1 = 8 – 1 = 7
Un árbol multicamino es una estructura de datos homogénea, dinámica y no lineal,
en donde a cada nodo le pueden seguir una cantidad n de nodos hijos, y cada hijo
se designa por el número de hijo que le corresponde.

Estructuras No Lineales

Cargado por

Copyright:

Formatos disponibles

Estructuras No Lineales

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Estructuras No Lineales

Cargado por

Copyright:

Formatos disponibles

Estructuras de Datos: presentación en PowerPoint sobre Estructuras No

Un árbol es dinámico porque su estructura puede cambiar durante la ejecución de

En relación con otros nodos:

En cuanto a la posición dentro del árbol:

Un árbol binario es una estructura de datos homogénea, dinámica y no lineal en

Un árbol binario es distinto cuando su estructura es diferente a la de otros árboles

Un árbol binario es similar cuando su estructura es idéntica a la de otros árboles

altura (subárbol izquierdo) – altura (subárbol derecho) <= 1

Ejemplo. Si usamos los árboles anteriores para determinar si son o no

El primero tiene una altura izquierda de 2 y derecha 1, 2-1 <= 1, la condición es

El segundo tiene una altura izquierda de 2 y derecha 0, 2-0 <= 1, la condición es

Número de nodos = 2altura - 1

Ejemplo. La altura de este árbol anterior es 3, aplicando la fórmula del número de

También podría gustarte