3

Olá, pessoal. Comecei a estudar a linguagem Java há pouco tempo e decidi tentar criar uma arvore binária com três funcionalidades:

1 - Adicionar elemento à árvore

2 - Buscar e imprimir elemento da árvore

3 - Remover elemento da arvore (realocando seus filhos)

A terceira funcionalidade deve ser feita de modo que, por exemplo, uma arvore binária que tenha raiz de valor 3 e filhos 2 e 5, ao receber o comando de remover o valor 3, deve manter os valores 2 e 5 na árvore. Ou seja: ao remover o nó pai, seus filhos não são removidos, mas sim reinseridos na arvore.

Com isso em mente, eu criei a classe Arvore que segue abaixo:

package org.hello;

import javax.swing.JOptionPane;

public class Arvore {
    int valor;
    Arvore left = null;
    Arvore right  = null;
    String e,d;
    int size;

    Arvore(){
        size=0;
    }
    Arvore(int x){
        valor=x;
        size=0;
    }

    int insert(Arvore root,int valor){
        Arvore a = new Arvore(valor);
        if(root == null){
            root = a;
            root.size++;
            JOptionPane.showMessageDialog(null, "Elemento Adicionado!.");
        }
        else{
            if(valor > root.valor){
                if(root.right == null){
                    root.right = a;
                    root.size++;
                    a.size = root.size;
                    JOptionPane.showMessageDialog(null, "Elemento Adicionado!.");
                }
                else{
                    return insert(root.right,valor);
                }
            }
            else {
                if(valor < root.valor){
                    if(root.left == null){
                        root.left = a;
                        root.size++;
                        a.size = root.size;
                        JOptionPane.showMessageDialog(null, "Elemento Adicionado!.");
                    }
                    else{
                        return insert(root.left,valor);
                    }
                }
                else{
                    if(valor == root.valor){
                        JOptionPane.showMessageDialog(null, "Elemento já existente.");
                    }
                }
            }


        }
        return 0;
    }

    int buscar(Arvore root, int valor){
        if(root == null){
            JOptionPane.showMessageDialog(null, "Elemento não encontrado.");
        }
        else{
            if(root.valor == valor){ 
                if(root.left == null ){
                    root.e = "vazio" ;
                }
                else{
                    root.e = Integer.toString(root.left.valor);
                }
                if(root.right == null){
                    root.d = "vazio";
                }
                else{
                    root.d = Integer.toString(root.right.valor);
                }
                JOptionPane.showMessageDialog(null,"Valor: "+root.valor+"\n"+"Esquerdo: "+root.e+"\n"+"Direito: "+root.d+"\n\n");
            }
            else{
                if(root.valor < valor){
                    return buscar(root.right,valor);
                }
                else{
                    return buscar(root.left,valor);
                }
            }
        }
        return 0;
    }
Arvore novo_no(Arvore source,Arvore dest){
    if(source.right==null && source.left==null){
        return dest;
    }
    else{
        if(source.right != null && source.left != null){
        dest.insert(dest,source.left.valor);
        dest.insert(dest,source.right.valor);
        dest = novo_no(source.left,dest);
        dest = novo_no(source.right,dest);
        return dest;
        }
        else{
            if(source.right != null && source.left == null){
                dest.insert(dest,source.right.valor);
                dest = novo_no(source.right,dest);
                return dest;
            }
            else{
                dest.insert(dest,source.left.valor);
                dest = novo_no(source.left,dest);
                return dest;
            }
        }
    }
}
int remove(Arvore root, int valor){
    if(root==null){
        JOptionPane.showMessageDialog(null,"Elemento não cadastrado.");
    }
    else{
        if(root.valor == valor){
            Arvore dest = new Arvore();
            dest = null;
            root = novo_no(root,dest);
            return 0;
        }
        else{
            if(root.valor > valor){
                return remove(root.left,valor);
            }
            else{
                return remove(root.right,valor);
            }
        }
    }
    return 0;
}
} 

As funções 'insert' e 'buscar', responsáveis por inserir e buscar os elementos na árvore, respectivamente, estão funcionando normalmente. Já as funções 'remove' e 'novo_no', que atuam em conjunto para remover um elemento da árvore, não funcionam bem, gerando o erro mencionado no título.

OBS: não tenho certeza se as duas funções apresentam erros ou se apenas uma delas está errada. Por isso, gostaria da ajuda de vocês para entender por que o programa não funciona da forma desejada.

Quanto ao comportamento do programa:

Adicionando os números 5,6 e 4 à árvore, como teste, e fazendo a busca de qualquer um deles, o programa funciona perfeitamente. No entanto, ao tentar remover algum dos nós filhos(4 e 6), o programa age como se os tivesse removido, quando na verdade ainda é possível buscá-los na árvore. Já quando se tenta remover o nó pai(5), o programa encerra e apresenta as linhas de erro abaixo:

Exception in thread "main" java.lang.NullPointerException
at org.hello.Arvore.novo_no(Arvore.java:100)
at org.hello.Arvore.remove(Arvore.java:128)
at org.hello.Principal.main(Principal.java:40)
at org.hello.Principal.main(Principal.java:36)
at org.hello.Principal.main(Principal.java:41)
at org.hello.Principal.main(Principal.java:36)
at org.hello.Principal.main(Principal.java:26)
at org.hello.Principal.main(Principal.java:26)
at org.hello.Principal.main(Principal.java:22)

Eu chequei as linhas mencionadas acima, mas não consegui entender o que havia de errado. Por isso, conto com a ajuda de vocês para entender o que houve. Segue abaixo a função Principal:

package org.hello;
import java.util.Scanner;

import javax.swing.JOptionPane;

public class Principal {

static Arvore pai = null;

public static void main(String[] args){

    int escolha = Integer.parseInt(JOptionPane.showInputDialog("Escolha uma opção: \n\n 1-Adicionar elemento \n 2-Buscar elemento \n 3-Remover elemento \n"));

    switch(escolha){
    case 1:
        int valor = Integer.parseInt(JOptionPane.showInputDialog("Digite o valor a ser adicionado: "));
        if(pai==null){
            Arvore a = new Arvore(valor);
            pai = a;
            JOptionPane.showMessageDialog(null, "Elemento Adicionado!.");
            pai.size++;
            main(null);
            break;
        }
        pai.insert(pai, valor);
        main(null);
        break;
    case 2:
        int valor2 = Integer.parseInt(JOptionPane.showInputDialog("Digite o valor a ser buscado: "));
        if(pai == null){
            JOptionPane.showMessageDialog(null,"Elemento não existente.");
            main(null);
            break;
        }
        pai.buscar(pai, valor2);
        main(null);
        break;
    case 3:
        int valor3 = Integer.parseInt(JOptionPane.showInputDialog("Digite o valor a ser removido: "));
        pai.remove(pai, valor3);
        main(null);
        break;
    }
}
}

Agradeço desde já!

Olá novamente. Segundo o @cleberz, o seguinte bloco não estava funcionando por fornecer um valor nulo para a função novo_no:

 ...    
if(root.valor == valor){
    Arvore dest = new Arvore();
    dest = null; //pra quê anular se você 
                 //acabou de inicializar?
    root = novo_no(root,dest); //isso manda um nulo aqui
    return 0;
}
... 

Após a correção, esse bloco ficou assim:

...    
if(root.valor == valor){
    Arvore dest = new Arvore();
    root = novo_no(root,dest);
    /* 1 */
return 0;
}
...

Porém, na linha /* 1 */, se eu colocar 3 JOptionPane.showMessageDialog() para mostrar o valor do novo nó(root) e o valor de seus 2 filhos, eu tenho o seguinte retorno:

valor do nó: 0

valor nó direito: 4

valor nó esquerdo: null

Isso quando adicionamos apenas os números 5,4 e 6 à arvore. Mas embora esse não seja o retorno desejado, já que o valor do nó deveria ser o número 4, enquanto o número 6 seria seu filho direito, ao buscar o valor 5 na árvore novamente ele ainda se encontra lá, mesmo que o valor de root devesse ter sido alterado antes da função remove retornar. Eu gostaria de saber por que o valor de root não se altera, nesse caso.

2 Respostas 2

2

O problema especificamente do NullPointerException naquela linha está ocorrendo porque o seu método remove() está passando um valor nulo no parametro dest função novo_no() :

    ...    
    if(root.valor == valor){
        Arvore dest = new Arvore();
        dest = null; //pra quê anular se você 
                     //acabou de inicializar?
        root = novo_no(root,dest); //isso manda um nulo aqui
        return 0;
    }
    ...

A função novo_no() por sua vez está tentando acessar um membro (no caso, um método) daquele parâmetro sem verificar se ele é nulo:

Arvore novo_no(Arvore source,Arvore dest){
  if(source.right==null && source.left==null){
      return dest;
  }
  else{
      if(source.right != null && source.left != null){
      dest.insert(dest,source.left.valor); //dest é nulo aqui

Bom, esse é o problema do NPE do seu código. Mas vejo alguns outros problemas (típicos de iniciante, claro) como:

1 - usando a mesma classe para a Árvore ao invés de usar uma classo para a Árvore, e outra para o nó. A classe Árvore pode conter o ponteiro para a raiz e o número de nós, e a classe nó pode conter somente o valor de seu nó, e os ponteiros para os nós-filhos dela. 2 - não há necessidade de se armazenar a versão em String dos valores para exibição posterior (variáveis d e e). Isso pode ser feito no próprio método que imprime.

1
  • Retirando a linha dest = null, o programa não dá mais erro, mais ainda assim ele não modifica o nó que deve ser retirado. Utilizando o exemplo anterior, de inserir os números 5,4 e 6 na árvore, o root recebe um nó de valor 0 e filhos 4 e null como retorno da função novo_no, o que não é o resultado desejado. Mas mesmo assim, o valor de root não é modificado. O que poderia ser isso?
    – João Luca
    Commented 4/01/2016 às 11:42
0

Consegui fazer o programa funcionar. Basicamente, eu não entendia por que uma função como insert conseguia alterar o root, enquanto remove não fazia o mesmo. Acontece que, aparentemente, uma variável não altera a si mesma dentro da função. Para que isso aconteça, o valor alterado dentro da função deve ser retornado e armazenado em uma nova variável, e a variável antiga deve ser igualada a essa variável nova, para que seu valor mude. No entanto, quando se trata de uma variável dentro de uma variável, como é o caso de objetos da classe Arvore no meu programa, não é preciso retornar esse valor já que, por exemplo, o objeto root age como um "ponteiro", que aponta para seus atributos, podendo modificar root.left, por exemplo. Essa semelhança com ponteiros explica por que root não altera a si mesmo, já que seria necessário um ponteiro de ponteiro para fazê-lo.

Sendo assim, eu realizei as seguintes modificações:

1 - Na função novo_no da classe Arvore :

...
if(source.right==null && source.left==null){
        dest = null;
/*retorna um valor nulo para o nó, impedindo que o programa funcione 
de forma errada, já que, por ter sido inicializado dessa forma: 
'Arvore dest = new Arvore(); 
dest retornaria como um objeto Arvore de valor 0 */

        return dest;
    }
...

2 - Na função remove da classe Arvore :

... 
root.left = remove(root.left,valor);
...

...
root.right = remove(root.right,valor);
...

/* Dessa forma eu altero os nós esquerdos e direitos, já que eles não 
precisam ser retornados para a função main para serem modificados, como eu
havia dito anteriormente*/

3 - Na função main da classe Principal:

...
case 3:
        int valor3 = Integer.parseInt(JOptionPane.showInputDialog("Digite o
  valor a ser removido: "));
        Arvore c = pai.remove(pai, valor3);
        pai = c;
        main(null);
        break;
    /* Aqui, a variável c recebe o valor de retorno da função remove. Se 
essa função modificasse apenas os nós filhos, essa variável seria desnecessária. Mas como a 
raiz também pode ser removida, então é necessário retornar esse valor da função e igualá-lo 
ao pai.*/

...

Mas por que a função insert funcionava normalmente se ela não retorna nenhum objeto Arvore e mesmo assim ela altera o valor de pai ? Isso é simples:

...
case 1:
        int valor = Integer.parseInt(JOptionPane.showInputDialog("Digite o valor a ser adicionado: "));
        if(pai==null){
            Arvore a = new Arvore(valor);
            pai = a;
            JOptionPane.showMessageDialog(null, "Elemento Adicionado!.");
            pai.size++;
            main(null);
            break;
        }
        pai.insert(pai, valor);
        main(null);
        break;

/*Como é possível notar, o case 1 da função main tinha uma condição que
 tinha a função de alterar o 'pai' caso esse fosse nulo. Por isso, a função 'insert' era 
usada apenas para adicionar outros nós, não precisando alterar o valor da raiz. Por isso 
 não foi necessário armazenar o retorno dessa função, já que ela não era usada para modificar a raiz.*/

Acho que isso é tudo. Agradeço pelas respostas e espero que a minha pergunta possa ajudar outras pessoas.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .