Arboles Binarios

Arboles Binarios

Definición:

Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos pueden ser estructura no lineal y dinámica de datos. 

Dinámica: puede cambiar durante la ejecución de un programa.

No lineal: a cada elemento del árbol pueden seguirse varios elementos. Están formados por un conjunto de nodos y un conjunto de aristas que conectan pares de nodos.

También se suele dar una definición re cursiva: un árbol es una estructura en compuesta por un dato y varios árboles.

Estas son definiciones simples. Pero las características que implican no lo son tanto.

Imagen de  un Árbol Binario

Tipos de Árbol Binario:

• ·         Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.        
•  Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.

•           Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura).

·        A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol binario completo como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n.

Partes de un árbol:

Cuando hay 0 nodos se dice que el árbol está vacío, en caso contrario el árbol consiste en un nodo denominado raíz, el cual tiene 0 o más referencias a otros árboles, conocidos como sub-árboles. 

Las raíces de los sub-árboles se denominan hijos de la raíz

 la raíz se denomina padre de las raíces de sus sub-árboles.

Recorrido de un Árbol:

•  Pre orden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en pre orden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:

1. Visite la raíz
2. Atraviese el sub-árbol izquierdo
3. Atraviese el sub-árbol derecho

• In orden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en in orden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:

 
1. Atraviese el sub-árbol izquierdo
2. Visite la raíz
3. Atraviese el sub-árbol derecho

• Post orden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en post orden, hay que realizar las siguientes operaciones recursivamente en cada nodo:

1. Atraviese el sub-árbol izquierdo
2. Atraviese el sub-árbol derecho
3. Visite la raíz

Ejemplo Explicativo de como Recorrer un Árbol Binario:

• Secuencia de recorrido de pre orden: F, B, A, D, C, E, G, I, H (raíz, izquierda, derecha)

• Secuencia de recorrido de in orden: A, B, C, D, E, F, G, H, I (izquierda, raíz, derecha); note cómo esto produce una secuencia ordenada

• Secuencia de recorrido de post orden: A, C, E, D, B, H, I, G, F (izquierda, derecha, raíz)

Declarar un Árbol Binario:

Para implementar el árbol, se utilizan variables de tipo puntero y variables referenciadas.

La variable de tipo puntero se llamará Puntero y apuntará a la variable referenciada Arbol que será un registro que estará formado por tres campos: 

Nodo para almacenar la información sobre el hecho histórico. Rama Izquierda que apuntará al personaje histórico que cumple con las exigencias de la información y Rama Derecha que utilizaremos para apuntar al personaje que no cumple los requisitos de la información.

Type

Puntero = ˆ Arbol;

Arbol = Record

Nodo : String;

RamaIzquierda : Puntero;

RamaDerecha : Puntero;

End;

La variable referenciada se crea dinámicamente utilizando el procedimiento estándar New.

El árbol se construirá creando cada nodo y enlazándolo, después que se creen los subárboles, a su sucesor izquierdo y derecho respectivamente. Para ello se declaran las variables de tipo Puntero:

Var

Elemento, Predecesor : Puntero;

Elemento para el nodo que se crea y Predecesor para poder actualizar los punteros, de ese elemento que se creó, después que se creen los sub-árboles ya que dichos punteros, inicialmente, apuntarán a Nil para indicar que están vacío.

New (Elemento);

Elemento.Nodo := ‘¿Fue asaltante del Moncada?’;

Elemento.RamaIzquierda := Nil;

ElementoRamaDerecha := Nil;

Predecesor := Elemento;

New (Elemento);

Elemento.Nodo := ‘Fidel’;

Elemento.RamaIzquierda := Nil;

ElementoRamaDerecha := Nil;

Predecesor.RamaIzquierda := Elemento;

New (Elemento);

Elemento.Nodo := ‘Martí’;

Elemento.RamaIzquierda := Nil;

ElementoRamaDerecha := Nil;

Predecesor.RamaDerecha := Elemento;

Si al correr el programa el usuario pensó por ejemplo en Maceo, se recorrerá el subárbol derecho al responderse que no fue asaltante al Moncada y se preguntará entonces si es Martí, como la respuesta es de nuevo negativa, le pedirá al usuario que introduzca el nombre del personaje y una información que lo distinga de Martí.

Conclusión: Podemos concluir que los árboles en Object Pascal, permite la representación de estructuras de datos en la memoria de la computadora cuando la relación entre los elementos que componen dicha estructura es una relación jerárquica.

Vídeo: Recorrido En Arboles Binarios:

Ismael Pestana.