Creo que uno de los mayores dolores de cabeza cuando uno estudia estructuras de datos son el programar arboles binarios de cualquier tipo, más aún cuando los programamos por ejemplo usando punteros, pero es que el mayor problema quizá es que no se entiende muy bien el funcionamiento de los arboles binarios, aqui vamos a programarlos de inicio a fin.

Contenido

  1. Introducción
  2. ¿Para que sirve un árbol binario?
  3. ¿Cómo se ingresa la información?
  4. Definición de las clases
  5. Agregar nuevo nodo al árbol
  6. Eliminar nodo del árbol
  7. Inorden, postorden, preorden (pendiente)
  8. Buscar información en el árbol (pendiente)

Introducción

Vamos a hablar primero un poco de que son los arboles binarios; nos dice Wikipedia «Un árbol binario es un grafo conexo, acíclico y no dirigido tal que el grado de cada vértice no es mayor a 3», eso significa que tenemos un grafo donde cada nodo puede tener máximo 2 hijos ( o hojas ) y estas hojas no pueden tener como hijos a cualquier otra hoja anterior como podemos ver en la siguiente imagen:

Podemos ver en la imagen como «Raíz» es padre de «Hoja 1» y «Hoja 2» y estas a su vez también son la raíz de las «Sub hojas» y se vuelve un proceso recursivo hasta n cantidad de hojas.

¿Para que sirve un árbol binario?

Como todos sabemos un árbol binario es una estructura de datos, y como todas, este sirve para organizar datos para facilitar su manipulación, ya sea el ingreso, borrado o búsqueda de datos, y precisamente una de las principales ventajas de los árboles binarios es la búsqueda, ya que como en muchos algoritmos de búsqueda necesitamos tener la información ordenada y en nuestros árboles binarios precisamente los datos van ingresando de forma ordenada.

Recorridos con los conocidos métodos recursivos:

  • Inorden
  • Postorden
  • Preorden

¿Cómo se ingresa la información?

Como dije anteriormente, la información se ingresa de forma ordenada esto se resuelve de forma muy sencilla con estos pasos:  

  1. Se toma el dato a ingresar X
  2. Partiendo de la raíz preguntamos: Nodo == null ( o no existe ) ?
  3. En caso afirmativo X pasa a ocupar el lugar del nodo y ya hemos ingresado nuestro primer dato.
  4. En caso negativo preguntamos: X < Nodo
  5. En caso de ser menor pasamos al Nodo de la IZQUIERDA del que acabamos de preguntar y repetimos desde el paso 2 partiendo del Nodo al que acabamos de visitar
  6. En caso de ser mayor pasamos al Nodo de la DERECHA y tal cual hicimos con el caso anterior repetimos desde el paso 2 partiendo de este nuevo Nodo.

Nos daremos cuenta de que es un proceso RECURSIVO en el cual al final por más grande que sea el árbol el dato a entrar ocupará un lugar, vamos a ejemplificar lo ya mencionado con una imagen:

Si observan con detenimiento la imagen aunque se vea algo «complejo» entenderán bien el funcionamiento.

Vamos a programarlo

Todo lo dicho anteriormente, vamos a programarlo ahora usando POO con java (para que sea más fácil de entender).

Comenzamos con la abstracción de la información, tenemos que un árbol binario está compuesto por la raíz y sus nodos hijos, de la misma forma que la misma raíz no es más que otro nodo, partiendo de esto entonces crearemos 2 clases:

(Quiero comentar antes de esto que, aunque no soy muy partidario de escribir los nombres de los métodos y clases en español, por cuestiones de entendimiento para muchas personas que lleguen a esta información, los pondré de esa forma).

  • Arbol
  • Nodo

Para comenzar con esas clases tenemos, vamos ahora a definirlas:

// Nodo.java
public class Nodo {

    /* Declaraciones de variables */
    private int valor;

    private Nodo padre;
    private Nodo hojaIzquierda;
    private Nodo hojaDerecha;

    /* Constructor */
    public Nodo(int valor) {
        this.valor = valor;
    }

    /* Setters y Getters */
    public void setValor(int valor) {
        this.valor = valor;
    }

    public int getValor() {
        return valor;
    }

    public Nodo getPadre() {
        return padre;
    }

    public void setPadre(Nodo padre) {
        this.padre = padre;
    }

    public Nodo getHojaIzquierda() {
        return hojaIzquierda;
    }

    public void setHojaIzquierda(Nodo hojaIzquierda) {
        this.hojaIzquierda = hojaIzquierda;
    }

    public Nodo getHojaDerecha() {
        return hojaDerecha;
    }

    public void setHojaDerecha(Nodo hojaDerecha) {
        this.hojaDerecha = hojaDerecha;
    }

}

Vamos a revisar un poco más de cerca el código.

Es una clase muy sencilla, como podemos ver únicamente tiene 4 atributos (variables) fáciles de entender:

  • valor
  • hojaIzquierda
  • hojaDerecha

valor es el dato almacenado del propio nodo, mientras que como recordaremos cada nodo puede tener máximo 2 hijos uno a la izquierda y otro a la derecha, donde todos los nodos a su izquierda son menores a el mismo y todos los nodos a su derecha son mayores a el mismo, pero que comienzan como nulos ya que al crear un nuevo nodo, este no tiene hijos.

Hay que tener cuidado con setValor( int valor ) ¿Porque? pues bien, no podemos actualizar el valor al aire ya que perderíamos el orden, por lo que tenemos un contructor:

/* Constructor */
public Nodo(int valor) {
  this.valor = valor;
}

a partir del cual se ingresa el valor del nodo al crear una instancia del mismo: 

Nodo nodo = new Nodo( 1 );

Ya tenemos nuestra clase nodo lista, ahora pasemos con la clase Arbol.java que es aún más sencilla ( en definición ) que Nodo: 

// Arbol.java
public class Arbol {

    /* Atributos */
    private Nodo raiz;

    /* Contructories */    
    public Arbol( int valor ) {
        this.raiz = new Nodo( valor );
    }

    public Arbol( Nodo raiz ) {
        this.raiz = raiz;
    }

    /* Setters y Getters */
    public Nodo getRaiz() {
        return raiz;
    }

    public void setRaiz(Nodo raiz) {
        this.raiz = raiz;
    }

}

Prácticamente por ahora lo importante es su atributo «raiz» del tipo Nodo, el cual representará a todo nuestro árbol, adicionalmente he creado constructores que pueden ser de ayuda al momento de inicializar el árbol para crear la raíz de paso.

pffff que nos hemos alargado con el post, pero aún no terminamos, acabamos apenas de definir entidades faltan todas las funciones del mismo. vamos con ellas.

Hay que agregar métodos a nuestra clase de Arbol para poder ingresar nuevos nodos:

  • addNodo
  • removeNodo
  • recorridoPreorden
  • recorridoInorden
  • recorridoPostorden

Programando las funciones del árbol

En esta primera parte quiero abarcar al menos hasta el ingreso de nuevos nodos, comencemos entonces.

La modificación la haremos en nuestra clase Arbol que es la que llevará estas funciones de control, recordemos nuestro algoritmo de inserción que planteamos anteriormente:

  1. Se toma el dato a ingresar X
  2. Partiendo de la raíz preguntamos: Nodo == null ( o no existe ) ?
  3. En caso afirmativo X pasa a ocupar el lugar del nodo y ya hemos ingresado nuestro primer dato.
  4. En caso negativo preguntamos: X < Nodo
  5. En caso de ser menor pasamos al Nodo de la IZQUIERDA del que acabamos de preguntar y repetimos desde el paso 2 partiendo del Nodo al que acabamos de visitar
  6. En caso de ser mayor pasamos al Nodo de la DERECHA y tal cual hicimos con el caso anterior repetimos desde el paso 2 partiendo de este nuevo Nodo.

Entonces definamos nuestra función:

private void private void addNodo( Nodo nodo, Nodo raiz ) {
    /* 2.- Partiendo de la raíz preguntamos: Nodo == null ( o no existe ) ? */
    if ( raiz == null ) {
        /* 
        * 3.- En caso afirmativo X pasa a ocupar el lugar del nodo y ya 
        * hemos ingresado nuestro primer dato. 
        * ==== EDITO =====
        * Muchas gracias a @Espectro por la corrección de esta línea
        */
        this.setRaiz(nodo);
    }
    else {
        /* 4.- En caso negativo preguntamos: X < Nodo */
        if ( nodo.getValor() <= raiz.getValor() ) {
            /* 
            * 5.- En caso de ser menor pasamos al Nodo de la IZQUIERDA del
            * que acabamos de preguntar y repetimos desde el paso 2 
            * partiendo del Nodo al que acabamos de visitar 
            */
            if (raiz.getHojaIzquierda() == null) {
                raiz.setHojaIzquierda(nodo);
            }
            else {
                addNodo( nodo , raiz.getHojaIzquierda() );
            }
        }
        else {
            /* 
            * 6.- En caso de ser mayor pasamos al Nodo de la DERECHA y tal
            * cual hicimos con el caso anterior repetimos desde el paso 2
            * partiendo de este nuevo Nodo.
            */
            if (raiz.getHojaDerecha() == null) {
                raiz.setHojaDerecha(nodo);
            }
            else {
                addNodo( nodo, raiz.getHojaDerecha() );
            }
        }
    }
}

public void addNodo( Nodo nodo ) {
    this.addNodo( nodo , this.raiz );
}

Podemos ver que he agregado 2 funciones para insertar un nuevo nodo, pero solo 1 de ellas es vista desde fuera, la que nosotros llamaremos, esto es porque la función que  usamos realmente para insertar (llamada dentro del método que vemos desde fuera de la clase [el método público, para quien ande perdido]) necesita una referencia de la «raíz» a partir de que nodo va a hacer las comprobaciones, para que al usar la recursividad esta raíz pueda ir cambiando (de acuerdo al algoritmo) y seguir probando y comparando nodos.

Hasta ahora hemos comprendido el funcionamiento de los árboles binarios, hemos definido las clases a usar y ya comenzamos con las funciones básicas del mismo, en la próxima entrada veremos como hacer la eliminación de un nodo para así continuar hasta terminar este tema (que tanto dolor de cabeza le da a algunas personas) tan interesante.