Question:
Hey guys. I started studying the Java language recently and decided to try to create a binary tree with three features:
1 – Add element to tree
2 – Search and print tree element
3 – Remove tree element (relocating its children)
The third functionality must be done in such a way that, for example, a binary tree that has a root value of 3 and children 2 and 5, when receiving the command to remove the value 3, must keep the values 2 and 5 in the tree. In other words: when removing the parent node, its children are not removed, but reinserted in the tree.
With that in mind, I created the Tree class that follows:
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;
}
}
The 'insert' and 'fetch' functions, responsible for inserting and searching the elements in the tree, respectively, are working normally. The functions 'remove' and 'novo_no', which act together to remove an element from the tree, do not work well, generating the error mentioned in the title.
NOTE: I'm not sure if the two functions have errors or if only one of them is wrong. Therefore, I would like your help to understand why the program does not work as desired.
As for the behavior of the program:
Adding the numbers 5, 6 and 4 to the tree, as a test, and searching for any of them, the program works perfectly. However, when trying to remove some of the child nodes (4 and 6), the program acts as if it had removed them, when in fact it is still possible to fetch them from the tree. When trying to remove the parent node(5), the program closes and displays the error lines below:
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)
I checked the lines mentioned above, but I couldn't understand what was wrong. Therefore, I count on your help to understand what happened. Below is the Main function:
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;
}
}
}
Thanks in advance!
Hello again. According to @cleberz, the following block was not working because it provided a null value for the novo_no function:
...
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;
}
...
After the correction, this block looked like this:
...
if(root.valor == valor){
Arvore dest = new Arvore();
root = novo_no(root,dest);
/* 1 */
return 0;
}
...
However, on the line /* 1 */ , if I put 3 JOptionPane.showMessageDialog() to show the value of the new node(root) and the value of its 2 children, I get the following return:
node value: 0
right node value: 4
left node value: null
That's when we just add the numbers 5,4 and 6 to the tree. But although this is not the desired return, as the node value should be the number 4, while the number 6 would be its right child, when fetching the value 5 from the tree again it is still there, even if the value of root should have been changed before the remove function returned. I would like to know why the value of root doesn't change in that case.
Answer:
The problem specifically with the NullPointerException on that line is occurring because your remove() method is passing a null value in the parameter of this function 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;
}
...
The new_no() function in turn is trying to access a member (in this case, a method) of that parameter without checking if it is null:
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
Well, that's the problem with your code's NPE. But I see some other problems (typical for beginners, of course) like:
1 – using the same class for the Tree instead of using one class for the Tree, and another for the node. The Tree class can contain the pointer to the root and the number of nodes, and the node class can only contain the value of its node, and the pointers to its child nodes. 2 – there is no need to store the String version of the values for later display ( d and e variables). This can be done in the method that prints.