Programación Java - Ingresar palabra letra por letra en Árbol binario

Java: ingresar palabra en árbol binario

2 comentarios / Algoritmos, Ejercicios resueltos, java / Por

Hoy vamos a resolver un ejercicio de Java. Se trata de solicitar una palabra y almacenarla en un árbol binario de búsqueda o ABB. El mismo dice así:

  • Diseñar un programa en Java que ingrese una palabra mínima de 10 caracteres (se debe realizar la verificación de que no acepte frases), proceda a
    separar carácter a carácter y guardarlos en un ABB
  • Recuerde que la primera letra será la Raíz.
  • Es importante indicar que todo debe ser ejecutado en consola.
  • El programa debe tener mínimo las siguientes opciones: Ingresar, Visualizar (pre-orden, post-orden e in-orden) y Finalizar.
  • El programa debe tener al menos 3 clases.

Explicación del algoritmo

Esto se divide en dos partes: la implementación de un árbol binario y la lectura de la palabra junto con su validación.

Entonces primero debes tener el árbol binario con el tipo de dato String. Yo he tomado el ejemplo de árbol binario que yo mismo hice, y lo he adaptado a este nuevo tipo de dato usando compareTo y equals para comparar las cadenas.

Por otro lado vamos a validar la cadena (comprobar su longitud y ver si no es una frase), separarla (recorrerla con charAt y convirtiendo el char a String) y agregar cada letra al árbol.

El nodo

Para este ejercicio de agregar las letras de una palabra a un árbol binario usando Java necesitamos un nodo de tipo String:

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

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

    public String 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());
    }
}

Si no entiendes bien lo que se está haciendo, lee mi post sobre árboles binarios y nodos en Java, pues ahí lo expliqué a fondo. Aquí solo lo estoy adaptando.

Árbol

Ahora veamos el ABB que va a tener los nodos, en donde cada nodo tendrá una letra de la palabra:

class Arbol {
    private Nodo raiz;

    public Arbol() {

    }

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

    private boolean existe(Nodo 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 Nodo(dato);
        } else {
            this.insertar(this.raiz, dato);
        }
    }

    private void insertar(Nodo padre, String dato) {
        if (dato.compareTo(padre.getDato()) > 0) {
            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);
    }
}

Ya tenemos nuestro árbol preparado, ahora solo falta que le agreguemos letras.

Validando palabra

El ejercicio solicita que la longitud de la palabra sea de 10 como mínimo y que no se ingresen frases.

Yo entiendo como frase a una cadena que lleva un espacio, cosa que podemos detectar con indexOf, mismo que devuelve el índice de una subcadena o -1 si la misma no se encuentra.

Entonces tenemos un ciclo infinito que solo se romperá con el return en caso de que pase ambas validaciones.

    private static String solicitarPalabra() {
        Scanner sc = new Scanner(System.in);
        while (true) {
            System.out.println("Ingresa la palabra: ");
            String palabra = sc.nextLine();
            if (palabra.indexOf(" ") != -1) {
                System.out.println("No puedes ingresar una frase");
            } else if (palabra.length() < 10) {
                System.out.println("La longitud mínima es de 10");
            } else {
                return palabra;
            }
        }

    }

Insertar palabra en árbol

Finalmente vamos a combinar los métodos y clases para solucionar el ejercicio. En este caso tenemos otro método que devolverá el Árbol binario de Java lleno con las letras de la palabra:

    public static Arbol obtenerArbol() {
        String palabra = AyudanteDatos.solicitarPalabra();
        Arbol arbol = new Arbol();
        for (int i = 0; i < palabra.length(); i++) {
            String letra = String.valueOf(palabra.charAt(i));
            if (!arbol.existe(letra)) {
                arbol.insertar(letra);
            }
        }
        return arbol;
    }

Recorremos la cadena en la línea 4 e insertamos la letra (después de convertirla) en la línea 7, comprobando antes que no exista en el árbol.

Menú

Debemos tener la opción de ingresar la palabra y de visualizarla en los 3 recorridos que son postorden, inorden y preorden. El menú queda así:

    public static void main(String[] args) {
        String eleccion = "";
        Arbol arbol = null;
        Scanner sc = new Scanner(System.in);
        while (!eleccion.equals("5")) {
            System.out.println("1. Ingresar");
            System.out.println("2. Visualizar Pre-Orden");
            System.out.println("3. Visualizar Pos-Orden");
            System.out.println("4. Visualizar In-Orden");
            System.out.println("5. Salir");
            System.out.println("Elige: ");
            eleccion = sc.nextLine();
            if (eleccion.equals("1")) {
                arbol = AyudanteDatos.obtenerArbol();
            } else if (eleccion.equals("2")) {
                if (arbol != null) {
                    arbol.preorden();
                } else {
                    System.out.println("No has ingresado nada");
                }
            } else if (eleccion.equals("3")) {
                if (arbol != null) {
                    arbol.postorden();
                } else {
                    System.out.println("No has ingresado nada");
                }
            } else if (eleccion.equals("4")) {
                if (arbol != null) {
                    arbol.inorden();
                } else {
                    System.out.println("No has ingresado nada");
                }
            }
        }

    }

Dependiendo de la opción invocamos a una u otra función.

Explicación en vídeo

Poniendo todo junto

Programación Java - Ingresar palabra letra por letra en Árbol binario
Programación Java – Ingresar palabra letra por letra en Árbol binario

El código completo queda como se ve a continuación. Puedes ejecutar esto en Netbeans, IntelliJ IDEA, etcétera. Yo lo compilo en la terminal y uso VSCode.

import java.util.Scanner;
/*
    https://parzibyte.me/blog
*/

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

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

    public String 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.print(this.getDato() + ",");
    }
}

class Arbol {
    private Nodo raiz;

    public Arbol() {

    }

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

    private boolean existe(Nodo 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 Nodo(dato);
        } else {
            this.insertar(this.raiz, dato);
        }
    }

    private void insertar(Nodo padre, String dato) {
        if (dato.compareTo(padre.getDato()) > 0) {
            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 AyudanteDatos {
    public static Arbol obtenerArbol() {
        String palabra = AyudanteDatos.solicitarPalabra();
        Arbol arbol = new Arbol();
        for (int i = 0; i < palabra.length(); i++) {
            String letra = String.valueOf(palabra.charAt(i));
            if (!arbol.existe(letra)) {
                arbol.insertar(letra);
            }
        }
        return arbol;
    }

    private static String solicitarPalabra() {
        Scanner sc = new Scanner(System.in);
        while (true) {
            System.out.println("Ingresa la palabra: ");
            String palabra = sc.nextLine();
            if (palabra.indexOf(" ") != -1) {
                System.out.println("No puedes ingresar una frase");
            } else if (palabra.length() < 10) {
                System.out.println("La longitud minima es de 10");
            } else {
                return palabra;
            }
        }

    }
}

class Main {
    public static void main(String[] args) {
        String eleccion = "";
        Arbol arbol = null;
        Scanner sc = new Scanner(System.in);
        while (!eleccion.equals("5")) {
            System.out.println("1. Ingresar");
            System.out.println("2. Visualizar Pre-Orden");
            System.out.println("3. Visualizar Pos-Orden");
            System.out.println("4. Visualizar In-Orden");
            System.out.println("5. Salir");
            System.out.println("Elige: ");
            eleccion = sc.nextLine();
            if (eleccion.equals("1")) {
                arbol = AyudanteDatos.obtenerArbol();
            } else if (eleccion.equals("2")) {
                if (arbol != null) {
                    arbol.preorden();
                    System.out.println("");
                } else {
                    System.out.println("No has ingresado nada");
                }
            } else if (eleccion.equals("3")) {
                if (arbol != null) {
                    arbol.postorden();
                    System.out.println("");
                } else {
                    System.out.println("No has ingresado nada");
                }
            } else if (eleccion.equals("4")) {
                if (arbol != null) {
                    arbol.inorden();
                    System.out.println("");
                } else {
                    System.out.println("No has ingresado nada");
                }
            }
        }

    }
}

Por aquí te dejo más tutoriales y ejercicios resueltos de Java.

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.

2 comentarios en “Java: ingresar palabra en árbol binario”

  1. bellamod

    Como podría pedir todo eso que pides desde consola usando un JOptionPane, lo del menu ya lo tengo pero cuando ingrese la cadena de caracteres el programa se rompe

    Responder

Dejar un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *