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 de inserción permite agregar un nuevo nodo hoja al árbol, pero antes de agregarlo, debemos tomar en cuenta como se hace el acomodo u organización de los nodos dentro de la estructura del árbol. El primer nodo que entra en el árbol se le conoce como nodo raíz, del cual se desprendes los nodos intermedio y hojas.

El segundo elemento que entra en el árbol, después del nodo raíz, tiene dos opciones para su inserción dentro de la estructura, el lado izquierdo o el lado derecho del árbol, para determinar por cuál lado debe entrar el segundo nodo tenemos que determinar el valor del campo dato del nuevo nodo, si el dato es menor que el nodo actual, el nuevo nodo se inserta por el lado izquierdo, o si el dato es mayor que el nodo actual, el nuevo nodo se inserta por el lado derecho. De esta forma la estructura del árbol organiza los nodos para un rápido acceso y búsqueda de un elemento.

Algo más que debe contemplar después elegir el camino por donde se insertara el nuevo nodo, es, si existe un espacio libre para la inserción del nuevo nodo, es decir, si el nodo actual no contiene hojas, el nuevo nodo se puede insertar, en caso contrario debe continuar la búsqueda de un lugar disponible dentro del árbol.

Ejemplo. Si tenemos un árbol con un nodo raíz con el dato 10 y queremos insertar seis nodos más con los datos 20, 5, 8, 1, 15 y 30 el árbol se estructuraría de la siguiente manera.

Ejercicio. Crear un árbol con los siguientes datos: H, G, A, M, R, O, Z, Y, Ñ, y L, tome en cuenta el ordenamiento de los nodos según lo visto anteriormente.

Ejercicio. Crear un árbol con su nombre completo todo escrito en minúsculas, eliminando los espacios y los caracteres duplicados.

Ejercicio. Crear un árbol, con las palabras de esté enunciado (en minúsculas).

Después de conocer la forma de organización de los nodos en un árbol binario, debe contemplar que los árboles binarios no deben contener nodos duplicados. Por lo tanto, antes de insertar un nuevo nodo, debe revisar que el nodo no exista antes de su inserción, si el nodo ya existe, el nuevo nodo no se insertará.

Los pasos para la insertar un nuevo nodo en un árbol binario son:

1. Crear el nodo nuevo.

2. Si el árbol se encuentra vacío, el nodo nuevo se asigna a la raíz.

3. Si no se encuentra vacío, se revisa si el nodo nuevo existe, de ser así, el proceso termina.

4. Si el nodo nuevo no existe, se busca el camino y el nodo del cual dependerá el nuevo nodo.

5. Se determina si el nuevo nodo se inserta del lado izquierdo o derecho.

6. Por último, se establecen las relaciones entre el nuevo nodo y el nodo que ahora será su padre.

RECORRIDOS EN LOS ÁRBOLES BINARIOS

Recorrer significa visitar cada uno de los nodos de un árbol exactamente una sola vez, este proceso puede interpretarse como poner todos los

...