java

Árbol binario en Java

Árbol binario en Java - Recorrido, inserción y búsqueda

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:

class Nodo {
    private int dato;
    private Nodo izquierda, derecha;

    public Nodo(int dato) {
        this.dato = dato;
        this.izquierda = this.derecha = null;
    }


    public int getDato() {
        return dato;
    }

    public Nodo getIzquierda() {
        return izquierda;
    }

    public void setIzquierda(Nodo izquierda) {
        this.izquierda = izquierda;
    }

    public Nodo getDerecha() {
        return derecha;
    }

    public void setDerecha(Nodo derecha) {
        this.derecha = derecha;
    }

    public void imprimirDato() {
        System.out.println(this.getDato());
    }
}

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:

private void preorden(Nodo n) {
    if (n != null) {
        n.imprimirDato();
        preorden(n.getIzquierda());
        preorden(n.getDerecha());
    }
}

private void inorden(Nodo n) {
    if (n != null) {
        inorden(n.getIzquierda());
        n.imprimirDato();
        inorden(n.getDerecha());
    }
}

private void postorden(Nodo n) {
    if (n != null) {
        postorden(n.getIzquierda());
        postorden(n.getDerecha());
        n.imprimirDato();
    }
}

public void preorden() {
    this.preorden(this.raiz);
}

public void inorden() {
    this.inorden(this.raiz);
}

public void postorden() {
    this.postorden(this.raiz);
}

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.

public boolean existe(int busqueda) {
    return existe(this.raiz, busqueda);
}

private boolean existe(Nodo n, int busqueda) {
    if (n == null) {
        return false;
    }
    if (n.getDato() == busqueda) {
        return true;
    } else if (busqueda < n.getDato()) {
        return existe(n.getIzquierda(), busqueda);
    } else {
        return existe(n.getDerecha(), busqueda);
    }

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.

Arbol arbol = new Arbol();
arbol.insertar(1);
arbol.insertar(2);
arbol.insertar(3);
arbol.insertar(4);
arbol.insertar(0);
System.out.println("Recorriendo inorden:");
arbol.inorden();
System.out.println("Recorriendo postorden:");
arbol.postorden();
System.out.println("Recorriendo preorden:");
arbol.preorden();
System.out.println(arbol.existe(1)); // true
System.out.println(arbol.existe(7)); // false
System.out.println(arbol.existe(0)); // true

Código completo

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

/*
  ____          _____               _ _           _
 |  _ \        |  __ \             (_) |         | |
 | |_) |_   _  | |__) |_ _ _ __ _____| |__  _   _| |_ ___
 |  _ <| | | | |  ___/ _` | '__|_  / | '_ \| | | | __/ _ \
 | |_) | |_| | | |  | (_| | |   / /| | |_) | |_| | ||  __/
 |____/ \__, | |_|   \__,_|_|  /___|_|_.__/ \__, |\__\___|
         __/ |                               __/ |
        |___/                               |___/

    Blog:       https://parzibyte.me/blog
    Ayuda:      https://parzibyte.me/blog/contrataciones-ayuda/
    Contacto:   https://parzibyte.me/blog/contacto/

    Copyright (c) 2020 Luis Cabrera Benito
    Licenciado bajo la licencia MIT

    El texto de arriba debe ser incluido en cualquier redistribución
* */
class Nodo {
    private int dato;
    private Nodo izquierda, derecha;

    public Nodo(int dato) {
        this.dato = dato;
        this.izquierda = this.derecha = null;
    }


    public int getDato() {
        return dato;
    }

    public Nodo getIzquierda() {
        return izquierda;
    }

    public void setIzquierda(Nodo izquierda) {
        this.izquierda = izquierda;
    }

    public Nodo getDerecha() {
        return derecha;
    }

    public void setDerecha(Nodo derecha) {
        this.derecha = derecha;
    }

    public void imprimirDato() {
        System.out.println(this.getDato());
    }
}

class Arbol {
    private Nodo raiz;

    public Arbol() {

    }

    public boolean existe(int busqueda) {
        return existe(this.raiz, busqueda);
    }

    private boolean existe(Nodo n, int busqueda) {
        if (n == null) {
            return false;
        }
        if (n.getDato() == busqueda) {
            return true;
        } else if (busqueda < n.getDato()) {
            return existe(n.getIzquierda(), busqueda);
        } else {
            return existe(n.getDerecha(), busqueda);
        }

    }

    public void insertar(int dato) {
        if (this.raiz == null) {
            this.raiz = new Nodo(dato);
        } else {
            this.insertar(this.raiz, dato);
        }
    }

    private void insertar(Nodo padre, int dato) {
        if (dato > padre.getDato()) {
            if (padre.getDerecha() == null) {
                padre.setDerecha(new Nodo(dato));
            } else {
                this.insertar(padre.getDerecha(), dato);
            }
        } else {
            if (padre.getIzquierda() == null) {
                padre.setIzquierda(new Nodo(dato));
            } else {
                this.insertar(padre.getIzquierda(), dato);
            }
        }
    }

    private void preorden(Nodo n) {
        if (n != null) {
            n.imprimirDato();
            preorden(n.getIzquierda());
            preorden(n.getDerecha());
        }
    }

    private void inorden(Nodo n) {
        if (n != null) {
            inorden(n.getIzquierda());
            n.imprimirDato();
            inorden(n.getDerecha());
        }
    }

    private void postorden(Nodo n) {
        if (n != null) {
            postorden(n.getIzquierda());
            postorden(n.getDerecha());
            n.imprimirDato();
        }
    }

    public void preorden() {
        this.preorden(this.raiz);
    }

    public void inorden() {
        this.inorden(this.raiz);
    }

    public void postorden() {
        this.postorden(this.raiz);
    }
}


 
class Main {
     public static void main(String[] argumentos) {
        Arbol arbol = new Arbol();
        arbol.insertar(1);
        arbol.insertar(2);
        arbol.insertar(3);
        arbol.insertar(4);
        arbol.insertar(0);
        System.out.println("Recorriendo inorden:");
        arbol.inorden();
        System.out.println("Recorriendo postorden:");
        arbol.postorden();
        System.out.println("Recorriendo preorden:");
        arbol.preorden();
        System.out.println(arbol.existe(1)); // true
        System.out.println(arbol.existe(7)); // false
        System.out.println(arbol.existe(0)); // true
    }
}

Á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.

class NodoCadena {
    private String dato;
    private NodoCadena izquierda, derecha;

    public NodoCadena(String dato) {
        this.dato = dato;
        this.izquierda = this.derecha = null;
    }


    public String getDato() {
        return dato;
    }

    public NodoCadena getIzquierda() {
        return izquierda;
    }

    public void setIzquierda(NodoCadena izquierda) {
        this.izquierda = izquierda;
    }

    public NodoCadena getDerecha() {
        return derecha;
    }

    public void setDerecha(NodoCadena derecha) {
        this.derecha = derecha;
    }

    public void imprimirDato() {
        System.out.println(this.getDato());
    }
}


class ArbolCadenas {
    private NodoCadena raiz;

    public ArbolCadenas() {

    }

    public boolean existe(String busqueda) {
        return existe(this.raiz, busqueda);
    }

    private boolean existe(NodoCadena n, String busqueda) {
        if (n == null) {
            return false;
        }
        if (n.getDato().equals(busqueda)) {
            return true;
        } else if (busqueda.compareTo(n.getDato()) < 0) {
            return existe(n.getIzquierda(), busqueda);
        } else {
            return existe(n.getDerecha(), busqueda);
        }

    }

    public void insertar(String dato) {
        if (this.raiz == null) {
            this.raiz = new NodoCadena(dato);
        } else {
            this.insertar(this.raiz, dato);
        }
    }

    private void insertar(NodoCadena padre, String dato) {
        if (dato.compareTo(padre.getDato()) > 0) {
            if (padre.getDerecha() == null) {
                padre.setDerecha(new NodoCadena(dato));
            } else {
                this.insertar(padre.getDerecha(), dato);
            }
        } else {
            if (padre.getIzquierda() == null) {
                padre.setIzquierda(new NodoCadena(dato));
            } else {
                this.insertar(padre.getIzquierda(), dato);
            }
        }
    }

    private void preorden(NodoCadena n) {
        if (n != null) {
            n.imprimirDato();
            preorden(n.getIzquierda());
            preorden(n.getDerecha());
        }
    }

    private void inorden(NodoCadena n) {
        if (n != null) {
            inorden(n.getIzquierda());
            n.imprimirDato();
            inorden(n.getDerecha());
        }
    }

    private void postorden(NodoCadena n) {
        if (n != null) {
            postorden(n.getIzquierda());
            postorden(n.getDerecha());
            n.imprimirDato();
        }
    }

    public void preorden() {
        this.preorden(this.raiz);
    }

    public void inorden() {
        this.inorden(this.raiz);
    }

    public void postorden() {
        this.postorden(this.raiz);
    }
}

Su uso es igual al árbol de enteros:

ArbolCadenas arbolCadenas = new ArbolCadenas();
arbolCadenas.insertar("Luis");
arbolCadenas.insertar("Chris");
arbolCadenas.insertar("Zelda");
arbolCadenas.insertar("Cuphead");
arbolCadenas.insertar("Leon");
System.out.println("Recorriendo inorden:");
arbolCadenas.inorden();
System.out.println("Recorriendo postorden:");
arbolCadenas.postorden();
System.out.println("Recorriendo preorden:");
arbolCadenas.preorden();
System.out.println(arbolCadenas.existe("Luis")); // true
System.out.println(arbolCadenas.existe("Claire")); // false
System.out.println(arbolCadenas.existe("Zelda")); // true

Poniendo todo junto

Árbol binario en Java – Recorrido, inserción y búsqueda

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

/*
  ____          _____               _ _           _
 |  _ \        |  __ \             (_) |         | |
 | |_) |_   _  | |__) |_ _ _ __ _____| |__  _   _| |_ ___
 |  _ <| | | | |  ___/ _` | '__|_  / | '_ \| | | | __/ _ \
 | |_) | |_| | | |  | (_| | |   / /| | |_) | |_| | ||  __/
 |____/ \__, | |_|   \__,_|_|  /___|_|_.__/ \__, |\__\___|
         __/ |                               __/ |
        |___/                               |___/

    Blog:       https://parzibyte.me/blog
    Ayuda:      https://parzibyte.me/blog/contrataciones-ayuda/
    Contacto:   https://parzibyte.me/blog/contacto/

    Copyright (c) 2020 Luis Cabrera Benito
    Licenciado bajo la licencia MIT

    El texto de arriba debe ser incluido en cualquier redistribución
* */
package me.parzibyte;

import java.util.TreeMap;

class NodoCadena {
    private String dato;
    private NodoCadena izquierda, derecha;

    public NodoCadena(String dato) {
        this.dato = dato;
        this.izquierda = this.derecha = null;
    }


    public String getDato() {
        return dato;
    }

    public NodoCadena getIzquierda() {
        return izquierda;
    }

    public void setIzquierda(NodoCadena izquierda) {
        this.izquierda = izquierda;
    }

    public NodoCadena getDerecha() {
        return derecha;
    }

    public void setDerecha(NodoCadena derecha) {
        this.derecha = derecha;
    }

    public void imprimirDato() {
        System.out.println(this.getDato());
    }
}


class ArbolCadenas {
    private NodoCadena raiz;

    public ArbolCadenas() {

    }

    public boolean existe(String busqueda) {
        return existe(this.raiz, busqueda);
    }

    private boolean existe(NodoCadena n, String busqueda) {
        if (n == null) {
            return false;
        }
        if (n.getDato().equals(busqueda)) {
            return true;
        } else if (busqueda.compareTo(n.getDato()) < 0) {
            return existe(n.getIzquierda(), busqueda);
        } else {
            return existe(n.getDerecha(), busqueda);
        }

    }

    public void insertar(String dato) {
        if (this.raiz == null) {
            this.raiz = new NodoCadena(dato);
        } else {
            this.insertar(this.raiz, dato);
        }
    }

    private void insertar(NodoCadena padre, String dato) {
        if (dato.compareTo(padre.getDato()) > 0) {
            if (padre.getDerecha() == null) {
                padre.setDerecha(new NodoCadena(dato));
            } else {
                this.insertar(padre.getDerecha(), dato);
            }
        } else {
            if (padre.getIzquierda() == null) {
                padre.setIzquierda(new NodoCadena(dato));
            } else {
                this.insertar(padre.getIzquierda(), dato);
            }
        }
    }

    private void preorden(NodoCadena n) {
        if (n != null) {
            n.imprimirDato();
            preorden(n.getIzquierda());
            preorden(n.getDerecha());
        }
    }

    private void inorden(NodoCadena n) {
        if (n != null) {
            inorden(n.getIzquierda());
            n.imprimirDato();
            inorden(n.getDerecha());
        }
    }

    private void postorden(NodoCadena n) {
        if (n != null) {
            postorden(n.getIzquierda());
            postorden(n.getDerecha());
            n.imprimirDato();
        }
    }

    public void preorden() {
        this.preorden(this.raiz);
    }

    public void inorden() {
        this.inorden(this.raiz);
    }

    public void postorden() {
        this.postorden(this.raiz);
    }
}

class Nodo {
    private int dato;
    private Nodo izquierda, derecha;

    public Nodo(int dato) {
        this.dato = dato;
        this.izquierda = this.derecha = null;
    }


    public int getDato() {
        return dato;
    }

    public Nodo getIzquierda() {
        return izquierda;
    }

    public void setIzquierda(Nodo izquierda) {
        this.izquierda = izquierda;
    }

    public Nodo getDerecha() {
        return derecha;
    }

    public void setDerecha(Nodo derecha) {
        this.derecha = derecha;
    }

    public void imprimirDato() {
        System.out.println(this.getDato());
    }
}

class Arbol {
    private Nodo raiz;

    public Arbol() {

    }

    public boolean existe(int busqueda) {
        return existe(this.raiz, busqueda);
    }

    private boolean existe(Nodo n, int busqueda) {
        if (n == null) {
            return false;
        }
        if (n.getDato() == busqueda) {
            return true;
        } else if (busqueda < n.getDato()) {
            return existe(n.getIzquierda(), busqueda);
        } else {
            return existe(n.getDerecha(), busqueda);
        }

    }

    public void insertar(int dato) {
        if (this.raiz == null) {
            this.raiz = new Nodo(dato);
        } else {
            this.insertar(this.raiz, dato);
        }
    }

    private void insertar(Nodo padre, int dato) {
        if (dato > padre.getDato()) {
            if (padre.getDerecha() == null) {
                padre.setDerecha(new Nodo(dato));
            } else {
                this.insertar(padre.getDerecha(), dato);
            }
        } else {
            if (padre.getIzquierda() == null) {
                padre.setIzquierda(new Nodo(dato));
            } else {
                this.insertar(padre.getIzquierda(), dato);
            }
        }
    }

    private void preorden(Nodo n) {
        if (n != null) {
            n.imprimirDato();
            preorden(n.getIzquierda());
            preorden(n.getDerecha());
        }
    }

    private void inorden(Nodo n) {
        if (n != null) {
            inorden(n.getIzquierda());
            n.imprimirDato();
            inorden(n.getDerecha());
        }
    }

    private void postorden(Nodo n) {
        if (n != null) {
            postorden(n.getIzquierda());
            postorden(n.getDerecha());
            n.imprimirDato();
        }
    }

    public void preorden() {
        this.preorden(this.raiz);
    }

    public void inorden() {
        this.inorden(this.raiz);
    }

    public void postorden() {
        this.postorden(this.raiz);
    }
}


public class Main {
    public static void main(String[] argumentos) {
        Arbol arbol = new Arbol();
        arbol.insertar(1);
        arbol.insertar(2);
        arbol.insertar(3);
        arbol.insertar(4);
        arbol.insertar(0);
        System.out.println("Recorriendo inorden:");
        arbol.inorden();
        System.out.println("Recorriendo postorden:");
        arbol.postorden();
        System.out.println("Recorriendo preorden:");
        arbol.preorden();
        System.out.println(arbol.existe(1)); // true
        System.out.println(arbol.existe(7)); // false
        System.out.println(arbol.existe(0)); // true
        ArbolCadenas arbolCadenas = new ArbolCadenas();
        arbolCadenas.insertar("Luis");
        arbolCadenas.insertar("Chris");
        arbolCadenas.insertar("Zelda");
        arbolCadenas.insertar("Cuphead");
        arbolCadenas.insertar("Leon");
        System.out.println("Recorriendo inorden:");
        arbolCadenas.inorden();
        System.out.println("Recorriendo postorden:");
        arbolCadenas.postorden();
        System.out.println("Recorriendo preorden:");
        arbolCadenas.preorden();
        System.out.println(arbolCadenas.existe("Luis")); // true
        System.out.println(arbolCadenas.existe("Claire")); // false
        System.out.println(arbolCadenas.existe("Zelda")); // true
    }
}

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.

Estoy aquí para ayudarte 🤝💻

Estoy aquí para ayudarte en todo lo que necesites. Si requieres alguna modificación en lo presentado en este post, deseas asistencia con tu tarea, proyecto o precisas desarrollar un software a medida, no dudes en contactarme. Estoy comprometido a brindarte el apoyo necesario para que logres tus objetivos. Mi correo es parzibyte(arroba)gmail.com, estoy como@parzibyte en Telegram o en mi página de contacto

No te pierdas ninguno de mis posts 🚀🔔

Suscríbete a mi canal de Telegram para recibir una notificación cuando escriba un nuevo tutorial de programación.
parzibyte

Programador freelancer listo para trabajar contigo. Aplicaciones web, móviles y de escritorio. PHP, Java, Go, Python, JavaScript, Kotlin y más :) https://parzibyte.me/blog/software-creado-por-parzibyte/

Ver comentarios

  • Que tal bro, disculpa como se guardaría la información que se ingresan en los nodos.
    Pd: Estoy realizando un adivinar animales pero me gustaría que esta información que se ingresa quede almacenada para cuando yo quiera volver a ejecutar el programa en java. De antemano te agradecería mucho, saludos.

Deja un comentario
Compartir
Publicado por
parzibyte
Etiquetas: árbolárbol binarioárbolesbúsquedacadenaestructura de datosinordenintjavanodopostordenpreordentree
5 años hace

Entradas recientes

Creador de credenciales web – Aplicación gratuita

Hoy te voy a presentar un creador de credenciales que acabo de programar y que…

1 semana hace

Desplegar PWA creada con Vue 3, Vite y SQLite3 en Apache

Ya te enseñé cómo convertir una aplicación web de Vue 3 en una PWA. Al…

2 semanas hace

Arquitectura para wasm con Go, Vue 3, Pinia y Vite

En este artículo voy a documentar la arquitectura que yo utilizo al trabajar con WebAssembly…

2 semanas hace

Vue 3 y Vite: crear PWA (Progressive Web App)

En un artículo anterior te enseñé a crear un PWA. Al final, cualquier aplicación que…

2 semanas hace

Errores de Comlink y algunas soluciones

Al usar Comlink para trabajar con los workers usando JavaScript me han aparecido algunos errores…

2 semanas hace

Esperar promesa para inicializar Store de Pinia con Vue 3

En este artículo te voy a enseñar cómo usar un "top level await" esperando a…

2 semanas hace

Esta web usa cookies.