Autor Tema: Arboles binarios en Java recursividad obtener LinkedList de nodos hoja código  (Leído 10860 veces)

jeison

  • Sin experiencia
  • *
  • APR2.COM
  • Mensajes: 1
    • Ver Perfil
Hola necesito un metodo que retorne en un LinkedList los nodos hoja de un árbol binario, sin embargo no se me ocurre como puedo recorrer cada nodo del arbol para preguntar si es o no hoja, tengo este metodo que recorre el arbol y guarda sus elementos en un String pero no se como puedo utilizarlo
Código: [Seleccionar]
private String preOrder(BinaryNode node) {
        String temp = "";

        if (node != null) {

            temp += node.element + "\n";
            temp += preOrder(node.left);
            temp += preOrder(node.right);
        }
        return temp;
    }
« Última modificación: 11 de Julio 2018, 20:12 por Ogramar »

Alex Rodríguez

  • Moderador Global
  • Experto
  • *******
  • Mensajes: 2053
    • Ver Perfil
Re:Arboles Binarios en java
« Respuesta #1 en: 08 de Julio 2018, 13:14 »
Hola, para escribir en los foros se recomienda seguir las indicaciones que se dan en https://aprenderaprogramar.com/foros/index.php?topic=1460.0

En tu caso falta mucho código, tan solo has puesto un método. En este hilo se tratan los árboles binarios, quizás te sea de ayuda: https://aprenderaprogramar.com/foros/index.php?topic=1428.0

Saludos

Kabuto

  • Moderador Global
  • Experto
  • *******
  • Mensajes: 866
    • Ver Perfil
Re:Arboles Binarios en java
« Respuesta #2 en: 10 de Julio 2018, 22:11 »
Hola,

Nunca habia trabajado con arboles binarios en programación, así que esta consulta ha despertado mi curiosidad y he creado mi propio código para representar un Arbol Binario, obteniendo también una posible solución a tu consulta sobre obtener una LinkedList con los "nodos hoja".
Aunque claro, la solución que yo doy está adaptada a mi código, que podría ser radicalmente distinto al tuyo y a los tipos de clases que estes utilizando.
Aún así, quizás te sirva al menos de inspiración.

En mi caso, creo que he conseguido una representación bastante simple de un arbol.
Aquí la auténtica magia está en hacer buen uso de la "recursividad" para poder viajar a través de los nodos del arbol obteniendo la información que podamos necesitar.

Tan solo he necesitado tres clases: Nodo, Arbol y una clase Test con el main() para crear el arbol y ver si consigo datos correctos de él.

Para comprobar si mi código funciona he tomado como referencia los valores de ejemplo que puso el maestro Ogramar en el otro post que habéis enlazado.


Con esta serie de prueba (60 75 66 85 42 14 73 72 2 54) el árbol que genera sería este:



Así es fácil comprobar si estoy obteniendo los resultados correctos.

Una vez creado el arbol, le pido que me informe de la altura (empezando a contar desde 0 para el "nivel raiz" ), de la cantidad de nodos totales, cantidad de nodos hoja y una lista de los valores de los nodos hoja obtenidos mediante una LinkedList.
Aparentemente parece que obtengo los resultados correctos en la consola de salida:
Citar
Altura del arbol(1er nivel es 0): 4
Cantidad de nodos: 10
Cantidad de hojas: 4
Los valores de los nodos hoja son : 2 54 72 85


Así que doy por hecho que mi código es correcto, y eso que la "recursividad" es algo que tengo bastante verde..., de hecho el método para contar "nodos hoja" no esperaba que funcionase tal y como lo he escrito je je..

Bien, aquí os dejo mis clases para que las probéis, comentéis y a ver si hay suerte y pueden seros útiles.

La clase Nodo es la más importante. Sus atributos son un valor entero y dos objetos más de la misma clase Nodo, es decir, dos "nodos hijos", los cuales se inician como null al principio y luego se instanciarán en nuevos nodos si el "nodo padre" recibe el valor adecuado.
Lo realmente importante, son los métodos, que como dije antes con la magia de la recursividad se consiguen maravillas con unas pocas lineas de código.
Lo cierto es que casi hay más lineas de comentarios documentando la clase, que lineas de código....

Clase Nodo:
Código: [Seleccionar]
package arbol;

import java.util.LinkedList;

public final class Nodo {

private int valor;
private Nodo izq;
private Nodo der;

public Nodo(int valor) {
this.valor = valor;
izq = null;
der = null;
}

public int getValor() {
return valor;
}

/**
* Este es el método más importante ya que es donde se decide a que lado se ramificará
* el nodo segun el valor recibido y a que altura del arbol se situará.<br>
* Por ello este metodo recibe dos argumentos: el valor para un nuevo nodo y la altura incial.<br>
* Esta altura se irá incrementando según descendemos por el arbol binario hasta poder crear un nuevo nodo
* con el valor proporcionado. La altura incrementada será retornada para así poder controlar hasta que altura
* hemos tenido que descender y así la clase <b>Arbol</b> tendrá un control en tiempo real de su altura actual.<br><br>
* El proceso consiste en comparar el valor recibido con el valor de este nodo: si es menor se ramificará a la izquierda y
* si es mayor se ramificará a la derecha. En el caso de que el valor recibido sea IGUAL al del nodo actual, no se creará
* ningún nodo nuevo.<br><br>
* Al ramificar a un lado u otro, lo que hacemos es preguntar si por ese lado hay ya un nodo o no.<br>
* Si no lo hay (encontramos un null en lugar de un nodo), creamos un nuevo <b>Nodo</b> y devolvemos la <i>altura</i> incrementada.<br>
* Si existe ya un <b>Nodo</b>, hacemos una llamada recursiva de este método pasando el valor y también la <i>altura</i> incrementada.<br>
* <br>De este modo, el valor irá pasando de nodo en nodo de manera recursiva hasta encontrar un sitio donde colocarse y retornaremos
* el valor de la altura incrementada según la cantidad de niveles (llamadas recursivas) que hayamos avanzado.
* @param v Valor recibido para crear un nuevo nodo.
* @param altura La altura del arbol en la que nos encontramos intentando crear un nuevo nodo. Este valor se incrementará según se
* desciende por el arbol hasta encontrar un hueco donde crear el nodo.
* @return Valor de la altura hasta que hemos tenido que descender hasta conseguir crear un nuevo nodo.
*/
public int recibeValor(int v, int altura) {
if (valor > v) {
if (izq == null)
{
izq = new Nodo(v);
return ++altura;//Puesto que se ha creado un nuevo nodo, se incrementa la altura recibida inicialmente
}
else
return izq.recibeValor(v, ++altura);//Llamada recursiva, imcrementamos la altura ya que pasamos al siguiente nivel del arbol
}
else if (valor < v) {
if (der == null)
{
der = new Nodo(v);
return ++altura;
}
else
return der.recibeValor(v, ++altura);
}
else
return altura;//En el caso de recibir un valor IGUAL al del nodo actual, cuyo caso no se crea nuevo nodo
}

/**
* Este metodo "viaja" a través del arbol contando los nodos existentes.<br>
* Para ello comprueba si existen o no "nodos hijos" a izquierda y derecha.
* Si encuentra nodos hijos, hace una llamada recursiva de este método para seguir
* buscando nodos por cada ramificación donde existan nodos.
* @return Cantidad de nodos encontrados a partir del nodo donde se invoca al método.
*/
public int cuentaNodos() {
if (izq == null && der == null)
return 0;//No hay nodos, es una hoja
else if (izq != null && der != null)
return 2 + izq.cuentaNodos() + der.cuentaNodos();//Tiene 2 nodos. Sumamos 2 + las nodos que encontremos a continuacion
else if (izq != null && der == null)
return 1 + izq.cuentaNodos(); //Solo 1 nodo, el izquierdo. Sumamos 1 más los nodos que vayamos encontrando
else
return 1 + der.cuentaNodos();//Solo 1 nodo, el derecho.

}

/**
* Este metodo "viaja" a través del arbol contando las "hojas" existentes.<br>
* Una "hoja" es un nodo del cual no cuelga ningún otro nodo, por lo cual usaremos
* una variable que se irá pasando recursivamente a traves de las ramificaciones hasta encontrar
* hojas que será cuando se incremente el valor de la variable contador.<br>
* Esta variable contador se pasa como argumento desde la clase <b>Arbol</b> incializada a 0 y
* finalmente es recogida con todos los incrementos ocurridos al encontrar hojas.
* @param hojas Contador de hojas que se va pasando recursivamente por cada nodo.
* @return Cantidad de hojas encontradas desde el nodo donde se ha invocado el método.
*/
public int cuentaHojas(int hojas) {
if (izq == null && der == null)
return ++hojas;//No hay nodos, es una hoja
else if (izq != null && der != null)
return izq.cuentaHojas(hojas) + der.cuentaHojas(hojas);
else if (izq != null && der == null)
return izq.cuentaHojas(hojas);
else
return der.cuentaHojas(hojas);
}

/**
* Este metodo "viaja" a través del arbol recopilando el valor de los "nodos hoja" existentes.<br>
* EStos valores se almacenan en una LinkedList invocada desde la clase <b>Arbol</b> e irá viajando
* de manera recursiva por todas las ramificaciones del arbol buscando "nodos hoja" y obteniendo su valor.
* @param lista Listado de valores de los "nodos hoja"
*/
public void listarHojas(LinkedList<Integer> lista) {
if (izq == null && der == null) {
lista.add(valor);
}
else if (izq != null && der != null)
{
izq.listarHojas(lista);
der.listarHojas(lista);
}
else if (izq != null && der == null)
izq.listarHojas(lista);
else
der.listarHojas(lista);
}
}

El método recibeValor() es el más interesante. Es quién, cuando el arbol recibe un nuevo valor entero, decide por donde ha de ramificarse el arbol y hasta que nivel para crear el nuevo nodo.
Además para facilitar la tarea de conocer la "altura" del arbol, este método informa hasta que nivel ha descendido para poder crear el nodo.
Este dato lo recibe la clase Arbol y así cada vez que se crea un nuevo nodo, sabe si su altura ha aumentado o no.

Los siguientes métodos de la clase Nodo son muy similares en estructura, solo cambia el tipo de operacion a realizar.


Pasamos a la Clase Arbol
Código: [Seleccionar]
package arbol;

import java.util.LinkedList;

public final class Arbol {

private Nodo raiz;
private int altura;

public Arbol(int valor) {
raiz = new Nodo(valor);
altura = 0;
}

public int getAltura() {
return altura;
}

public void insertarValor(int valor) {
int alturaAlcanzada = raiz.recibeValor(valor, 0);//El control de altura comienza desde 0
/*
* Actualizamos la altura del arbol según el valor recibido.
* Si para crear el nuevo nodo se ha alcanzado una altura superior
* a la altura actual del arbol, es que el arbol "ha crecido" y se ha de actualizar.
*/
if (alturaAlcanzada > altura)
altura = alturaAlcanzada;
}

public int contarNodos() {
return 1 + raiz.cuentaNodos();
}

public int contarHojas() {
return raiz.cuentaHojas(0);
}

public LinkedList<Integer> getListadoHojas() {
LinkedList<Integer> listadoHojas = new LinkedList<Integer>();
raiz.listarHojas(listadoHojas);
return listadoHojas;
}
}

Clase muy, muy simple.
Sus atributos son un "nodo raiz" (que a su vez contiene subnodos que se irán ramificando) y un entero para controlar en todo momento la altura actual del arbol.
Este atributo no es estrictamente necesario, pero simplifica el hecho de obtener después este dato.

Sus métodos no hacen gran cosa, tan solo pedir al objeto Nodo que haga el "trabajo duro" y retornar los datos obtenidos.

El método getListadoHojas(), junto con el método listarHojas() de la clase Nodo,  son quienes dan una posible solución a obtener una LinkedList con los valores de los "nodos hoja".

Por último la clase Test:
Código: [Seleccionar]
package arbol;

import java.util.LinkedList;

public final class Test {

private static Arbol arbol;
private final static int[] valores = {60, 75, 66, 85, 42, 14, 73, 72, 2, 54};

public static void main(String[] args) {

//Creamor arbol con el valor inicial
arbol = new Arbol(valores[0]);
//Insertamos siguientes valores
for (int i = 1; i < valores.length; i++)
arbol.insertarValor(valores[i]);

System.out.println("Altura del arbol(1er nivel es 0): " + arbol.getAltura());
System.out.println("Cantidad de nodos: " + arbol.contarNodos());
System.out.println("Cantidad de hojas: " + arbol.contarHojas());
System.out.print("Los valores de los nodos hoja son : ");
LinkedList<Integer> listaHojas = arbol.getListadoHojas();
for (Integer valor: listaHojas)
System.out.print(valor + " ");

}

}

Se declara un objeto Arbol y un vector con los valores enteros que usaremos para crear nodos a modo de prueba, que son los valores de la imagen publicada anteriormente.

Una vez creado el Arbol, le pedimos los datos que queremos conocer y podemos comprobar que son correctos, si nos fijamos en la imagen con los valores de muestra.

Un saludo.
NO respondo dudas por mensaje privado
Publicando vuestras dudas en el foro público conseguimos:
- Que más gente aporte respuestas mejores o complementarias.
- Que otras personas puedan aprender de vuestras dudas.

Mejor en PÚBLICO que en privado. Gracias

Ogramar

  • Moderador Global
  • Experto
  • *******
  • Mensajes: 2646
    • Ver Perfil
Gracias por llamarme "maestro" Kabuto, yo creo que el maestro eres tú  ;) Todo este tema de los árboles es muy interesante pues son modelos matemáticos con aplicaciones prácticas muy interesantes. De hecho hay muchas clases del API Java que son implementaciones de árboles, no conozco el detalle de las implementaciones pero estoy pensando en TreeMap y otras. Todo esto se expande hacia otra cosa igualmente interesante como son estructuras de datos como montículos, pilas y colas, etc. Hay estructuras de datos ordenadas como montículos ordenados que pueden ser bastante eficientes. A quien le interese, ahí tiene materia para entretenerse...

Salu2

Kabuto

  • Moderador Global
  • Experto
  • *******
  • Mensajes: 866
    • Ver Perfil
La verdad es que es muy interesante.

Y también me fascina el potencial de la Recursividad.

De hecho, aún sigo dándole vueltas a este método:
Código: [Seleccionar]
public int cuentaHojas(int hojas) {
if (izq == null && der == null)
return ++hojas;//No hay nodos, es una hoja
else if (izq != null && der != null)
return izq.cuentaHojas(hojas) + der.cuentaHojas(hojas);
else if (izq != null && der == null)
return izq.cuentaHojas(hojas);
else
return der.cuentaHojas(hojas);
}

Está escrito por mí, y funciona perfectamente... pero cuando lo escribí estaba seguro de que no iba a funcionar. De que no podía ser tan fácil.
Este método siempre se invoca desde la clase Arbol sobre el nodo raiz, pasándole un int con valor 0.
Al ser un tipo de dato primitivo, y que por lo tanto se pasa "por valor" y no "por referencia", estaba convencido que daba igual por cuantas ramificaciones viajase.
Al final me llegaría retornado un valor 1, ya que al encontrar una "hoja", el valor se incrementa.
Pero el resto de "hojas" no saben (o eso creo...) que las otras "hojas" han incrementado ese valor.
Cuando una "hoja" incrementa, retorna el valor, no lo transfiere a otras invocaciones del método para que vayan acumulándose los incrementos.
Así que en teoría todas las "hojas" existentes reciben un 0 y lo incrementan en 1.
Por esto pensaba que iba a recibir un 1 sin importar cuantas hojas hubiesen realmente.

Pero no..., resulta que recibimos todos los incrementos debidamente acumulados.... y aún no estoy seguro de por qué.... xDD
Intento hacer una "traza mental" de este código pero no soy capaz, es dificil con tantas llamadas recursivas. Además trabajo varias horas al dia y me deja bastante incapacitado mentalmente je je...

A ver si el domingo con calma, me lo miro bien como es el proceso que se lleva a cabo con este código.

¿Es quizás que la variable int se pasa "por valor" en la primera invocación inicial que hacemos en el nodo raiz, pero a partir de ahí el resto de invocaciones recursivas lo reciben "por referencia"?
No se si tiene sentido esto que digo... Me voy a dormir.
« Última modificación: 12 de Julio 2018, 01:06 por Kabuto »
NO respondo dudas por mensaje privado
Publicando vuestras dudas en el foro público conseguimos:
- Que más gente aporte respuestas mejores o complementarias.
- Que otras personas puedan aprender de vuestras dudas.

Mejor en PÚBLICO que en privado. Gracias

Ogramar

  • Moderador Global
  • Experto
  • *******
  • Mensajes: 2646
    • Ver Perfil
Tal como dices la recursividad tiene un gran potencial, pero a su vez grandes riesgos. Uno de los riesgos es precisamente lo difícil que es de seguir la traza de ejecución con métodos recursivos. La mayoría de la gente terminamos perdiéndonos, lo cual es bastante normal. Diría además que la mayoría de los programadores rehuyen en cierta medida de la recursividad por la dificultad para trazar y llegar a conclusiones sobre lo que hacen estos métodos. No obstante, tiene grandes aplicaciones y algunas de uso frecuente, por ejemplo para recorrer estructuras de directorios e ir alcanzando todas las carpetas y ficheros (que si nos fijamos bien no deja de ser una estructura de árbol, no binario, pero árbol al fin y al cabo).

Respecto a cómo pasan los parámetros en Java puede ser interesante leer esto, según lo cual todo parámetro sea tipo primitivo u objeto pasa por valor (aunque habría matices a comentar): https://www.aprenderaprogramar.com/foros/index.php?topic=49.msg2892#msg2892

Voy a intentar seguir lo que sería la traza de ejecución para un árbol con un nodo raíz y dos nodos hoja hijos. Cada llamada al método la voy a llamar ref.

Llamas al método con el parámetro 0 llamada ref1 y como izq es distinto de null y derecha es distinto de null, te devuelve una llamada ref2 con parámetro a 0 + llamada ref3 con parámetro 0. La llamada ref2 concluye con la condición base: izquierda y derecha son null, y por tanto su return devuelve 1. La llamada ref3 concluye de la misma manera, y también devuelve 1. Ahora se resuelve la llamada ref1 que estaba pendiente de tener los resultados de ref2 y ref3 para devolver su propio resultado, y el resultado que devuelve es 1+1=2 es decir, que hay 2 hojas.

Creo que quizás es útil ver las propias llamadas recursivas como un árbol (aquí ya veo árboles por todos lados), donde en la raíz tienes ref1 (+) que sería un nodo suma de sus hijos. Sus hijos son ref2 y ref3 que valen 1. De ahí que el nodo ref1 termine valiendo 2.

Voy a intentarlo con un árbol binario que tiene el nodo raíz, dos nodos hijo, ramificando el izquierdo a su vez en dos nodos hojas, y siendo el nodo derecho del raíz hoja directamente.

Aquí partimos de la llamada ref1 que deriva a ref2 + ref3. ref3 devuelve un 1, mientras que ref2 devuelve ref4+ref5. Como resultado de ref4 + ref5 obtenemos 1+1. Esto se suma al resultado de ref2 que es 1. Finalmente en ref1 suma 2 más 1 obteniendo 3, que es el número de nodos hoja que tenemos. La cuestión aquí es que el resultado ref1 queda pendiente de poder operarse hasta que se tengan resultados para ref2 y ref3. A su vez ref2 queda pendiente de operarse hasta que se tengan resultados de ref4 y ref5...

Todo pasa por valor: al final lo que terminas haciendo son sumas. Partes de los resultados base de un nodo hoja: un 1. El resto de resultados se van obteniendo agregando esos resultados base.

Desde luego todo esto es complejo de ver y a lo mejor dentro de un rato no estoy satisfecho con esta explicación, pero por lo menos se ha intentado ;)

Salu2

Kabuto

  • Moderador Global
  • Experto
  • *******
  • Mensajes: 866
    • Ver Perfil
Para trazar esto.... se necesita papel, lápiz y bebidas azucaradas para tener combustible en la sesera ja ja...

Viendo tu explicación, ahora me doy cuenta de lo evidente.
Que en cuanto un arbol tiene al menos dos hojas, entonces se dará esta condicion:
Código: [Seleccionar]
else if (izq != null && der != null)
return izq.cuentaHojas(hojas) + der.cuentaHojas(hojas);
y se retornará, al menos, una suma de resultados: 1 + 1.

Si hay 3 hojas, se retornaría una suma recursiva (los parentesis representan la suma recursiva):
 (1 + 1) + 1 si la ramificacion más profunda está por la izquierda,
 1 + (1 + 1) si estuviese por la derecha.

Si hay 4 hojas: (1 + 1) + (1 + 1)

5 hojas: ((1 + 1) + 1) + (1 + 1) si la ramificación más profunda estuviese a la izquierda

etc...

En definitiva, excepto cuando solo hay una hoja en todo el arbol, a partir de dos o más hojas siempre tendremos sumas y más sumas recursivas.

De ahí que no se cumpla mi inicial temor de que solo iba a recibir un 0 incrementado en 1.
Yo no veía en qué momento ese 0 incrementado en 1, llegaría a ser un 1 incrementado a 2, y luego un 2 incrementado a 3, etc....
Y es que esto no ocurre nunca, y de hecho ¡¡no hace falta que ocurra!!
Lo que recibimos son una suma de muchos 0 incrementados en 1.

Y por ello, el método funciona perfectamente, ¡¡oh yeah!!

De hecho funciona así precisamente porque el dato primitivo se está pasando "por valor"
Si estuviese pasandose "por referencia", ocurriría un despropósito.
Y lo acabo de comprobar modificando los metodos para en lugar de pasarle un 0 como int primitivo, pasarle un vector int[] que contiene el 0.

Cambio en clase Nodo:
Código: [Seleccionar]
public int cuentaHojas(int[] hojas) {
if (izq == null && der == null)
return ++hojas[0];//No hay nodos, es una hoja
else if (izq != null && der != null)
return izq.cuentaHojas(hojas) + der.cuentaHojas(hojas);
else if (izq != null && der == null)
return izq.cuentaHojas(hojas);
else
return der.cuentaHojas(hojas);
}

Cambio en clase Arbol:
Código: [Seleccionar]
public int contarHojas() {
int[] v = {0};
return raiz.cuentaHojas(v);
}

De este modo, el conteo de hojas falla y me dice que hay 10, en lugar de 4.


Y yo que ayer pensaba que quizás me funcionaba porque de algún modo el 0 int primitivo estaba pasándose "por referencia"...

Vaya giros inesperados da la vida ja ja ja ...

Muy didáctico ha sido este ejercicio. Un saludo.
NO respondo dudas por mensaje privado
Publicando vuestras dudas en el foro público conseguimos:
- Que más gente aporte respuestas mejores o complementarias.
- Que otras personas puedan aprender de vuestras dudas.

Mejor en PÚBLICO que en privado. Gracias

 

Sobre la educación, sólo puedo decir que es el tema más importante en el que nosotros, como pueblo, debemos involucrarnos.

Abraham Lincoln (1808-1865) Presidente estadounidense.

aprenderaprogramar.com: Desde 2006 comprometidos con la didáctica y divulgación de la programación

Preguntas y respuestas

¿Cómo establecer o cambiar la imagen asociada (avatar) de usuario?
  1. Inicia sesión con tu nombre de usuario y contraseña.
  2. Pulsa en perfil --> perfil del foro
  3. Elige la imagen personalizada que quieras usar. Puedes escogerla de una galería de imágenes o subirla desde tu ordenador.
  4. En la parte final de la página pulsa el botón "cambiar perfil".