Error related to binary tree element removal and child relocation (java.lang.NullPointerException)

Question

Error related to binary tree element removal and child relocation (java.lang.NullPointerException)

Navigation

#1 by (2 votes)
#2 by (0 votes)

3

Hello everyone. I started studying the Java language recently and decided to try to create a binary tree with three functions:

1 - Add element to tree

2 - Search and print tree element

3 - Remove element from the tree (relocating your children)

The third functionality should be done so that, for example, a binary tree that has a value of 3 root and a child 2 and 5, on receiving the remove value 3 command, should keep values 2 and 5 in the tree . That is to say: when removing the parent node, its children are not removed, but reinserted in the tree.

With this in mind, I've 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 fetching the elements in the tree, respectively, are working normally. The 'remove' and 'new_no' functions, 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 both functions have errors or if only one of them is wrong. So I'd like your help to understand why the program does not work the way you want it to.

As for the behavior of the program:

Adding the numbers 5, 6, and 4 to the tree as a test, and by doing any of them, the program works perfectly. However, when attempting to remove any of the child nodes (4 and 6), the program acts as if it removed them, when in fact it is still possible to fetch them from the tree. Already 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 could not understand what was wrong. So I count on your help to understand what happened. Here 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;
    }
}
}

Thank you 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 fix, this block looks like this:

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

However, on 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 have the following return:

node value: 0

value right node: 4

left node value: null

That's when we just added numbers 5.4 and 6 to the tree. But although this is not the desired return, since the value of the node should be the number 4, while the number 6 would be its right child, when fetching the value 5 in the tree again it is still there, even though the value of root should have been changed before the remove function returns. I would like to know why the root value does not change, in that case.

java

asked by anonymous 03.01.2016 / 23:04

2 answers

Excel file reading Doubt with version of AspNet.Mvc

score 2 · Answer 1

The problem specifically of the NullPointerException on that row is occurring because your remove method is passing a null value in the dest in>:

    ...    
    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 is in turn trying to access a member (in this case, a method) of that parameter without checking whether 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 NPE problem with your code. But I see some other problems (typical of beginner, of course) like:

1 - using the same class for the Tree instead of using a classo 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 contain only 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 (variables d and and ). This can be done in the very method it prints.

score 0 · Answer 2

I was able to make the program work. Basically, I did not understand why a function like insert could change root , while remove did not do the same. It turns out that, apparently, a variable does not change itself within the function. For this to happen, the changed value inside the function must be returned and stored in a new variable, and the old variable must be matched to this new variable, so that its value changes. However, when it comes to a variable within a variable, as is the case with objects of the Arvore class in my program, you do not need to return this value since, for example, the root object acts as a " pointer ", which points to its attributes, being able to modify root.left , for example. This similarity with pointers explains why root does not change itself, since it would require a pointer pointer to do so.

So, I've made the following changes:

1 - In function novo_no of class Tree:

...
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 - In function remove of class Tree:

... 
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 - In the main function of the Main class:

...
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.*/

...

But why did the insert function normally work if it does not return any Tree objects and still it changes the value of pai ? This is simple:

...
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.*/

I think that's all. Thanks for the answers and hope that my question can help other people.