2. Árboles Binarios

Publicado por: Gilber Briceño

2. DEFINICIÓN.

Se definen como árboles de grado 2. Esto es, cada nodo puede tener dos, uno o ningún hijo. Al tratarse como mucho de dos hijos, cada uno de ellos puede identificarse como hijo izquierdo o hijo derecho.

2.1. Implementación física.

El gráfico de un árbol es una representación conceptual cuya implementación física admite diversas posibilidades condicionadas, en primer lugar, por el dispositivo de almacenamiento del mismo (memoria principal o memoria externa). A los efectos del curso nos ocuparemos exclusivamente de la memoria principal en donde puede optarse por dos filosofías principales:

• Estructuras de datos estáticas, normalmente matrices.
• Estructuras de datos dinámicas

En cualquier caso, la representación física de un árbol requiere contemplar tres componentes:

• La clave (simple o compuesta).
• Dos punteros, indicando las ubicaciones respectivas de los nodos hijo izquierdo e hijo derecho.

Ejemplo. La  figura 1.3. representa un árbol binario que podría implementarse físicamente según se ilustra en las figuras  1.4. (estructura estática)  ó 1.5. (estructura dinámica).

Figura 1.3.  Ejemplo de árbol binario.

Figura 1.4.  Ejemplo de árbol binario. Implementación estática

Figura 1.5.  Ejemplo de árbol binario. Implementación dinámica.

2.2. Algoritmos básicos con árboles binarios.

Para la utilización de árboles binarios es necesario definir las clases NodoArbol y Arbol siguiendo la sintaxis siguiente:

2.2.1. Recorridos.

Se entiende por recorrido el tratamiento realizado para acceder a los diferentes nodos de un árbol. El recorrido puede afectar a la totalidad de los nodos del árbol (recorrido completo), por ejemplo si se desea conocer el número de nodos, o finalizar anticipadamente en función de determinada/s circunstancia/s, por ejemplo al encontrar el valor de una clave determinada.

En cualquier caso, el recorrido se puede realizar basándose en las siguientes modalidades:

• En profundidad. Se progresa verticalmente desde la raíz hacia las hojas y, en principio, de izquierda a derecha. Se plantean tres posibilidades atendiendo al momento en que se procesa la clave.

1.  Preorden. La clave se procesa en primer lugar. Posteriormente se realizan las llamadas recursivas (por la izquierda y por la derecha). La exploración en preorden del árbol de la figura 1.3.a. daría el siguiente resultado: 15, 25, 20, 10, 5, 45. Este tipo de recorrido es el más utilizado pues atiende a la estructura de organización jerárquica del árbol. También es el más eficiente cuando se trata de buscar claves. En general, el algoritmo de recorrido en preorden es el siguiente:

2. Orden central. Se desciende recursivamente por la rama izquierda. Al alcanzar la condición de finalización (arbol == null) se retorna y se procesa la clave, y a continuación se progresa por la rama derecha. La exploración en orden central del árbol de la figura 1.3.a. daría el siguiente resultado: 25, 15, 10, 20, 45, 5. Este tipo de recorrido es especialmente útil en todos aquellos procesos en los que sea necesario recorrer los nodos de acuerdo al orden físico de los mismos. En general, el algoritmo de recorrido en orden central es el siguiente:

3. Postorden. Se desciende recursivamente por la rama izquierda, al alcanzar el final de dicha rama, se retorna y se desciende por la rama derecha. Cuando se alcanza el final de la rama derecha, se procesa la clave. La exploración en postorden del árbol de la figura 1.3.a. daría el siguiente resultado: 25, 10, 45, 5, 20, 15.Este recorrido es el menos utilizado. Se utiliza para liberar memoria, o bien cuando la información de los niveles más profundos del árbol afecta a la información buscada. En general, el algoritmo de recorrido en postorden es el siguiente:

Ejemplo de algoritmo de recorrido en profundidad: desarrollar un método estático (sumaClaves) que obtenga la suma de las claves del árbol.

Como ejercicio se propone al alumno la realización de un algoritmo que cuente los nodos que tiene un árbol, utilizando uno de los tres recorridos en profundidad propuestos.

• Recorrido en amplitud. Implica un acceso a las claves recorriendo cada nivel de izquierda a derecha y descendiendo al siguiente. Por ejemplo, la exploración en amplitud del árbol de la figura 1.3.a. daría el siguiente resultado: 15, 25, 20, 10, 5, 45.

Para la implementación del recorrido en amplitud se requiere la utilización de la técnica iterativa así como de la disponibilidad de una estructura de datos auxiliar: TAD cola de nodos de árbol:

Por ejemplo, el algoritmo siguiente permite obtener un listado de las claves de un árbol binario recorrido en amplitud:

La idea, básicamente, consiste en encolar en la cola de punteros las direcciones (referencias) de los posibles hijos de cada nodo procesado (su dirección se encuentra en la variable p).

A continuación, en cada iteración se extrae el primer elemento de la cola que se corresponde con el nodo actual del árbol. Si su hijo izquierdo y/o su hijo derecho son distintos de null se encolan, y el proceso terminará cuando la cola se encuentre vacía.

2.2.2. Búsqueda.

Hasta ahora se han presentado distintos modos de recorrer el árbol completo. En algunas ocasiones, será necesario finalizar antes de completar el recorrido, no realizando posteriores llamadas recursivas. En algunos casos se requiere el empleo de un argumento adicional (pasado por referencia) que permita evitar, en su caso, la ejecución de posteriores llamadas recursivas.

El siguiente ejemplo implementa un método (búsqueda) que recibe como argumentos un árbol y una clave (ambos pasados por valor) y devuelve true si dicha clave se encuentra en el árbol, y false en caso contrario.

Se procede a recorrer en principio todo el árbol. Cada vez que se alcanza un extremo (llamada desde una hoja) se cumple la condición arbol == null y el método devuelve el valor false. Si a lo largo del recorrido se encuentra la clave buscada, el método devolverá el puntero a dicho nodo, y ya no se realizan nuevas llamadas recursivas, siendo este valor el que se entrega al módulo que llamó a el método, lo que evita el error que supondría alcanzar la condición de finalización en el extremo derecho del árbol (hijo derecho de la última hoja).

Por razones de eficiencia se realiza un recorrido en preorden.

2.2.3. Creación de un árbol.

Para insertar claves en un árbol es necesario establecer previamente un criterio. Normalmente no se permite insertar claves repetidas. En el apartado 3.2.1. se muestra cómo insertar nodos en un árbol binario de búsqueda. Para los árboles binarios que no sean de búsqueda, se puede utilizar el método juntar, que recibe una clave y dos árboles (a1 y a2), y devuelve un árbol con la clave en la raíz, a1 como subárbol izquierdo, y a2 como subárbol derecho:

En el siguiente ejemplo, se muestra como generar el árbol de la figura 1.6:

Figura 1.6. Ejemplo de árbol binario.

2.2.4.Tratamiento de hojas.

En este tipo de algoritmos se trata de evaluar la condición de que un nodo del árbol sea una hoja:

Por ejemplo, el siguiente método de tipo entero (cuentaHojas) devuelve como resultado el número de hojas del árbol que se le entrega como argumento.

2.2.5. Procesamiento con constancia del nivel.

Determinados tratamientos requieren conocer el nivel en que se encuentran los nodos visitados, para lo cual es necesario conocer el nivel actual.

Recorrido en profundidad.

Cuando se va a realizar un tratamiento en profundidad, pasamos como argumento (por valor) el nivel actual. En cada llamada recursiva (por la derecha o por la izquierda) se incrementa el nivel en una unidad. La inicialización de dicho argumento (a 1) se realiza en la primera llamada (no recursiva).

Por ejemplo, el siguiente método (clavesNiveles) recorre un árbol en preorden5 mostrando en la pantalla el valor de las diferentes claves así como el nivel en que se encuentran.

Recorrido en amplitud.

El algoritmo explicado para el recorrido en amplitud en el apartado 2.2.2., permite recorrer el árbol en amplitud, sin embargo, no se tiene constancia del nivel en que se encuentran los nodos a los que se accede.

En caso de que esto sea necesario debería modificarse, bien la estructura de la cola añadiendo el nivel, o bien el algoritmo visto anteriormente de manera que su estructura sea una iteración anidada en dos niveles.

Si se puede cambiar la estructura de la cola, podría utilizarse una cola con el siguiente tipo de elementos:

Utilizando los siguientes métodos para obtener el árbol y el nivel:

De tal forma que al encolar el árbol completo, pondríamos el nivel a 1, y posteriormente, cada vez que se va a encolar un elemento, lo primero que haremos será actualizar el nivel.

Si no se puede alterar la estructura de la cola, sería necesario cambiar el algoritmo de manera que existan dos niveles de iteración. El nivel externo es el general (para todo el árbol) y el nivel interno para cada nivel del árbol. Cuando se inicia el recorrido de un nivel (controlado por medio de la variable contador) es necesario conocer a prioridad su amplitud (variable actual) y según se va explorando dicho nivel se cuenta el número de hijos del siguiente nivel (variable siguiente). Al iniciar el proceso del siguiente nivel se pasa a la variable actual el último valor encontrado en la variable siguiente.

A continuación se muestra como ejemplo una variante del ejemplo anterior.

2.3. Ejemplo.

A continuación se desarrolla un método que intenta verificar si dos árboles son iguales o no.