En este tutorial se desarrolla un ejemplo sencillo en el que se grafica un árbol binario de búsqueda con ayuda de la herramienta Graphviz. Es importante mencionar que para que ejemplo funcione correctamente debe estar instalado Graphviz. Este proyecto se desarrolló utilizando Ubuntu 14.04 y Netbeans 8.0. El proyecto completo del ejemplo puede descargarse del siguiente enlace:

Graficar árboles binarios de búsqueda con Graphviz y Java.

Todo el código dentro del proyecto está documentado con comentarios que contienen explicaciones sobre su funcionamiento.

Instalación de Graphviz

Lo primero que haremos será instalar Graphviz, en caso de que no lo hayamos instalado todavía, para ello abrimos una terminal, en Ubuntu puede hacerse con la combinación de teclas Ctrl+Alt+t o en Aplicaciones → Accesorios → Terminal, una vez abierta la terminal ingresamos el comando “sudo apt-get install graphviz”, autenticamos ingresando nuestra contraseña y aceptamos la descarga e instalación, con esto quedará instalado Graphviz.

Funcionamiento del proyecto

El proyecto cuenta con la clase ArbolBinarioBusqueda, en el método principal de la aplicación, se instancian dos objetos de esta clase, es decir, dos árboles binarios de búsqueda, el primero almacena únicamente texto y el segundo únicamente números. El código de la clase principal de la aplicación es el siguiente:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

/*
 * Ejemplo desarrollado por Erick Navarro
 * Blog: e-navarro.blogspot.com
 * Octubre - 2015
 */

package abbgraphviz;

import abb.ArbolBinarioBusqueda;

/**
 * Clase principal de la aplicación.
 * @author Erick Navarro
 */
public class ABBGraphviz {

    /**
     * Método principal de la aplicación
     * @param args los argumentos de la línea de comando
     */
    public static void main(String[] args) {
        //Creamos un árbol cuyos nodos contendrán solamente texto
        ArbolBinarioBusqueda arbol_texto=new ArbolBinarioBusqueda();
        //Llenamos con información el árbol
        arbol_texto.insertar("Juan");
        arbol_texto.insertar("Pedro");
        arbol_texto.insertar("María");
        arbol_texto.insertar("Roberto");
        arbol_texto.insertar("Teodoro");
        arbol_texto.insertar("Manuel");
        arbol_texto.insertar("Diego");
        arbol_texto.insertar("Alejandro");
        //Graficamos el árbol generando la imagen arbol_texto.jpg
        arbol_texto.graficar("arbol_texto.jpg");
        //Imprimimos el contenido del árbol ordenado
        arbol_texto.inorden();
        
        System.out.println();
        //Creamos un árbol cuyos nodos contendrán solamente numeros
        ArbolBinarioBusqueda arbol_numeros=new ArbolBinarioBusqueda();
        //Llenamos con información el árbol
        arbol_numeros.insertar(12);
        arbol_numeros.insertar(5);
        arbol_numeros.insertar(26);
        arbol_numeros.insertar(33);
        arbol_numeros.insertar(59);
        arbol_numeros.insertar(27);
        arbol_numeros.insertar(15);      
        //Graficamos el árbol generando la imagen arbol_numeros.jpg
        arbol_numeros.graficar("arbol_numeros.jpg");
        //Imprimimos el contenido del árbol ordenado
        arbol_numeros.inorden();
    }
    
}

Al ser ejecutada la aplicación, se generan dos imagenes, una para cada árbol la primera arbol_texto.jpg corresponde al árbol que solo almacena texto en sus nodos.

La segunda arbol_numeros.jpg corresponde al árbol que solo almacena números.

En la consola se verán los elementos de ambos árboles impresos en orden, esto se logra haciendo un recorrido enorden de los arboles binarios de búsqueda.

Árbol binario de búsqueda

En un árbol binario, todos los nodos tienen como máximo dos hijos.

“Un árbol binario de búsqueda es aquel que dado un nodo, todos los datos del subárbol izquierdo son menores que los datos de ese nodo, mientras que todos los datos del subárbol derecho son mayores que sus propios datos.”

Fuente: Programación en Java 2. Luis Joyanes Aguilar, Ignacio Zahonero Martínez.

En este árbol únicamente se desarrolla el método para insertar nodos, porque el objetivo de la aplicación es únicamente graficar el árbol, adicionalmente, podrían desarrollarse métodos para eliminar nodos, buscar nodos, vaciar el árbol, calcular la profundidad del árbol, etc. El único recorrido que se hace del árbol es el enorden, que muestra los nodos del árbol ordenados, pero existen otros recorridos que también podrían implementarse como el recorrido preorden, postorden o el recorrido por anchura.

Interfaz Comparable: El secreto tras la flexibilidad de este árbol

La razón por la cual este árbol puede utilizarse para almacenar cadenas o bien para almacenar números es la interfaz Comparable. Lo que almacena el nodo es la instancia de una clase que implementa la interfaz Comparable, por supuesto que todos los nodos tienen que poder compararse satisfactoriamente, por ejemplo no se podrían almacenar números enteros y también cadenas de caracteres en un mismo árbol, ya que no podrían comparase satisfactoriamente porque se daría un problema de tipos. Pero si todos los nodos almacenan números, el árbol funciona sin problemas, al igual cuando todos los nodos almacenan cadenas.

Si deseáramos almacenar otro tipo de información podríamos programar una clase que contenga los atributos que deseamos y que implemente la interfaz Comparable, entonces sin modificar el árbol podríamos almacenar esta información.

Fuentes consultadas:

Programación en Java 2. Algoritmos, estructuras de datos y programación orientada a objetos. Luis Joyanes Aguilar, Ignacio Zahonero Martínez.

En este tutorial se desarrolla un ejemplo sencillo en el que se grafica un árbol AVL con ayuda de la herramienta Graphviz. Es importante mencionar que para que ejemplo funcione correctamente debe estar instalado Graphviz. Este proyecto se desarrolló utilizando Ubuntu 14.04 y Netbeans 8.0. El proyecto completo del ejemplo puede descargarse del siguiente enlace:

Graficar árboles AVL con Graphviz y Java.

Todo el código dentro del proyecto está documentado con comentarios que contienen explicaciones sobre su funcionamiento.

Instalación de Graphviz

Lo primero que haremos será instalar Graphviz, en caso de que no lo hayamos instalado todavía, para ello abrimos una terminal, en Ubuntu puede hacerse con la combinación de teclas Ctrl+Alt+t o en Aplicaciones → Accesorios → Terminal, una vez abierta la terminal ingresamos el comando “sudo apt-get install graphviz”, autenticamos ingresando nuestra contraseña y aceptamos la descarga e instalación, con esto quedará instalado Graphviz.

Funcionamiento del proyecto

El proyecto cuenta con la clase ArbolAVL, en el método principal de la aplicación, se instancian dos objetos de esta clase, es decir, dos árboles AVL, el primero almacena únicamente texto y el segundo únicamente números. El código de la clase principal de la aplicación es el siguiente:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

/*
 * Ejemplo desarrollado por Erick Navarro
 * Blog: e-navarro.blogspot.com
 * Octubre - 2015
 */

package avlgraphviz;

import avl.ArbolAVL;

/**
 * Clase principal de la aplicación.
 * @author Erick Navarro
 */
public class AVLGraphviz {

    /**
     * Método principal de la aplicación
     * @param args los argumentos de la línea de comando.
     */
    public static void main(String[] args) {
        //Creamos un árbol cuyos nodos contendrán solamente texto
        ArbolAVL arbol_texto=new ArbolAVL();
        //Llenamos con información el árbol
        arbol_texto.insertar("Juan");
        arbol_texto.insertar("Pedro");
        arbol_texto.insertar("María");
        arbol_texto.insertar("Roberto");
        arbol_texto.insertar("Teodoro");
        arbol_texto.insertar("Manuel");
        arbol_texto.insertar("Diego");
        arbol_texto.insertar("Alejandro");
        arbol_texto.insertar("Margarita");
        arbol_texto.insertar("Luis");
        arbol_texto.insertar("Hernán");
        arbol_texto.insertar("Jaime");
        arbol_texto.insertar("Ana");
        arbol_texto.insertar("Francisco");
        arbol_texto.insertar("Andrea");
        //Graficamos el árbol generando la imagen arbol_texto.jpg
        arbol_texto.graficar("arbol_texto.jpg");
        //Imprimimos el contenido del árbol ordenado
        arbol_texto.inorden();
        
        System.out.println();
        //Creamos un árbol cuyos nodos contendrán solamente numeros
        ArbolAVL arbol_numeros=new ArbolAVL();
        //Llenamos con información el árbol
        arbol_numeros.insertar(12);
        arbol_numeros.insertar(5);
        arbol_numeros.insertar(26);
        arbol_numeros.insertar(33);
        arbol_numeros.insertar(59);
        arbol_numeros.insertar(27);
        arbol_numeros.insertar(15);      
        arbol_numeros.insertar(47);
        arbol_numeros.insertar(74);
        arbol_numeros.insertar(84);
        arbol_numeros.insertar(88);
        arbol_numeros.insertar(90);
        arbol_numeros.insertar(124);
        arbol_numeros.insertar(612);
        //Graficamos el árbol generando la imagen arbol_numeros.jpg
        arbol_numeros.graficar("arbol_numeros.jpg");
        //Imprimimos el contenido del árbol ordenado
        arbol_numeros.inorden();
    }   
}

Al ser ejecutada la aplicación, se generan dos imagenes, una para cada árbol la primera arbol_texto.jpg corresponde al árbol que solo almacena texto en sus nodos.

La segunda arbol_numeros.jpg corresponde al árbol que solo almacena números.

En la consola se verán los elementos de ambos árboles impresos en orden, esto se logra haciendo un recorrido enorden de los arboles AVL.

Árbol AVL

El árbol AVL es un árbol binario de búsqueda equilibrado. Recibió el nombre del árbol AVL en honor de Adelson, Velskii y Landis, que fueron los primeros científicos en estudiar esta estructura de datos. “Un árbol AVL es un árbol binario de búsqueda en el que las alturas de los subárboles izquierdo y derecho de cualquier nodo difieren como máximo en 1.”

Fuente: Algoritmos y estructuras de datos, una perspectiva en C. Luis Joyanes Aguilar, Ignacio Zahonero Martínez.

En este árbol únicamente se desarrolla el método para insertar nodos, porque el objetivo de la aplicación es únicamente graficar el árbol, adicionalmente, podrían desarrollarse métodos para eliminar nodos, buscar nodos, vaciar el árbol, calcular la profundidad del árbol, etc. El único recorrido que se hace del árbol es el enorden, que muestra los nodos del árbol ordenados, pero existen otros recorridos que también podrían implementarse como el recorrido preorden, postorden o el recorrido por anchura.

Interfaz Comparable: El secreto tras la flexibilidad de este árbol

La razón por la cual este árbol puede utilizarse para almacenar cadenas o bien para almacenar números es la interfaz Comparable. Lo que almacena el nodo es la instancia de una clase que implementa la interfaz Comparable, por supuesto que todos los nodos tienen que poder compararse satisfactoriamente, por ejemplo no se podrían almacenar números enteros y también cadenas de caracteres en un mismo árbol, ya que no podrían comparase satisfactoriamente porque se daría un problema de tipos. Pero si todos los nodos almacenan números, el árbol funciona sin problemas, al igual cuando todos los nodos almacenan cadenas. Si deseáramos almacenar otro tipo de información podríamos programar una clase que contenga los atributos que deseamos y que implemente la interfaz Comparable, entonces sin modificar el árbol podríamos almacenar esta información.

Fuentes consultadas

Algoritmos y estructuras de datos, una perspectiva en C. Luis Joyanes Aguilar, Ignacio Zahonero Martínez.

En este tutorial se desarrolla un ejemplo sencillo de un intérprete que recibe como entrada un archivo de texto que contiene varias expresiones aritméticas que son evaluadas y posteriormente graficadas por Graphviz, para ello se hace análisis léxico y sintáctico de dicha entrada, los analizadores se generan con Jlex y Cup. Es importante mencionar que para que el ejemplo funcione correctamente debe estar instalado Graphviz. Para desarrollar el proyecto se utilizó Ubuntu 14.04 y Netbeans 8.0. El proyecto completo del ejemplo puede descargarse del siguiente enlace:

Graficar expresiones aritméticas con Graphviz, Java, Jlex y Cup

Todo el código dentro del proyecto está documentado con comentarios que contienen explicaciones sobre su funcionamiento.

Si desean, una pequeña introducción al uso de Jlex y Cup pueden visitar alguno de mis posts:

• Mi primer proyecto utilizando Jlex y Cup (Linux)
• Mi primer proyecto utilizando Jlex y Cup (Windows)

Instalación de Graphviz

Lo primero que haremos será instalar Graphviz, para ello abrimos una terminal, en Ubuntu puede hacerse con la combinación de teclas Ctrl+Alt+t o en Aplicaciones → Accesorios → Terminal, una vez abierta la terminal ingresamos el comando “sudo apt-get install graphviz”, autenticamos ingresando nuestra contraseña y aceptamos la descarga e instalación, con esto quedará instalado Graphviz.

Funcionamiento del proyecto

La aplicación recibe como entrada un archivo que se encuentra en la carpeta del proyecto, dicho archivo se llama “entrada.txt” y contiene lo siguiente:

1
2
3
4
5

Evaluar[1+1];
Evaluar[1+1*2];
Evaluar[1.5+1.25*6.4/3.3-5.2+7.1];
Evaluar[1.1+1.2*6.3/3.4-5+1*-2.12345];
Evaluar[(2+2)*3+(1-1)];

Al ejecutar la aplicación, esta le hace análisis léxico y sintáctico al archivo de entrada, evalúa las expresiones aritméticas e indica el resultado de la expresión y el nombre del archivo en el que se generó la imagen.

Veremos que se generan una serie de archivos .dot y una serie de archivos .jpg, los archivos dot, contienen el código con el que Graphviz genera la imagen jpg correspondiente.

A continuación se muestra el detalle de las imágenes que se generaron para cada línea del archivo de entrada.

1

Evaluar[1+1];

1

Evaluar[1+1*2];

1

Evaluar[1.5+1.25*6.4/3.3-5.2+7.1];

1

Evaluar[1.1+1.2*6.3/3.4-5+1*-2.12345];

1

Evaluar[(2+2)*3+(1-1)];

La magia detrás de todo esto: Árbol de sintaxis abstracta (AST)

Un árbol de sintaxis abstracta (AST) es una representación simplificada de la estructura sintáctica del código fuente. A nivel de programación un AST es una estructura de datos que se genera durante el proceso de análisis sintáctico.

En este ejemplo el AST es la pieza más importante porque con él pueden ejecutarse las principales funciones que son: evaluar la expresión y graficar la expresión.

En este ejemplo el AST se construye al hacer análisis sintáctico al archivo de entrada, esta estructura es un árbol binario, ya que cada nodo puede tener como máximo dos hijos y modela bien el funcionamiento de las expresiones aritméticas porque todas sus operaciones tienen dos operandos y el caso del operador “-” de las expresiones negativas que tiene un solo operando.

Hacemos análisis sintáctico una sola vez para cargar el árbol, posteriormente podemos recorrer ese árbol las veces que deseemos, podemos manipularlo y hacer muchas cosas sin necesidad de hacer nuevamente análisis sintáctico al archivo de entrada.

En este caso, el árbol se carga y posteriormente se recorre para evaluar la expresión aritmética y mostrar en consola el resultado. Se recorre nuevamente el árbol para generar el código de Graphviz y guardarlo en un archivo .dot, con el archivo .dot podemos pedirle a Graphviz que cree el diagrama de la expresión aritmética.

Todos los métodos que realizan estas acciones luego de cargar el árbol se encuentran en la clase “Nodo”, del paquete “arbol”. El método getValor, devuelve el resultado de la expresión aritmética evaluada. El método graficar, genera el diagrama de la expresión aritmética y devuelve el nombre del archivo generado.

Si les gusto este tutorial, puede que también estén interesados en este otro:

• Intérprete sencillo utilizando Java, Jlex y Cup

Fuentes consultadas:

Compiladores, principios, técnicas y herramientas. Aho, Lam, Sethi y Ullman. Segunda Edición.