Estructura De Datos - Arbol

Introducción

En informática, un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él.

Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.

Árbol

Definición

Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos. También se suele dar una definición recursiva: un árbol es una estructura compuesta por un dato y varios árboles. La forma gráfica se puede apreciar como sigue:

En relación con los nodos, debemos definir algunos conceptos como:

• Nodo Hijo: Cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, “L” y “M” son hijos de “G”.

• Nodo Padre: Es el nodo que contiene un puntero al nodo actual. En el ejemplo, “A” es padre de “B”, “C” y “D”.

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

• Nodo Raíz: Es el nodo que no tiene padre. Este es el nodo que usaremos para acceder al árbol. En el ejemplo, ese nodo es “A”.

• Nodo Hoja: Es el nodo que no tiene hijos. En el ejemplo, hay varios: “K”, “M”, “O”, etc.

• Nodo Rama: Esta definición apenas se usara, pero, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo “B”, “G”, “D”, “J”, etc.

Existen otros conceptos que definen las características del árbol, en relación a su tamaño:

• Orden: Es el número potencial de hijos que puede tener cada elemento del árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos, es de orden dos, si puede apuntar a tres, es de orden tres, etc.

• Grado: Es el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol de ejemplo, el grado es tres, ya que tanto “A” como “D” tienen tres hijos y no existen elementos con más de tres hijos.

• 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. En el ejemplo, el nodo “D” tiene nivel uno, el nodo “G” tiene nivel dos, el nodo ‘N nivel tres.

• Altura: La altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol de ejemplo, tiene altura tres, la rama “B” tiene altura dos, la rama “G” tiene altura uno, la “H” cero, etc.

Representación

Los pasos que se deben aplicar para lograr la conversión del árbol general a binario son los siguientes:

• Deben enlazarse los hijos de cada nodo en forma horizontal (los hermanos).

• Debe enlazarse en forma vertical el nodo padre con el hijo que se encuentra más a la izquierda.

• Debe rotarse el diagrama resultante, aproximadamente 45 grados hacia la izquierda y así se obtendrá el árbol binario correspondiente.

Conversión de un árbol general en un árbol binario. (a) Árbol general. (b) Árbol binario luego de aplicar pasos 1 y 2. (c) Árbol binario luego de aplicar el paso 3.

Todo árbol binario obtenido a partir de un árbol general, debe cumplir lo siguiente:

• En la rama derecha de cada nodo, excepto el nodo raíz, si ésta es distinta de vacío se encuentra un nodo que era hermano de éste en el árbol general.

• En la rama izquierda de cada nodo (si ésta es distinta de vacío), se encuentra un nodo que era hijo de éste en el árbol generado.

Existen dos formas tradicionales de representar un árbol binario en memoria.

• Por medio de listas enlazadas, variables dinámicas.

• Por medio de arreglos.

Representación de Arboles Binarios en Memoria Por medio de Listas Enlazadas y Arreglos.

Los nodos del árbol binario serán representados como registros, que contendrán como mínimo tres campos. En un campo se almacenará la información del nodo. Los dos restantes se utilizarán para apuntar los subárboles izquierdo y derecho respectivamente del nodo en cuestión. Dado el siguiente nodo T:

Dónde:

• IZQ: campo donde se almacena la dirección del subárbol izquierdo del nodo T.

• INFO: campo donde se almacena la información de interés del nodo.

• DER: campo donde se almacena la dirección del subárbol derecho del nodo T.

La definición de un árbol binario en lenguaje algorítmico es como sigue.

Árboles binarios

Los árboles de orden dos son bastante especiales, de hecho les dedicaremos varios capítulos. Estos árboles se conocen también como árboles binarios.

Un árbol binario, requiere de una estructura de NODO que permita almacenar el dato correspondiente, además de una referencia al hijo izquierdo y una más al hijo derecho. El árbol será una liga al nodo raíz, a partir del cual, se podrá acceder al resto de la estructura.

Operaciones básicas con árboles

Salvo que trabajemos con árboles especiales, como los que veremos más adelante, las inserciones serán siempre en punteros de nodos hoja o en punteros libres de nodos rama. Con estas estructuras no es tan fácil generalizar, ya que existen muchas variedades de árboles.

De nuevo tenemos casi el mismo repertorio de operaciones de las que disponíamos con las listas:

• Añadir o insertar elementos.

• Buscar o localizar elementos.

• Borrar elementos.

• Moverse a través del árbol.

• Recorrer el árbol completo.

Los algoritmos de inserción y borrado dependen en gran medida del tipo de árbol que estemos implementando, de modo que por ahora los pasaremos por alto y nos centraremos más en el modo de recorrer árboles.

El algoritmo de creación de un árbol binario es el siguiente:

Procedimiento crear (q: nodo)

inicio

mensaje ("Rama izquierda?")

lee(respuesta)

si respuesta = "si" entonces

new(p)

q(li) <-- nil

crear(p)

en caso contrario

...