Enero 19, 2018, 12:03:21 pm

Autor Tema: Problema añadiendo nodo a árbol binario--Como funcionan las referencias en java?  (Leído 4170 veces)

0 Usuarios y 1 Visitante están viendo este tema.

Desconectado does

  • Me das tu IP?
  • *
  • Mensajes: 50
    • Ver Perfil
Saludos a todos!
Últimamente estuve trabajando con arboles en java en especial con una implementación de un árbol binario y para añadir un nodo cree un método recursivo que cumple con el trabajo, pero por alguna razón, que escapa a mi entendimiento del lenguaje, este método no cumple con su trabajo y mi duda es el por que no funciona.
Claro, podría buscar en Internet algún otro método,de alguien mas y que si funcione, copiarlo en mi programa y listo pero el asunto es que quiero entender por que no funciona.
Muchas gracias.

Estos son los miembros de la clase Node y para no pegar demasiado código asumamos que los seters y geters también fueron declarados.
Código: (java) You are not allowed to view links. Register or Login

public class Node
{
    private  char symbol;
    private String code;
    private int count;
    private float prob;
    private Node leftSon;
    private Node rightSon;
}

Estos son los miembros del árbol binario y el método addNode para añadir un nuevo nodo al árbol.
Código: (java) You are not allowed to view links. Register or Login
public class Btree
{
    public Node head; //Nodo padre de todo el arbol
    public int size;      //Numero de nodos del arbol

    public void addNode(Node actual, char symbol,String code)
    {
        if(actual == null)                                                        //Si el lugar esta vació agrega un nodo
        {
            actual = new Node(symbol,code);
            size++;
        }
        else if(actual.getSymbol() == symbol)                      //Si el nodo ya existía agrega uno a su cuenta
            actual.setCount(actual.getCount()+1);
        else if(actual.getSymbol() > symbol)                        //El símbolo que llego es menor que el del nodo actual
            addNode(actual.getLeftSon(),symbol,code);       //Llama a la función usando al hijo izquierdo del actual
        else                                                                           //El símbolo nuevo es mayor que el del nodo actual
            addNode(actual.getRightSon(),symbol,code);
    }
}

Ahora que ya esta aclaro el como se construyeron las clases pasamos a la clase principal donde hago lo siguiente:
Código: (java) You are not allowed to view links. Register or Login
Btree btree = new Btree(); //el constructor de btree pone head = null y size = 0
Scanner scan = new Scanner(System.in);
String entrada;

entrada = scan.nextLine();
for(int i = 0; i < entrada.length();i++)
    btree.addNode(btree.getHead(), entrada.charAt(i),null);

Como se puede ver, leo una string de la entrada y cada uno de sus caracteres es pasado al método addNode que ,como nodo actual, lleva la propia cabeza del árbol.
Es entonces que empieza el problema por que el método addNode entra a los casos que le corresponden como se espera y a pesar de que crea nuevos nodos, no los agrega al árbol.
De nuevo, gracias por la ayuda.
C Nuestro que estas en la Memoria,
Compilado sea tu código,
venga a nosotros tu software,
carguense tus punteros.
así en la RAM como en el Disco Duro,
Danos hoy nuestro Array de cada día,
Perdona nuestros Warnings...

Desconectado .:MYTO:.

  • Me das tu IP?
  • *
  • Mensajes: 193
  • Sexo: Masculino
  • Hunt3r m1nd 1s 0nly f0r f3w...
    • Ver Perfil
 Tal y como tienes el código ahora la recursión funciona en teoría. En la práctica no funciona porque nunca haces nada con actual si éste es null (en addNode). Es decir, creas una referencia pero no la guardas; en cuanto la función finaliza el nuevo nodo se pierde.

 Te ayudo.

Código: You are not allowed to view links. Register or Login
if(actual == null)
        {
            actual = new Node(symbol,code);
            if(size++ == 0) this.head = actual;
        }

 Eso arreglaría el árbol para añadir el nodo cabeza, pero sigue sin funcionar para el resto de nodos. Eso te lo dejo a ti.


Salu2
 
Debería estar estudiando...

Desconectado does

  • Me das tu IP?
  • *
  • Mensajes: 50
    • Ver Perfil
Saludos y gracias por tomarte el tiempo para verlo.

En esta parte del código le paso el parámetro actual que es de hecho la raíz del árbol
for(int i = 0; i < entrada.length();i++)
    btree.addNode(btree.getHead(), entrada.charAt(i),null); // <--aquí
[/code]

Mi duda es mas bien, por que no funciona si le paso como referencia la raíz del nodo.
« Última modificación: Octubre 18, 2016, 07:32:48 am por does »

Desconectado .:MYTO:.

  • Me das tu IP?
  • *
  • Mensajes: 193
  • Sexo: Masculino
  • Hunt3r m1nd 1s 0nly f0r f3w...
    • Ver Perfil
 Sí, pero más arriba dices que al crear el árbol, head = null y size = 0. Como no lo veo instanciada, deduzco que btree.getHead() == null es true.


 De todas maneras, supongamos que head != null. Sigue fallando el código porque no hace nada con actual en addNode cuando actual == null. Tienes que decirle al nodo anterior que el nodo actual es hijo suyo.

 Yo haría algo así:

Código: You are not allowed to view links. Register or Login
public class Btree {
    protected Node head;
    protected int size;

    protected void addNode(Node padre, Node hijo, boolean esHijoDerecho, char symbol, String code) {
        if(hijo == null) {
            hijo = new Node(symbol, code);
            if(esHijoDerecho) {
                padre.setRightSon(hijo);
            } else {
                padre.setLeftSon(hijo);
            }
            this.size++;
        } else if(hijo.getSymbol() == symbol) {
            hijo.setCount(hijo.getCount()+1);
        } else if(hijo.getSymbol() > symbol) {
            this.addNode(hijo, hijo.getLeftSon(), false, symbol, code);
        } else {
            this.addNode(hijo, hijo.getRightSon(), true, symbol, code);
        }
    }

    public void addNode(char symbol, String code) {
        if(this.size == 0) {
            this.head = new Node(symbol, code);
            this.size++;
        } else {
            this.addNode(this.head, this.head, false, symbol, code);
        }
    }
}

 Y en el main

Código: You are not allowed to view links. Register or Login
for(int i = 0; i < entrada.length(); i++) {
    btree.addNode(entrada.charAt(i), null);
}


Salu2.
« Última modificación: Octubre 18, 2016, 08:33:49 am por .:MYTO:. »


question
Ejemplo arbol binario

Iniciado por myguestp

6 Respuestas
3861 Vistas
Último mensaje Junio 18, 2010, 09:23:14 am
por Joseph_g
question
Arbol Binario de Busqueda con Clases

Iniciado por pahcko

0 Respuestas
1655 Vistas
Último mensaje Mayo 15, 2010, 04:44:33 pm
por pahcko
xx
Recorrido por anchura en un arbol binario

Iniciado por xaps

5 Respuestas
2476 Vistas
Último mensaje Junio 04, 2013, 07:02:49 am
por MetalRider
resuelto
problema al eliminar el primer nodo!!

Iniciado por .::MeryMery::.

1 Respuestas
2294 Vistas
Último mensaje Agosto 22, 2010, 11:50:23 am
por .::MeryMery::.
xx
Codigo fuente de arbol b+ en java

Iniciado por andrescampx

0 Respuestas
8291 Vistas
Último mensaje Febrero 13, 2007, 03:36:53 pm
por andrescampx
xx
Problema Explorer: arbol de carpetas

Iniciado por Potemkin

5 Respuestas
932 Vistas
Último mensaje Enero 21, 2012, 03:16:48 pm
por keygenida
question
Sniffear siendo un nodo

Iniciado por darkgx

1 Respuestas
666 Vistas
Último mensaje Diciembre 20, 2011, 05:58:34 pm
por soez
question
Cómo hacer un arbol con ramas para fondo web?

Iniciado por M4inFox

4 Respuestas
3562 Vistas
Último mensaje Junio 08, 2013, 04:45:29 am
por Jose1960
xx
Problema al abrir archivo en binario y enviar por winsock

Iniciado por carlmycol

7 Respuestas
2047 Vistas
Último mensaje Julio 03, 2008, 11:43:35 am
por seth
resuelto
problema con operador binario en funcion con datos flotantes

Iniciado por ralymontes

8 Respuestas
1487 Vistas
Último mensaje Noviembre 16, 2009, 07:55:34 pm
por ralymontes