2

Estou tentando remover uma folha da árvore, fiz um código que aparentemente, na minha cabeça está certo, só que ele não remove o elemento que eu quero.

Aqui está minha classe 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;
    }
}

Aqui está minha classe 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);
            }
        }

    }
}
}

Aqui está minha aplicação principal:

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();
    }
}
3
  • 1
    if (!flag) e if (flag == false) são a mesma coisa. Commented 31/10/2019 às 19:14
  • Sim, é que no primeiro flag se ele for true, eu não quero que ele entre naquele bloco de código, pois daria NullPointerException, já que o no.getEsquerda() seria justamente da folha, do nó que acabei de anular. Já na segunda flag, ela só fica true quando acha a folha, quando não, ela permanece false. daí fiz esse bloco de código para o no pai, anular a referência ao nó que acabou de ser removido, quando a pilha de execução da recursividade voltar para o pai. Commented 31/10/2019 às 19:44
  • Você não possui nenhum código que possa modificar o valor dessa flag entre as duas comparações. Commented 3/11/2019 às 20:07

1 Resposta 1

3

Pelo que entendi, esta é uma árvore binária de busca. Sendo assim, o algoritmo para remover um nó deve levar em conta alguns casos:

  1. se o nó for uma folha (ou seja, não tem sub-árvore direita nem esquerda), é só removê-lo:

Ex:

  10
 /  \
5    15
    /
   12

Para remover o 12 é fácil: como ele não tem filhos, é só retirá-lo da árvore.

  10
 /  \
5    15
  1. nó só tem um filho: substitua o nó pelo filho

Ex:

  10
 /  \
5    15
    /
   12
  /  \
 11  13

Para remover o 15: como ele só tem um filho (que é o nó 12), basta substituí-lo pelo filho.

  10
 /  \
5    12
    /  \
   11  13
  1. se o nó tem 2 filhos:
    • encontre o maior dos filhos que estão na sub-árvore à esquerda
    • copie o valor do maior filho para o nó
    • remova recursivamente o filho da sub-árvore esquerda

Ex:

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

Para remover o 15:

  • encontre o maior filho da sub-árvore esquerda: no caso é o 13
  • substituia o valor de 15 por este maior filho:
  10
 /  \
5    13
    /  \
   12  17
  /  \
 11  13
  • recursivamente remova o 13 da sub-árvore esquerda (ou seja, começo a remover o 13 a partir do 12):
    • o algoritmo vai procurando recursivamente pelo 13, e como a busca foi feita a partir do 12, ele chega no 13 debaixo. E quando ver que ele não tem filhos, cai no caso 1 (ele é simplesmente removido):
  10
 /  \
5    13
    /  \
   12  17
  /
 11

O algoritmo acima e o código abaixo foram adaptados deste artigo. No seu caso ficaria assim:

// 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;
}

Se só quer remover as folhas (de acordo com este comentário), basta adaptar o algoritmo acima para ignorar os casos em que o nó não é folha:

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;
}
5
  • Obrigado pela resposta, vai me ajudar muito futuramente. mas no momento eu só quero remover uma folha, só estou fazendo um método remover exclusivamente pra isso. O meu método remover funciona da seguinte maneira: ele verifica se o nó é folha, e é o nó procurado pra remover. após isso, se ele acha o nó, ele anula ele e seta a flag true. como a flag está true, ela não entra no bloco de código que aplica a recursividade: remover(no.getEsquerda(), valor); a flag evita um NullPointerException já que não entra nesse código. Commented 1/11/2019 às 1:17
  • Se a flag é false, quando a recursividade volta para o nó pai que foi removido, ele anula a referência ao nó que foi excluido. Este código parece estar completo para mim, só que ele simplismente não remove o nó, não entendo o porque. Desde já agradeço por ter me respondido, após remover a folha, vou criar um método pra remover um nó que só tenha um filho, depois um nó que tenha dois, daí juntarei tudo pra fazer tudo isso em um remover só. este é um processo lento mas é necessário para eu aprender, Obrigado. Commented 1/11/2019 às 1:20
  • 1
    @GabrielHenrique Eu acho que não precisa desta flag, basta adaptar o algoritmo de remoção para ignorar os casos em que o nó não é folha. Atualizei a resposta com esta opção.
    – hkotsubo
    Commented 2/11/2019 às 12:57
  • Muito obrigado, como eu marco a pergunta como solucionada ? Commented 7/11/2019 às 16:17
  • @GabrielHenrique É só clicar no ✓ no lado esquerdo da resposta (aqui tem instruções mais detalhadas, caso vc não encontre)
    – hkotsubo
    Commented 7/11/2019 às 16:22

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 .