Hoy toca ver una estructura de datos en Java: el árbol binario. Vamos a crear una clase para gestionar un árbol binario que tendrá las siguientes características:

1. Insertar datos (de manera balanceada)
2. Buscar datos
3. Recorrer en preorden, inorden y postorden

Además de eso, nuestro árbol tendrá soporte para datos de tipo String y de tipo int, por lo que podremos almacenar, buscar y mostrar datos tanto de cadena como de tipo entero.

Clase Nodo

Los árboles tienen nodos u hojas. Cada nodo tiene: un dato, un Nodo izquierdo y uno derecho. A su vez cada Nodo hijo puede tener más nodos y así hasta formar un árbol.

He implementado la siguiente clase en Java:

Lo único que tienes es una referencia a un Nodo izquierda y a otro nodo derecha (ambos pueden ser nulos o tener a su vez otro izquierda y/o derecha). Además de los getters, setters y finalmente el dato que guarda cada nodo.

El árbol

Vamos a crear una clase llamada Arbol que gestionará los Nodos. Esto es para abstraer más fácil todo esto de los árboles binarios en Java.

Método insertar

Esta función se encarga de insertar el valor dependiendo del mismo. Se hace lo siguiente: si la raíz no tiene dato, se le asigna el valor. En caso de que la raíz ya tenga un dato, se comprueba si el dato es menor, y si es así, se asigna al nodo izquierda de la raíz.

Si el dato es mayor que el dato de la raíz, entonces se coloca en la derecha de la raíz.

Pero además: si ya hay un dato a la izquierda o derecha de la raíz, se comprueba la izquierda o derecha del mismo de manera recursiva. Es decir, conforme el árbol crezca, se recorrerán más hojas para colocar de manera efectiva el nodo.

Si te fijas es un método sobrecargado. El que existe de forma simplemente recibe un dato que se insertará sin que el invocador tenga que acomodarlo.

En cambio el método privado recibe el nodo en el que se inserta, y busca la mejor manera de acomodarlo usando recursividad (línea 9 a 23).

Recorridos del árbol

Para los árboles binarios existen 3 tipos de recorridos: preorden, postorden e inorden. Vamos a ver los tres:

Como puedes ver lo único que cambia en los 3 métodos es el órden de visita de cada nodo. En uno primero se visita el actual, luego el izquierdo y luego el derecho.

En el inorden primero se visitan todos los nodos izquierda, luego el central y finalmente el de la derecha.

El recorrido postorden primero recorre la izquierda, luego la derecha y finalmente el nodo actual.

Lo interesante aquí es que, al recorrer el árbol inorden se obtendrán los datos ordenados.

Búsqueda dentro del árbol

Un método común requerido en los árboles es la búsqueda. En este caso vamos a crear una función que indica si determinado dato existe o no dentro del árbol.

La magia de todo esto es que la búsqueda será muy rápida, pues los datos están ordenados (los menores a la raíz están a la izquierda; los mayores a la derecha) así que digamos que se hará una búsqueda binaria.

Como puedes ver igualmente existen dos métodos, uno que es el que se invoca desde la clase y otro que se invoca internamente. Se usa de igual modo la recursión para seguir buscando por todos los nodos.

La recursión se detiene bien cuando se encuentra el valor o cuando ya no quedan nodos por recorrer.

Creando árbol e insertando datos

Veamos un ejemplo de cómo usar el árbol para insertar datos, recorrerlo y comprobar si un elemento existe dentro.

Código completo

Ahora veamos el código completo que conforma todo este ejercicio. Queda así:

Si quieres puedes probarlo en línea.

Árbol binario con nodo String

Como lo prometí al inicio, también dejo un ejemplo de árbol binario en Java pero ahora con Nodos/Hojas cuyo dato es de tipo String.

No es nada complejo, solo cambia la forma de comparar, pues usamos compareTo y equals para saber si una cadena es “menor o mayor” que otra.

Su uso es igual al árbol de enteros:

Poniendo todo junto

Las dos clases de árboles y sus respectivos nodos así como el modo de uso se engloban en el siguiente archivo:

Si quieres pruébalo en línea aquí.

Pequeña nota sobre los genéricos

Si te fijas en los ejemplos anteriores puedes ver que tuvimos que implementar un Nodo para cada tipo de dato, pero gracias a los genéricos se podría implementar un Nodo genérico cuyo tipo de dato fuera cualquiera.

Para ello se me ocurre implementar una interfaz que exponga dos métodos: compareTo y equals, así como las cadenas (pero con otros tipos de datos). De este modo podríamos tener árboles de todo tipo.

Ejemplo en YouTube

Si quieres puedes ver una explicación en mi canal de YouTube:

Conclusión

El árbol binario es una maravilla, lo que más me gusta es su modo de ordenar los datos de manera que queden, valga la redundancia, ordenados.

Te invito a ver un ejemplo de árbol binario en C.