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.