Arboles binarios En Java recorrido preorden postorden inorden

[Mac]

Hola comunidad tengo esta pequeña problemática. Tengo un arbol en JAVA tipo Int (De números enteros) me funciona perfectamente pero al momento de hacerlo Tipo String ( Letras ) no se que sucede !  si ya e declarado las variable de Tipo String  .....

Colocare el código para que me orienten ... 

Muchísimas Gracias Por Su Colaboración
---------------------------------------------------------------------------------------------------
PruebaArbol

Código: [Seleccionar]

package main;

import javax.swing.*;
//import java.util.Random;
import operaciones.Arbol;

public class PruebaArbol {

    public static void main(String[] args) {

        Arbol arbol = new Arbol();

        int in;
        //, valor;
        String nombre;

        // Random numeroAleatorio = new Random();
        in = Integer.parseInt(JOptionPane.showInputDialog(" Digite cuantos Nombres Contendra El Arbol " ));
        System.out.println(" Insertando los siguientes valores: ");
        for (int i = 1; i <= in; i++) {

            nombre = JOptionpane.showInputDialog("Escribe tu nombre:");

            // valor = Integer.parseInt(JOptionPane.showInputDialog(" Digite Los Numeros Para El Arbol "));
            // valor = numeroAleatorio.nextInt(100);  Lo quito para dijitar datos por el usurio
            System.out.print(nombre + " ");
            arbol.insertarNodo(nombre);
        }

        System.out.println("\n\nRecorrido Preorden");
        arbol.recorridoPreorden();

        System.out.println("\n\nRecorrido Inorden");
        arbol.recorridoInorden();

        System.out.println("\n\nRecorrido Postorden");
        arbol.recorridoPostorden();
        System.out.println();
    }
}

-----------------
Arbol

Código: [Seleccionar]

package operaciones;

public class Arbol {

    private NodoArbol raiz;

    public Arbol() {
        raiz = null;
    }

    public void insertarNodo(int valorInsertar) {
        if (raiz == null) {
            raiz = new NodoArbol(valorInsertar);
        } else {
            raiz.insertar(valorInsertar);
        }
    }

    public void recorridoPreorden() {
        ayudantePreorden(raiz);
    }

    private void ayudantePreorden(NodoArbol nodo) {
        if (nodo == null) {
            return;
        }
        System.out.printf("%d ", nodo.datos);
        ayudantePreorden(nodo.nodoIzq);
        ayudantePreorden(nodo.nodoDer);
    }

    public void recorridoInorden() {
        ayudanteInorden(raiz);
    }

    private void ayudanteInorden(NodoArbol nodo) {
        if (nodo == null) {
            return;
        }
        ayudanteInorden(nodo.nodoIzq);
        System.out.printf("%d ", nodo.datos);
        ayudanteInorden(nodo.nodoDer);
    }

    public void recorridoPostorden() {
        ayudantePostorden(raiz);
    }

    private void ayudantePostorden(NodoArbol nodo) {
        if (nodo == null) {
            return;
        }
        ayudantePostorden(nodo.nodoIzq);
        ayudantePostorden(nodo.nodoDer);
        System.out.printf("%d ", nodo.datos);
    }
}
------------
NodoArbol

Código: [Seleccionar]

package operaciones;

public class NodoArbol {

    NodoArbol nodoIzq;
    NodoArbol nodoDer;
    int datos;

    public NodoArbol(int datosNodo) {
        this.datos = datosNodo;
        nodoIzq = nodoDer = null;
    }

    public void insertar(int valorInsertar) {
        if (valorInsertar < datos) {
            if (nodoIzq == null) {
                nodoIzq = new NodoArbol(valorInsertar);
            } else {
                nodoIzq.insertar(valorInsertar);
            }
        } else if (valorInsertar > datos) {
            if (nodoDer == null) {
                nodoDer = new NodoArbol(valorInsertar);
            } else {
                nodoDer.insertar(valorInsertar);
            }
        }
    }
}


[Mac]

Me sigue saliendo el error no se que ocurre ?¿ 

[Ogramar]

Hola, ¿qué mensaje de error tienes con el árbol de String? Es decir, dices que "no se que sucede !" pero a qué te refieres exactamente.

Según comentas tienes el código de un árbol tipo int que te funciona perfectamente. ¿Puedes pegar ese código para verlo? Posiblemente a través de ese código se pueda ver qué es lo que te falla en el código con String.

Salu2

[Mac]

Bueno mira Ogramar Garcias por tu ayuda ...  ... en estos Días  he podido seguir investigando el Tema De Arboles ... Y he logrado entenderlo haciéndolo tipo Numérico...  Tipo (Int) pero quiero ahora pasarlo a Tipo (String) Caracteres el arbol ..

Bueno ahora tengo un inconveniente !!    en el método de ordenamiento de Inorden no me lo ordena de ese modo !! 

Quisiera que me orientaras por que no esta ordenándolos en el método Inorden 

[Ogramar]

Lo que te comentaba es que dices que has conseguido que te funcione bien con int, y que pegues el código con int que te funcione bien para poder verlo y hacer pruebas, compararlo y en base a esa comparación ver qué es lo que falla con los String 

[Mac]

Te entiendo ... entonces aquí  esta el código funcionando con el tipo de dato numérico tipo (Int) ... Hacerlo tipo (String) es el objetivo .. pues ya te lo coloque anteriormente ! 

Gracias por tu ayuda ! 

//////////////////////////////////////////////////////////

Arbol.java

Código: [Seleccionar]

//---------- CLASE ARBOL------------------
 class Arbol{
private NodoArbol raiz;

//contruir un arbol vacio
public Arbol()
{
raiz = null;
}

//insertar un nuevo nodo en el arbol de busqueda binaria
public synchronized void insertarNodo(int valorInsertar)
{
if(raiz == null)
raiz = new NodoArbol(valorInsertar); //crea nodo raiz

else
raiz.insertar(valorInsertar); // llama al metodo insertar
}

//--------------- EMPESAR EL RECORRIDO EN PREORDEN-----------------------
public synchronized void recorridoPreorden()
{
ayudantePreorden(raiz);
}
//metodo recursivo para recorrido en preorden

private void ayudantePreorden(NodoArbol nodo)
{
if (nodo == null)
return;

System.out.print(nodo.datos + " "); // mostrar datos del nodo
ayudantePreorden(nodo.nodoizquierdo); //recorre subarbol izquierdo
ayudantePreorden(nodo.nododerecho); //recorre subarbol derecho
}
   //--------------EMPEZAR RECORRIDO INORDEN-----------------------------------
public synchronized void recorridoInorden()
{
ayudanteInorden(raiz);
}

// metodo recursivo para recorrido inorden

private void ayudanteInorden(NodoArbol nodo)
{
if (nodo == null)
return;

ayudanteInorden(nodo.nodoizquierdo);
System.out.print(nodo.datos + " ");
ayudanteInorden(nodo.nododerecho);
}

//-----------------------------EMPEZAR RECORRIDO POSORDEN---------------------------------
public synchronized void recorridoPosorden()
{
ayudantePosorden(raiz);
}

//metodo recursivo para recorrido posorden

private void ayudantePosorden(NodoArbol nodo)
{
if (nodo == null)
return;

ayudantePosorden(nodo.nodoizquierdo);
ayudantePosorden(nodo.nododerecho);
System.out.print(nodo.datos + " ");
}

}//fin clase arbol


/////////////////////////////////////////////////////////////////////////

NodoArbol.java

Código: [Seleccionar]

//arbol en java inorden, posorden, preorden */

//definicion de la clase NodoArbol
class NodoArbol {

//miembros de acceso
NodoArbol nodoizquierdo;
int datos;
NodoArbol nododerecho;

//iniciar dato y hacer de este nodo un nodo hoja
public NodoArbol(int datosNodo)
{
datos = datosNodo;
nodoizquierdo = nododerecho = null; //el nodo no tiene hijos
}

//buscar punto de insercion  e insertar nodo nuevo
public synchronized void insertar(int valorInsertar)
{
//insertar en subarbol izquierdo
if (valorInsertar < datos){

//inserta nuevo nodoarbol
if (nodoizquierdo == null)
nodoizquierdo = new NodoArbol(valorInsertar);
else //continua recorriendo subarbol izquierdo
nodoizquierdo.insertar(valorInsertar);
}

//insertar nodo derecho
else if(valorInsertar > datos){

//insertar nuevo nodoarbol
if (nododerecho == null)
nododerecho = new NodoArbol(valorInsertar);
else //continua recorriendo subarbol derecho
nododerecho.insertar(valorInsertar);
}
} //fin del metodo insertar

} //fin clase nodoarbol
//////////////////////////////////////////////////////////////////////////////

PruebaArbol.java

Código: [Seleccionar]

//programa para probar la clase arbol
public class PruebaArbol {
public static void main(String args[])
{
Arbol arbol = new Arbol();
int valor;

System.out.println( "Insertando los siguientes valores: ");

//insertando 10 numeros aleatorios del 0 al 99 en el arbol
for (int i = 1; i<=10 ; i++)
{
valor = (int) (Math.random() * 100);
System.out.print(valor + " ");
arbol.insertarNodo(valor);
}

System.out.println("\n\nRecorrido preorden");
arbol.recorridoPreorden();

System.out.println("\n\nRecorrido inorden");
arbol.recorridoInorden();

System.out.println("\n\nRecorrido posorden");
arbol.recorridoPosorden();
}
}

[Ogramar]

A modo de recordatorio de árboles binarios:

Recorrido de árboles binarios:

    Preorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:

    Visite la raíz
    Atraviese el sub-árbol izquierdo
    Atraviese el sub-árbol derecho

    Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:

    Atraviese el sub-árbol izquierdo
    Visite la raíz
    Atraviese el sub-árbol derecho

    Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:

    Atraviese el sub-árbol izquierdo
    Atraviese el sub-árbol derecho
    Visite la raíz

Si hacemos una prueba con el árbol de enteros con el código que tú has puesto obtenemos por ejemplo lo siguiente:

Insertando los siguientes valores:
69 49 92 29 69 27 51 68 11 37

Recorrido preorden
69 49 29 27 11 37 51 68 92

Recorrido inorden
11 27 29 37 49 51 68 69 92

Recorrido posorden
11 27 37 29 68 51 49 92 69


El dibujo del árbol sería como éste:

            69
         49      92
      29      51
   27      37   
11


El único problema que he detectado en el árbol de enteros por el momento es que si tienes que insertar un valor que ya existía previamente no se inserta. Por eso en la serie anterior del ejemplo aparecen 10 valores como insertados pero sólo 9 valores en los recorridos. Si quisieras corregir esto, tendrías que cambiar alguno de los condicionales para introducir un igual, por ejemplo en vez de if (valorInsertar < datos){ sería if (valorInsertar <= datos){

Para la creación del árbol de enteros estás usando la siguiente estrategia: se crea el nodo raíz con un valor, por ejemplo 69. El siguiente número a insertar se compara con la raíz (69) y si es menor se inserta a la izquierda y si es mayor se inserta a la derecha. En el ejemplo 49 es menor y se inserta a la izquierda. Con el siguiente valor igual, se toma 92 y se compara con la raíz. Por ser mayor se inserta a la derecha. El siguiente valor es 27, se compara con la raíz y por ser menor se inserta a la izquierda. Como el nodo izquierdo ya está ocupado por el 49, se inserta sobre el 49. Se evalúa si es menor o mayor que 49, y por ser menor de 49 se inserta a la izquierda. El siguiente valor es 37. Se compara con la raíz (69) y por ser menor se inserta a la izquierda. Como está ocupado por 49 se compara con 49 y se inserta a la izquierda. Como está ocupado por 29 se compara con 29 y por ser mayor se inserta a la derecha... y así sucesivamente.

La cuestión es que con valores enteros insertas en el árbol basándote en comparaciones de mayor y menor para situar los elementos en un sitio u otro. Con Strings no puedes (o no se le ve sentido) hacer comparaciones mayor - menor, por tanto tienes que elegir otro criterio para realizar la inserción de elementos en el árbol. Puede ser longitud de palabras, orden alfabético, o simplemente crear un árbol balanceado (ir insertando por niveles, primero insertas dos hijos del nodo raíz; luego insertas dos hijos del nodo más a la izquierda y vas insertando nodos hasta que completas un nivel y vuelves a empezar por el siguiente nivel...).

¿Qué criterio es el que quieres usar con Strings?

[Mac]

Bueno primero que todo garcías por tu corrección gracias por tu ayuda y orientación ...

El criterio es que árbol Strings ordene en  Preorden - Inorden - Postorden nombres de personas que vaya ingresando ....

Gracias nuevamente por tu ayuda ! 

[Ogramar]

Hola, no me he explicado bien, lo que te quiero decir es que para poder ordenar recorrer con preorden, inorden y postorden primero tienes que definir cuál es el árbol que quieres recorrer.

Tu programar consta de dos partes:

a) Definir el árbol a recorrer

b) Recorrer el árbol en preorden, inorden o postorden.

Lo que hagas en la parte a) afecta al resultado que obtienes en la parte b).

Por ejemplo, no es lo mismo el árbol:

                      Juan

     Pedro                          Luis

Donde por ejemplo el recorrido preorden es: Juan, Pedro, Luis

Que el árbol:

                     Luis

    Pedro                            Juan

Donde el recorrido preorden es Luis, Pedro, Juan.

Aunque los datos sean los mismos, el recorrido varía en función de cómo estén ordenados los datos dentro del árbol.

Por eso es por lo que te preguntaba que con qué criterio quieres construir el árbol, ya que primero defines el árbol y después lo recorres. Y dependiendo de cómo lo hayas definido, los resultados del recorrido serán unos u otros.

Salu2

[Mac]

Pues bueno el criterio que tengo o que me han enseñado es primero (defines el árbol y después lo recorres) con ese criterio ! 

Y pues ahora mira esto ! que he hecho ..

Pero el recorrido de -------  > Recorrido Inorden no me sale en su orden !

[Ogramar]

Lo que te pregunto es con qué criterio defines el árbol. Por ejemplo supón que quieres trabajar con 3 cadenas que son Luis, Roberto y Maquiavelo.

Puedes definir 3*2 = 6 árboles:

          Luis
Roberto            Maquiavelo

O bien:

          Luis
Maquiavelo          Roberto           



O bien:

             Maquiavelo
Roberto              Luis

O bien:

             Maquiavelo
Luis                        Roberto

O bien:

             Roberto
Luis                    Maquiavelo

O bien:

             Roberto
Maquiavelo            Luis


El árbol que utilices depende del criterio que uses para construir el árbol. En el caso del árbol de enteros usabas un criterio que permitía que se generaran árboles no compensados (es decir, con mayor desarrollo por un lado p.ej. la izquierda que por el otro). En realidad, con el árbol de enteros, la forma del árbol dependía de si el nuevo valor a insertar era mayor o menor que el valor en la raíz..., en base a comparaciones numéricas se construía el árbol.

¿Cómo quieres construir el árbol de Strings? ¿Con qué criterio? Si no sabes el árbol que tienes, no puedes recorrerlo, de ahí que lo primero que trato de saber es cómo se define el árbol de partida, para luego poder recorrerlo.

Tú has indicado: defines el árbol y después lo recorres.

Lo que quiero saber es cómo lo defines.

Por ejemplo, supón que extraes estas palabras con este orden: casa, abedul, estruendo, noche, dia, espejo, roca, dirimir, ambulancia, hiperrealidad, amigo

¿Cuál es el árbol que defines y por qué (con qué criterio)?

[Mac]

Bueno mas o menos te voy entendiendo .... Pero desconocía la forma que tu tienes de ver la temáticas del árbol no la he aprendido a si !

 ¿Cuál es el árbol que defines y por qué (con qué criterio)?

Ayúdame tu con un ejemplo ! respondiendo a esa pregunta !

Te lo agradecería ! 

[Ogramar]

Ummmm ¿Si no sabes el árbol que defines, cómo sabes si el recorrido inorden está bien o está mal?

Piensa que el árbol lo puedes crear de muchas maneras. ¿Tiene que ser por orden alfabético? ¿Por orden de longitud de palabras? ¿Tiene que ser un árbol balanceado? ¿O te da igual cómo queden las palabras en el árbol y únicamente te interesa ver cómo hace el recorrido?

[Mac]

Me interesa mas el recorrido

Preorden: (raíz, izquierdo, derecho).
                 ---
Inorden: (izquierdo, raíz, derecho).
                              ----
Postorden: (izquierdo, derecho, raíz).
                                              ----

y la ubicación de la raíz.

si tienes algunos ejemplos de ordenamiento en alfabético , longitud, y arboles balanceados seria bueno saberlos !     

[Ogramar]

Aquí te paso el código, no lo he probado pero se supone que debería funcionar. Si lo pruebas y funciona ya puedes mejorarlo para interaccionar con el usuario y no introducir palabras predefinidas en el árbol.

La idea es la siguiente: en el método public synchronized void insertar(String valorInsertar) de la clase NodoArbol insertas la palabra a la izquierda si es de longitud menor que la raíz, o a la derecha si es de longitud (número de caracteres).

Fíjate en la línea if (valorInsertar.length() <= datos.length())

tienes un <= para que si la palabra es de longitud igual, se inserte a la izquierda (este era un fallo que tenías en el código con los enteros).

Una vez construido el árbol con este criterio, debería hacerse el recorrido igual que lo hacía con los enteros.

Clase NodoArbol:

Código: [Seleccionar]

//arbol en java inorden, posorden, preorden */

//definicion de la clase NodoArbol
class NodoArbol {

    //miembros de acceso
    NodoArbol nodoizquierdo;
    String datos;
    NodoArbol nododerecho;

    //iniciar dato y hacer de este nodo un nodo hoja
    public NodoArbol(String datosNodo)
    {
        datos = datosNodo;
        nodoizquierdo = nododerecho = null; //el nodo no tiene hijos
    }

    //buscar punto de insercion  e insertar nodo nuevo
    public synchronized void insertar(String valorInsertar)
    {
        //insertar en subarbol izquierdo
        if (valorInsertar.length() <= datos.length()){

            //inserta nuevo nodoarbol
            if (nodoizquierdo == null)
                nodoizquierdo = new NodoArbol(valorInsertar);
            else //continua recorriendo subarbol izquierdo
                nodoizquierdo.insertar(valorInsertar);
        }

        //insertar nodo derecho
        else if(valorInsertar.length() > datos.length()){

            //insertar nuevo nodoarbol
            if (nododerecho == null)
                nododerecho = new NodoArbol(valorInsertar);
            else //continua recorriendo subarbol derecho
                nododerecho.insertar(valorInsertar);
        }
    } //fin del metodo insertar

} //fin clase nodoarbol

Clase Arbol

Código: [Seleccionar]

//---------- CLASE ARBOL------------------
class Arbol{
    private NodoArbol raiz;

    //contruir un arbol vacio
    public Arbol()
    {
        raiz = null;
    }

    //insertar un nuevo nodo en el arbol de busqueda binaria
    public synchronized void insertarNodo(String valorInsertar)
    {
        if(raiz == null)
            raiz = new NodoArbol(valorInsertar); //crea nodo raiz

        else
            raiz.insertar(valorInsertar); // llama al metodo insertar
    }

    //--------------- EMPESAR EL RECORRIDO EN PREORDEN-----------------------
    public synchronized void recorridoPreorden()
    {
        ayudantePreorden(raiz);
    }
    //metodo recursivo para recorrido en preorden

    private void ayudantePreorden(NodoArbol nodo)
    {
        if (nodo == null)
            return;

        System.out.print(nodo.datos + " "); // mostrar datos del nodo
        ayudantePreorden(nodo.nodoizquierdo); //recorre subarbol izquierdo
        ayudantePreorden(nodo.nododerecho); //recorre subarbol derecho
    }
    //--------------EMPEZAR RECORRIDO INORDEN-----------------------------------
    public synchronized void recorridoInorden()
    {
        ayudanteInorden(raiz);
    }

    // metodo recursivo para recorrido inorden
    private void ayudanteInorden(NodoArbol nodo)
    {
        if (nodo == null)
            return;

        ayudanteInorden(nodo.nodoizquierdo);
        System.out.print(nodo.datos + " ");
        ayudanteInorden(nodo.nododerecho);
    }

    //-----------------------------EMPEZAR RECORRIDO POSORDEN---------------------------------
    public synchronized void recorridoPosorden()
    {
        ayudantePosorden(raiz);
    }

    //metodo recursivo para recorrido posorden
    private void ayudantePosorden(NodoArbol nodo)
    {
        if (nodo == null)
            return;
        ayudantePosorden(nodo.nodoizquierdo);
        ayudantePosorden(nodo.nododerecho);
        System.out.print(nodo.datos + " ");
    }

}//fin clase arbol

Clase PruebaArbol

Código: [Seleccionar]

//programa para probar la clase arbol
public class PruebaArbol {
    public static void main(String args[])
    {
        Arbol arbol = new Arbol();
       

        System.out.println( "Insertando los siguientes valores:"+
        "camino, abedul, estruendo, noche, dia, espejo, roca, dirimir,"+
        "ambulancia, hiperrealidad, amigo");

        arbol.insertarNodo("camino");
        arbol.insertarNodo("abedul");
        arbol.insertarNodo("estruendo");
        arbol.insertarNodo("noche");
        arbol.insertarNodo("dia");
        arbol.insertarNodo("espejo");
        arbol.insertarNodo("roca");
        arbol.insertarNodo("dirimir");
        arbol.insertarNodo("ambulancia");
        arbol.insertarNodo("hiperrealidad");
        arbol.insertarNodo("amigo");


        System.out.println("\n\nRecorrido preorden");
        arbol.recorridoPreorden();

        System.out.println("\n\nRecorrido inorden");
        arbol.recorridoInorden();

        System.out.println("\n\nRecorrido posorden");
        arbol.recorridoPosorden();
    }
}

Ya nos contarás...

Salu2

[Mac]

Orgramar  Muchas gracias ... pues bueno veo que si el recorrido se recorre como debe ser .. ahora pues ahora me gustaría como saber el Nivel y la altura de el arbol !

[Ogramar]

¿Qué es el nivel del árbol?

[Mac]

Bueno Mira

Esto lo quisiera implementar en mi arbol de numero enteros  ...

Donde El Nivel seria Los nodos del arbol ... en la imagen que adjunto los que están encerrados en los círculos negros

Don la altura seria los subarboles donde paso la linea negra ...

Me corregirás si no es a si ! 

[Ogramar]

Yo lo que diría es que ese árbol tiene 9 nodos (o 9 elementos) y que cada nodo está en un nivel. Si empiezas desde cero, podríamos decir que el nodo 2 está en el nivel 0, los nodos 7 y 5 en el nivel 1, los nodos 2, 6 y 9 en el nivel 2 y los nodos 5, 11 y 4 en el nivel 3.

Si empiezas desde uno podríamos decir que el nodo 2 está en el nivel 1, los nodos 7 y 5 en el nivel 2, los nodos 2, 6 y 9 en el nivel 3 y los nodos 5, 11 y 4 en el nivel 4.

Como dice en la imagen, podríamos llamar a la altura = máxima nivel - 1, es decir, 4-1 = 3

La altura podríamos verla como el número de escalones, partiendo del nivel del suelo el nodo raíz estaría en el suelo y cada nodo en un nivel siguiente estaría en un nuevo escalón. Por eso tendríamos 4 niveles (suelo, escalón 1, 2 y 3) y altura 3 (3 escalones).

Pero decir que nivel es el número de nodos del árbol no parece que tenga mucho sentido 

[Mac]

Te entiendo perfectamente sobre la Altura pero me queda una duda ! !

Pero decir que nivel es el número de nodos del árbol no parece que tenga mucho sentido 

Entonces cual es el nivel de un árbol 

----------------------------------------------------------------------------------------