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:
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: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 Arbolpackage 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: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.
Tema: Arboles binarios en Java recursividad obtener LinkedList de nodos hoja código (Leído 14309 veces)
RSS -
WAP2