I can’t remove leaf in binary tree

Asked

Viewed 363 times

2

I’m trying to remove a leaf from the tree, I made a code that apparently, in my head is right, only it doesn’t remove the element I want.

Here is my class No:

package arvore;

public class No {

    private No esquerda;
    private No direita;
    private int valor;

    public No(int valor) {
        this.valor = valor;
    }

    public No getEsquerda() {
        return esquerda;
    }

    public void setEsquerda(No esquerda) {
        this.esquerda = esquerda;
    }

    public No getDireita() {
        return direita;
    }

    public void setDireita(No direita) {
        this.direita = direita;
    }

    public int getValor() {
        return valor;
    }

    public void setValor(int valor) {
        this.valor = valor;
    }
}

Here is my class ArvoreBinaria:

package arvore;

public class ArvoreBinaria {

private No raiz;

public ArvoreBinaria(int valor) {
    adicionar(raiz, valor);
}

public No getRaiz() {
    return raiz;
}

public void setRaiz(No raiz) {
    this.raiz = raiz;
}

public void adicionar(int valor) {
    adicionar(raiz, valor);
}

public void adicionar(No no, int valor) {
    if (this.raiz == null) {
        raiz = new No(valor);
        return;
    }
    if (valor < no.getValor()) {
        if (no.getEsquerda() != null) {
            adicionar(no.getEsquerda(), valor);
        } else {
            no.setEsquerda(new No(valor));
        }

    } else if (valor >= no.getValor()) {
        if (no.getDireita() != null) {
            adicionar(no.getDireita(), valor);
        } else {
            no.setDireita(new No(valor));
        }
    }
}

public void preOrdem() {
    preOrdem(this.raiz);
}

public void preOrdem(No no) {
    if (no != null) {
        System.out.println(no.getValor());
        preOrdem(no.getEsquerda());
        preOrdem(no.getDireita());
    }
}

public void posOrdem() {
    posOrdem(this.raiz);
}

public void posOrdem(No no) {
    if (no != null) {
        posOrdem(no.getEsquerda());
        posOrdem(no.getDireita());
        System.out.println(no.getValor());
    }

}

public void emOrdem() {
    emOrdem(this.raiz);
}

public void emOrdem(No no) {
    if (no != null) {
        emOrdem(no.getEsquerda());
        System.out.println(no.getValor());
        emOrdem(no.getDireita());
    }
}

public void remover(int valor) {
    remover(this.raiz, valor);
}

public void remover(No no, int valor) {
    if (no != null) {
        boolean flag = false;
        if (valor == no.getValor() && no.getEsquerda() == null && no.getDireita() == null) {
            no = null;
            flag = true;
        }
        if (!flag) {
            remover(no.getEsquerda(), valor);
            remover(no.getDireita(), valor);
        }
        if (flag == false) {
            if (no.getEsquerda() == null) {
                no.setEsquerda(null);
            }
            if (no.getDireita() == null) {
                no.setDireita(null);
            }
        }

    }
}
}

Here is my main application:

package app;

import arvore.ArvoreBinaria;

public class App {

    public static void main(String[] args) {
        ArvoreBinaria arvore = new ArvoreBinaria(10);
        arvore.adicionar(8);//                          10                                               
        arvore.adicionar(12);//                 8                 12
        arvore.adicionar(12);//           6           9       11        12
        arvore.adicionar(11);//        n      7     n   n   n    11    n   15
        arvore.adicionar(11);//             n   n               n  n      n   n
        arvore.adicionar(15);//                     
        arvore.adicionar(9);//                      n = null
        arvore.adicionar(6);//
        arvore.adicionar(7);//
        //System.out.println(arvore.getRaiz().getDireita().getEsquerda().getDireita().getValor());

        /*System.out.println("Pré Ordem");
        arvore.preOrdem();
        System.out.println("----------------------------"); 
        System.out.println("Em Ordem");
        arvore.emOrdem();
        System.out.println("----------------------------");
        System.out.println("Pós Ordem");
        arvore.posOrdem();
         */
        arvore.remover(7);
        //System.out.println(arvore.getRaiz().getEsquerda().getEsquerda().getDireita().getValor());
        arvore.emOrdem();
    }
}
java
  • 1

    if (!flag) and if (flag == false) are the same thing.

  • Yes, it is that in the first flag if it is true, I do not want it to enter that block of code, because it would give Nullpointerexception, since the no.getEsquerda() would be exactly of the sheet, of the node I just annulled. Already in the second flag, it only becomes true when it finds the sheet, when not, it remains false. then I made that code block for the in the parent, override the reference to the node that was just removed, when the recursive execution stack goes back to the parent.

  • You do not have any code that can modify the value of this flag between the two comparisons.

1 answer

3


From what I understand, this is a binary search tree. Therefore, the algorithm to remove a node should take into account some cases:

  1. if the node is a leaf (that is, it has no right or left subtree), just remove it:

Ex:

  10
 /  \
5    15
    /
   12

To remove the 12 it’s easy: as he has no children, just take him out of the tree.

  10
 /  \
5    15
  1. node has only one child: replace node with child

Ex:

  10
 /  \
5    15
    /
   12
  /  \
 11  13

To remove the 15: as he only has one child (which is knot 12), just replace it with the child.

  10
 /  \
5    12
    /  \
   11  13
  1. if the knot has 2 children:
    • find the largest of the children who are in the sub-tree on the left
    • copy the value of the largest child to the node
    • recursively remove child from left subtree

Ex:

  10
 /  \
5    15
    /  \
   12  17
  /  \
 11  13

To remove the 15:

  • find the largest child of the left subtree: in this case it is 13
  • replaces the value of 15 with this largest child:
  10
 /  \
5    13
    /  \
   12  17
  /  \
 11  13
  • recursively remove 13 from the left subtree (i.e., start removing 13 from the 12):
    • the algorithm will recursively search for 13, and as the search was done from 12, it arrives at 13 below. And when he sees that he has no children, he falls in case 1 (he is simply removed):
  10
 /  \
5    13
    /  \
   12  17
  /
 11

The above algorithm and code below have been adapted of this article. In your case it would look like this:

// encontrar o maior valor a partir do nó indicado
private No maiorValor(No no) {
    while (no.getDireita() != null) {
        no = no.getDireita();
    }

    return no;
}

public void remover(int valor) {
    remover(this.raiz, valor);
}

public No remover(No no, int valor) {
    // chave não encontrada na árvore
    if (no == null) {
        return no;
    }

    // valor menor, procurar na sub-árvore esquerda
    if (valor < no.getValor()) {
        no.setEsquerda(remover(no.getEsquerda(), valor));
    } else if (valor > no.getValor()) {
        // valor maior, procurar na sub-árvore direita
        no.setDireita(remover(no.getDireita(), valor));
    } else { // valor encontrado
        // caso 1: nó é uma folha (não tem filhos)
        if (no.getEsquerda() == null && no.getDireita() == null) {
            // remove-o (seta a "raiz" deste nó para null)
            return null;
        } else if (no.getEsquerda() != null && no.getDireita() != null) {
            // caso 3: nó tem 2 filhos
            // encontrar o maior dos filhos que antecede o nó
            No maiorAntecessor = maiorValor(no.getEsquerda());

            // copia o valor do antecessor para este nó
            no.setValor(maiorAntecessor.getValor());

            // remove o antecessor recursivamente
            no.setEsquerda(remover(no.getEsquerda(), maiorAntecessor.getValor()));
        } else {
            // caso 2: nó só tem um filho
            No child = (no.getEsquerda() != null) ? no.getEsquerda() : no.getDireita();
            no = child;
        }
    }

    return no;
}

If you only want to remove the leaves (according to this comment), just adapt the above algorithm to ignore cases where the node is not sheet:

public void removerFolha(int valor) {
    removerFolha(this.raiz, valor);
}

public No removerFolha(No no, int valor) {
    if (no == null) {
        return no;
    }

    // valor menor, procurar na sub-árvore esquerda
    if (valor < no.getValor()) {
        no.setEsquerda(removerFolha(no.getEsquerda(), valor));
    } else if (valor > no.getValor()) {
        // valor maior, procurar na sub-árvore direita
        no.setDireita(removerFolha(no.getDireita(), valor));
    } else { // valor encontrado
        // nó é uma folha (não tem filhos)
        if (no.getEsquerda() == null && no.getDireita() == null) {
            // remove-o (seta a "raiz" deste nó para null)
            return null;
        }
    }

    // nó não foi encontrado ou não é folha, retorna o próprio nó
    return no;
}

  • Thank you for your reply, you will help me very much in the future. but at the moment I just want to remove a sheet, I’m just doing a method remove exclusively for this. My remove method works as follows: it checks if the node is sheet, and is the node sought to remove. after this, if he finds the knot, he nullifies it and arrow the true flag. Since the flag is true, it does not enter the code block that applies the recursion: remove (no.getEsquerda(), value); the flag avoids a Nullpointerexception since it does not enter that code.

  • If the flag is false, when the recursion goes back to the parent node that was removed, it overrides the reference to the node that was deleted. This code seems to be complete for me, only it just doesn’t remove the node, I don’t understand why. Thank you for having answered me, after removing the sheet, I will create a method to remove a knot that has only one child, then a knot that has two, then I will put together everything to do all this in one remove. this is a slow process but it is necessary for me to learn, Thank you.

  • 1

    @Gabrielhenrique I think we do not need this flag, just adapt the removal algorithm to ignore the cases where the node is not leaf. I updated the response with this option.

  • Thank you very much, as I mark the question as solved ?

  • @Gabrielhenrique Just click on the left side of the answer (here has more detailed instructions in case you do not find)

Browser other questions tagged java

You are not signed in. Login or sign up in order to post.