Estructura De Datos No Lineales

ESTRUCTURAS DE DATOS NO LINEALES

M.E. HORACIO GARCIA ALDAPE

KARLA LOURDES HERNANDEZ NUÑEZ

Ing. Sistemas Computacionales

ESTRUCTURAS DE DATOS 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.

o B

o B+

o B*

o R

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.

Operaciones Básicas sobre árboles binarios.

Las operaciones que se pueden aplicar a un árbol binario son las siguientes:

- Creación de un árbol

- Inserción de un nodo nuevo.

- Eliminación de un nodo.

- Recorrido del árbol.

- Balanceo del árbol.

CREACIÓN

Un árbol se forma de una serie de nodos y un nodo se integra de una serie de campos, para este caso, el nodo de un árbol binario debe estar integrado por los siguientes campos:

- Padre

- Dato

- Izquierda

- Derecha

Donde los campos padre, izquierdo y derecho son los que permiten la relación con otros nodos dentro del árbol y el campo de dato es donde se almacena la información.

Otra estructura que puede tener un nodo para un árbol binario es contar con solo tres de los campos antes mencionados (dato, izquierdo y derecho), dicha estructura se representa de la siguiente manera:

- Dato

- Izquierda

- Derecha

La única diferencia entre una estructura y la otra, es que en la primera se puede recorrer el árbol de arriba hacia abajo y de abajo hacia arriba; en la segunda solo se puede recorrer de arriba hacia abajo.

Además debe tomar en cuenta que cada nodo es un objeto creado a partir de una clase auto-referenciada y dicha clase debe contener los campos antes mencionados.

Ejercicio. Construir una clase que permita crear objetos que se comporten como un nodo de un árbol.

public class NodoB

{

Object elemento;

NodoB padre, izquierdo, derecho;

//métodos

}

INSERCIÓN

La operación

...