Duda al definir un árbol n-ario

[samurai_7]

hola,
hace poco empecé con el mundo de java y estoy trabajando ahora con árboles. Estoy investigando el tema de los los árboles n-arios y he visto la siguiente definición por internet.

class Nodo{

int valor;
ArrayList <Nodo> hijos;


Nodo(int new data) {
hijos = new ArrayList <Nodo> ();
valor = new data;
}
}


En la primera parte define la clase nodo como una estructura con un int, y un array de Nodos, de acuerdo, ¿pero por qué hace la segunda parte? Nodo (int new data..) imagino que será quizás el operador para meter el valor en el nodo, pero no entiendo porqué lo hace dentro de la estructura, ni tampoco lo que hace.

[Profesor_Falken]

Buenas

Eso es el constructor de la clase y lo unico que hace es inicializar el nodo.
Esto:
Nodo(int new data) {

No existe ni compila en Java.

Un saludo

[samurai_7]

Gracias!
la cosa es que lo veo desde un video de youtube, y el programa compila. De todas formas hice mi versión y parece que va bien. ¿Me lo podrías confirmar?

public class nodoN {

private int valor;
private ArrayList <nodoN> hijos = new ArrayList <nodoN>();
private nodoN padre;
private nodoN raiz;

public void nodoN(){
valor=0;
hijos = new ArrayList<nodoN>();
padre=null;
}

public void nodoN(int v){
valor = v;
hijos.add(null);
padre = null;
}

public void setRaiz (nodoN n)
{
raiz = n;
}

public void agregarHijo(nodoN nodo, nodoN padre)
{
if(padre==null) {setRaiz(nodo);}
hijos.add(nodo);
nodo.padre=padre;

}


}

[Profesor_Falken]

Buenas,

Compila porque en ninguna parte estás haciendo lo que ponías al principio:

Nodo(int new data)

En principio parece correcto, pero no se porqué el método agregarHijo recibe un parámetro padre. Se supone que el padre es el nodo (this) al que le agregas el hijo ¿no?

Un saludo

[Olbapk]

Hola,
imagino que será para mantener el nivel conectado, e ir pudiendo subir y bajar, ¿no?.

Saludos.

[samurai_7]

Hola,
exactamente, el padre será donde agrego el hijo, pero es una forma de enganchar los nodos para poder ir subiendo de nivel cuando me interese sin necesidad de empezar de nuevo. ¿no lo ves necesario?.

Un saludo.

[Profesor_Falken]

Buenas,

Yo no digo que un nodo no deba tener un padre. Eso es correcto.

Lo que digo es que el método debería ser más bien así:

Código Java:

public void agregarHijo(nodoN nodo)
{
hijos.add(nodo);
nodo.padre=this;
}
 

Por otro lado no es necesario hacer la gestión del raiz explícitamente. Elemento raíz será todo aquel que no tenga padre.


Un saludo

[samurai_7]

hola,
había pensando en para la función, darle 2 parámetros, la estructura nodo actual, (el registro de datos) la cual quiero introducir y que contiene los datos que quiero y luego el nodo padre que sería el nodo actual que indica mi posición.

Imagino que tu haces lo mismo con tu función, pero no estoy seguro de entender lo que haces:
1)hijos.add(nodo); no le faltaría indicar donde lo estás metiendo, a que hijo se lo asigna? en que nivel?

2)nodo.padre=this; a "this" le faltaría algo no?, estás igualando el padre al nodo?

Disculpa pero no lo entiendo.

Lo que si he modificado mi función de instertar ya que me he dado cuenta de que si el actual (padre) es nulo, no hay arbol, por o que solo apunto raiz a dicho nada, y ya no es necesario hacer el resto.

public void agregarHijo(nodoN nodo, nodoN padre)
{
if(padre==null) {setRaiz(nodo);}

else
{
hijos.add(nodo);
nodo.padre=padre;
}
}

[Profesor_Falken]

Buenas,

Estás mezclando programación estructurada con programación orientada a objetos.

1)hijos.add(nodo); no le faltaría indicar donde lo estás metiendo, a que hijo se lo asigna? en que nivel?

No tengo que indicárselo. Estoy añadiendo un hijo al propio nodo.

2)nodo.padre=this; a "this" le faltaría algo no?, estás igualando el padre al nodo?

Cuando a un nodo le añado un hijo, este nodo es padre de dicho hijo.

Te pongo la clase nodo tal y como la veo yo:

Código Java:

public class nodoN {
 
    private int valor;
    private List <nodoN> hijos = new ArrayList <nodoN>();
    private nodoN padre;
 
    public void nodoN(){
        nodoN(0);
    }
 
    public void nodoN(int v){
        valor = v;
    }
 
    public boolean isRaiz (){
        return this.padre == null;
    }
 
    public void agregarHijo(nodoN nodo) {
        hijos.add(nodo);
        nodo.padre=this;
    }
 
    public List<NodoN> getHijos() {
        return hijos;
    }
 
   public int getValue() {
       return value;
   }
}
 

Para utilizarlo y hacer una estructura como esta:
raiz
--Nodo1
----Nodo3
--Nodo2
---Nodo4
---Nodo5
-----Nodo6

Código Java:

//Definimos nodos
NodoN raiz = new nodoN(0);
NodoN nodo1 = new Nodo(1);
NodoN nodo2 = new Nodo(2);
NodoN nodo3 = new Nodo(3);
NodoN nodo4 = new Nodo(4);
NodoN nodo5 = new Nodo(5);
NodoN nodo6 = new Nodo(6);
 
//Creamos la estructura de arbol
raiz.agregarHijo(nodo1);
raiz.agregarHijo(nodo2);
nodo1.agregarHijo(nodo3);
nodo2.agregarHijo(nodo4);
nodo2.agregarHijo(nodo5);
nodo5.agregarHijo(nodo6);
 

Para recorrer la estructura lo perfecto sería que implementases el patrón iterator en la clase nodo (http://www.tutorialspoint.com/design...or_pattern.htm).
Te pongo un ejemplo de recorrido recursivo del árbol pintando en consola:

Código Java:

public void recorrerArbol(nodoN nodoRaiz) {
   if (nodoRaiz.getHijos() == null) {
        System.out.println("Value=" + nodoRaiz.getValue();        
   }
   for (final nNodoN nodo : nodoRaiz.getHijos()) {
       recorrerArbol(nodo);
   }
}
[....]
recorrerArbol(raiz);
 

Nota: lo he escrito directamente sobre el post, por lo que puede que me haya equivocado en alguna letra y/o símbolo en el código. Sin embargo espero que sirva al menos la idea.


Un saludo

[samurai_7]

Buenas!, muchas gracias por tu ayuda y por todo el tiempo dedicado a escribir la respuesta.
Me has ayudado mucho, ya que me hiciste entenderlo todo, pero con tu definición tengo una duda para la búsqueda de elementos.
Al ser los hijos una lista de nodos, habría que aplicar recursividad en cada uno de ellos.


public nodoN buscarNodo(nodoN r, int v)
{
if(r==null)
{
System.out.println("no hay nodo para buscar");
return null;
}

else
{
if(r.valor==v)
{
return r;
}

else
{
for(int i=0;i<hijos.size();i++)
{
buscarNodo(r.hijos.get(i),v);
}
}
}
}

Código Java:

public nodoN buscarNodo(nodoN r, int v)
    {
        if(r==null)
        {
            System.out.println("no hay nodo para buscar");
            return null;
        }
        
        else
        {
            if(r.valor==v)
            {
                return r;
            }
            
            else
            {
                for(int i=0;i<hijos.size();i++)
                {
                buscarNodo(r.hijos.get(i),v);
                }               
            }
        }
    }
 

Aunque es bastante sencillo, no compila ya que me dice que el método debe volver un elemento tipo nodoN, cosa que ya hace, pero no se por qué me sigue dando ese error. He probado a meter el return en el primer if(para contemplar todos los casos) y sigue fallando.
¡¡gracias!!

[samurai_7]

[QUOTE=samurai_7;4656919]Buenas!, muchas gracias por tu ayuda y por todo el tiempo dedicado a escribir la respuesta.
Me has ayudado mucho, ya que me hiciste entenderlo todo, pero con tu definición tengo una duda para la búsqueda de elementos.
Al ser los hijos una lista de nodos, habría que aplicar recursividad en cada uno de ellos.

}

Código Java:

public nodoN buscarNodo(nodoN r, int v)
    {
        if(r==null)
        {
            System.out.println("no hay nodo para buscar");
            return null;
        }
        
        else
        {
            if(r.valor==v)
            {
                return r;
            }
            
            else
            {
                for(int i=0;i<hijos.size();i++)
                {
                buscarNodo(r.hijos.get(i),v);
                }               
            }
        }
    }
 

Aunque es bastante sencillo, no compila ya que me dice que el método debe volver un elemento tipo nodoN, cosa que ya hace, pero no se por qué me sigue dando ese error hasta que meto el return debajo de la llamada a recursividad(en el segundo else), aunque no debería ya que el método de por si ya está devolviendo un tipo adecuado.
¡¡gracias!!

[Profesor_Falken]

Buenas,

Es compilador tiene razon al quejarse, ya que cuando haces la llamada recursiva no haces retorno.

En realidad hay dos errores en dicho for:
-No haces retorno de un nodo en la llamada recursiva
-Cuando recorres lo haces sobre los hijos de la instancia cuando en realidad deberias hacerlos sobre el nodo pasado por parametro.

for(int i=0;i<r.hijos.size();i++)
{
return buscarNodo(r.hijos.get(i),v);
}

Otra forma mas sencilla de hacer el bucle seria:

Código Java:

for(final nodoN nodoHijo : r.hijos) {
    return buscarNodo(nodoHijo ,v);
}
 

Por otro lado, este metodo de busqueda es stateless y no depende del estado de una instancia, por lo que lo mas adecuado es que lo hagas static.
En resumen, tu codigo quedaria mas o menos asi:

Código Java:

public static nodoN buscarNodo(nodoN r, int v)
    {
        if(r==null)
        {
            System.out.println("no hay nodo para buscar");
            return null;
        }
        
        else
        {
            if(r.valor==v)
            {
                return r;
            }
            
            else
            {
                for(final nodoN nodoHijo : r.hijos) {
                      return buscarNodo(nodoHijo ,v);
               }          
            }
        }
    }
 

Y cuando quieras llamarlo lo puedes hacer asi

Código Java:

nodoN nodoEncontado = nodoN.buscarNodo(raiz, 8);
 

Un saludo

[samurai_7]

Hola,
gracias de nuevo por tomarte tu tiempo :).

Muchas gracias por tu ayuda en la instancia de los hijos, se me pasó ese detalle de r., pero llevas tu razón. ;).

Pero no estoy de acuerdo contigo en eso de que debe retornar un valor siempre, ya que de los 3 posibles casos que tengo, en 2 de ellos (cuando r ==null y cuando encuentro en el valor que deseo) devuelvo un resultado tipo nodoN, es sólo en la última función que falta (en la de búsqueda de los hijos) cuando no devuelve, pero dicha función al resolverse por recursividad, devolverá al resolverse un valor de tipo nodoN, ya que en última instancia tirará por alguno de los 2 caminos por lo que si está devolviendo algo.

Quizás sea fallo de concepto en Java, creo que en c se hacia como digo, ya que al resolverse la recursividad dará el tipo dado.
De todas formas, como tampoco había muchas opciones, puse un return como bien indicas, quedando el cógido de la siguiente forma:

Código Java:

public nodoN buscarNodo(nodoN r, int v)  <--1
    {
        if(r==null)
        {
            System.out.println("no hay nodo para buscar");
            return null;
        }
        
        else
        {
            if(r.valor==v)
            {
                return r;
            }
            
            else
            {
                for(int i=0;i<hijos.size();i++)  <--2
                {
                return buscarNodo(r.hijos.get(i),v);    
                }   
            }
        }
    }
 

<--1, me indica el mismo fallo que entes, que no devuleve el tipo adecuado (nodoN).
<--2, indica en el i++, cógido muerto. Imagino que será ya que en la primera iteración revolverá el resultado, y ya saldrá del bucle, por lo que no se llega a ejecutar el primer i++. Pero si no es con un bucle, no se me ocurre como llamar a cada uno de los hijos.

Gracias!