Resolvido - Método de Remoção de nós em Árvore Binária

This message was edited 1 time. Last update was at 10/12/2009 22:36:44

Boa noite galera,
preciso de uma ajuda com um trabalho de faculdade que estou fazendo onde tenho que remover nós de uma árvore binária, porém, não sei se é o método pra imprimir ou meu método de remoção que não está funcionando corretamente. Quando removo um nó que possui filhos, aparentemente os filhos perdem a referencia com o pai do nó removido e na hora de imprimir os elementos na tela, os filhos não são exibidos. Peço que deem uma olhada e tentem me ajudar a solucionar o erro.
Desde já, obrigado !

public class ArvoreBinariaOrdenada {
    //metodo main
    public static void main(String[] args) {
        
        double notas[]=new double[3];
        int matricula;
        String nome;
        String disciplina;
        String resposta;
        String respostaRepeticao;
        boolean continua=true;
        int RemoverMatricula;
        int funcao;
        boolean repeteOperacao=true;

Arvore MaryJane = new Arvore();
        System.out.println("EXEMPLO DE ARVORE BINARIA");

while(repeteOperacao==true){
            System.out.println("Digite:");
            System.out.println("1 para inserir nós na árvore");
            System.out.println("2 para remover nós da árvore");
            System.out.println("3 para exibir os nós da árvore em ordem crescente do número de matrícula");
            funcao=SavitchIn.readLineInt();
            if(funcao==1){
                continua=true;
                while(continua==true){
                    System.out.println("Digite a matricula do aluno que quer incluir na árvore");
                    matricula=SavitchIn.readLineInt();
                    System.out.println("Digite o nome do aluno que quer incluir na árvore");
                    nome=SavitchIn.readLineWord();
                    System.out.println("Digite a disciplina do aluno que quer incluir na árvore");
                    disciplina=SavitchIn.readLineWord();
                    for(int i=0;i<notas.length;i++){
                        System.out.println("Digite a "+(1+i)+"ª nota do aluno que quer incluir na árvore");
                        notas[i]=SavitchIn.readLineDouble();
                    }

Aluno UniBH=new Aluno(matricula,nome,disciplina,notas);//cria objetos do tipo Aluno
                    MaryJane.insereNo(UniBH);
                    resposta="";
                    System.out.println("Deseja incluir mais um aluno? (S/N)");
                    resposta=SavitchIn.readLineWord();
                    if(resposta.equals("s")||resposta.equals("S")){
                        continua=true;
                    }else if(resposta.equals("n")||resposta.equals("N")){
                        continua=false;
                    }
                }
            }
            if(funcao==2){
                continua=true;
                while(continua==true){
                    System.out.println("Digite a matricula do aluno que deseja remover da árvore");
                    RemoverMatricula=SavitchIn.readLineInt();
                    MaryJane.remover(MaryJane.raiz, RemoverMatricula);
                    resposta="";
                    System.out.println("Deseja excluir mais um aluno? (S/N)");
                    resposta=SavitchIn.readLineWord();
                    if(resposta.equals("s")||resposta.equals("S")){
                        continua=true;
                    }else if(resposta.equals("n")||resposta.equals("N")){
                        continua=false;
                    }
                }
            }
            if(funcao==3){
                continua=true;
                while(continua==true){
                    System.out.println("Em-Ordem:");
                    MaryJane.Imprimeemordem(MaryJane.raiz);
                    System.out.println("");
                    resposta="";
                    System.out.println("Deseja exibir a arvore mais uma vez? (S/N)");
                    resposta=SavitchIn.readLineWord();
                    if(resposta.equals("s")||resposta.equals("S")){
                        continua=true;
                    }else if(resposta.equals("n")||resposta.equals("N")){
                        continua=false;
                    }
                }
            }
            System.out.println("Deseja realizar outra operacao? (S/N)");
            respostaRepeticao=SavitchIn.readLineWord();
            if(respostaRepeticao.equals("s")||respostaRepeticao.equals("S")){
                repeteOperacao=true;
            }
            if(respostaRepeticao.equals("n")||respostaRepeticao.equals("N")){
                repeteOperacao=false;
            }
        }
    }
}

public class Arvore {

No raiz;
    
    public Arvore(){
        this.raiz=null;
    }

public synchronized void insereNo(Aluno inserido){
        if(this.raiz==null){
            raiz=new No(inserido);
        }
        else{
            raiz.inserir(raiz, inserido);
        }
    }

public No remover(No node, int matricula) {
            System.out.println("Percorrendo No com a matricula " + node.valor.matricula);
            if (node == null) {
                System.out.println("Arvore vazia ");
            }
            if (matricula < node.valor.matricula) {
                node.esquerda = remover(node.esquerda, matricula);
            }
            else if (matricula > node.valor.matricula) {
                node.direita = remover(node.direita, matricula);
            }

else if (node.esquerda != null && node.direita != null){
                System.out.println("Removeu No com a matricula " + node.valor.matricula);
                node.valor.matricula = node.encontraMinimo(node.direita).valor.matricula;
                node.direita = node.removeMinimo(node.direita);
            }
            else {
                System.out.println("Removeu No com a matricula " + node.valor.matricula);
                node = (node.esquerda == null) ? node.esquerda : node.direita;
            }
            return node;
        }
    
    public void Imprimeemordem(No nodo){
            if(nodo==null) return;

Imprimeemordem(nodo.esquerda);
            if(nodo.valor.aprovado==true){
                System.out.println("Matricula: "+nodo.valor.matricula);
                System.out.println("Nome:"+nodo.valor.nome);
                System.out.println("Disciplina: "+nodo.valor.disciplina);
                System.out.println("Resultado: Aprovado");

}else{
                System.out.println("Matricula: "+nodo.valor.matricula);
                System.out.println("Nome:"+nodo.valor.nome);
                System.out.println("Disciplina: "+nodo.valor.disciplina);
                System.out.println("Resultado: Reprovado");
            }
            Imprimeemordem(nodo.direita);
    }
}

//classe No com tres atributos
    public class No {

No esquerda;
        No direita;
        Aluno valor;

public No(Aluno valor) {
            this.valor = valor;
        }
        public void inserir(No node, Aluno valor) {
            if(valor.matricula < node.valor.matricula){
                if (node.esquerda != null) {
                    inserir(node.esquerda, valor);
                }else{
                    System.out.println("Inserindo "+valor.matricula+" a esquerda da matricula " + node.valor.matricula);
                    node.esquerda = new No(valor);
                }
            }else if(valor.matricula > node.valor.matricula){
                if (node.direita != null) {
                    inserir(node.direita, valor);
                }else{
                    System.out.println("Inserindo "+valor.matricula+" a direita da matricula " + node.valor.matricula);
                    node.direita = new No(valor);
                }
            }
        }
        
        public No removeMinimo(No node) {
            if (node == null) {
                System.out.println("ERRO");
            } else if (node.esquerda != null) {
                node.esquerda = removeMinimo(node.esquerda);
                return node;
            } else {
                return node.direita;
            }
            return null;
        }

public No encontraMinimo(No node) {
            if (node != null) {
                while (node.esquerda != null) {
                    node = node.esquerda;
                }
            }
            return node;
        }

}

JavaGuru Membro desde: 27/03/2009 17:08:37 Mensagens: 243 Offline

Rapaz... para remover nó em árvore binária não basta apagar o nó.

Um dos nós filhos tem que ocupar o lugar do nó pai que foi removido, ou tudo abaixo daquele nó deixa de fazer parte da árvore.

Você tem que aplicar aqueles algoritmos de giro, sabe? (Se não sabe, dê uma pesquisada sobre remoção de nós em árvores binárias e depois poste as novas dúvidas aqui).

This message was edited 1 time. Last update was at 08/12/2009 19:07:50

eu não estou conseguindo imaginar exatamente como irei mudar o método para levar um dos filhos para o lugar do pai quando remove-lo, será que poderia me dar algumas dicas, tenho que entregar o trabalho amanhã e já tem duas semanas q não paro de mexer nele.
Outra coisa, se tem criticas construtivas a fazer a respeito de mudanças no código, por favor não se contenham. =D

Agradeço a ajuda,

Diogo

JavaGuru Membro desde: 27/03/2009 17:08:37 Mensagens: 243 Offline

Dá uma olhada nesse link.

http://www.cs.usask.ca/content/resources/csconcepts/1998_6/bintree/2-5.html

Se não for necessário balanço na árvore pode fazer o método porco:
- Quando for tirar um nó, escolha um dos filhos(1) e insira o outro filho(2) e sua sub-arvore no fim da árvore(1), aí defina o filho(1) no lugar do pai. Isso vai desbalancear muito a árvore mas é um algoritmo bem fácil de fazer;

Ou se fizer da maneira mais normal:
- Quando for retirar o pai, pegue o último elemento(que vai ser uma folha) de um dos filhos e coloque no lugar do pai, assinale os filhos anteriores nesse elemento novo.

Ou se precisar manter ordem, vai ter que brincar de rotacionar para direita e esquerda.

Até!

Uma maneira mais fácil de fazer isso é você criar na classe No, da sua árvore, um nó que guarda o endereço do pai, aí quando for remover um determinado nó é só verificar se esse nó contem filho ou filhos e determinar o qual ocupará a posição do nó removido.

Não é necessário a classe No ter a informação do pai, mas é necessário que quando for remover um elemento você tenha um nó parental na árvore(em geral a raiz ou o pai do no a ser removido) e o nó que você quer remover. Faça uma busca pelo nó que você quer remover através do nó parental e no final vai acabar tendo o pai ( se você já não o passou ) e o nó a ser removido. Agora é mão na massa.

Ae galera, valeu as dicas... Consegui resolver o problema...agora ta tudo funfando de boa...

Main

public class ArvoreBinariaOrdenada {

public static void main(String[] args) {
        
        double notas[]=new double[3];
        int matricula;
        String nome;
        String disciplina;
        String resposta;
        String respostaRepeticao;
        boolean continua=true;
        int RemoverMatricula;
        int funcao;
        boolean repeteOperacao=true;

Arvore MaryJane = new Arvore();
        System.out.println("EXEMPLO DE ARVORE BINARIA");

while(repeteOperacao==true){
            System.out.println("Digite:");
            System.out.println("1 para inserir nós na árvore");
            System.out.println("2 para remover nós da árvore");
            System.out.println("3 para exibir os nós da árvore em ordem crescente do número de matrícula");
            funcao=SavitchIn.readLineInt();
            if(funcao==1){
                continua=true;
                while(continua==true){
                    System.out.println("Digite a matricula do aluno que quer incluir na árvore");
                    matricula=SavitchIn.readLineInt();
                    System.out.println("Digite o nome do aluno que quer incluir na árvore");
                    nome=SavitchIn.readLineWord();
                    System.out.println("Digite a disciplina do aluno que quer incluir na árvore");
                    disciplina=SavitchIn.readLineWord();
                    for(int i=0;i<notas.length;i++){
                        System.out.println("Digite a "+(1+i)+"ª nota do aluno que quer incluir na árvore");
                        notas[i]=SavitchIn.readLineDouble();
                    }

Aluno UniBH=new Aluno(matricula,nome,disciplina,notas);//cria objetos do tipo Aluno
                    MaryJane.insereNo(UniBH);
                    resposta="";
                    System.out.println("Deseja incluir mais um aluno? (S/N)");
                    resposta=SavitchIn.readLineWord();
                    if(resposta.equals("s")||resposta.equals("S")){
                        continua=true;
                    }
                    if(resposta.equals("n")||resposta.equals("N")){
                        continua=false;
                    }
                }
            }
            if(funcao==2){
                continua=true;
                while(continua==true){
                    System.out.println("Digite a matricula do aluno que deseja remover da árvore");
                    RemoverMatricula=SavitchIn.readLineInt();
                    MaryJane.removeNo(RemoverMatricula);
                    resposta="";
                    System.out.println("Deseja excluir mais um aluno? (S/N)");
                    resposta=SavitchIn.readLineWord();
                    if(resposta.equals("s")||resposta.equals("S")){
                        continua=true;
                    }
                    if(resposta.equals("n")||resposta.equals("N")){
                        continua=false;
                    }
                }
            }
            if(funcao==3){
                continua=true;
                while(continua==true){
                    System.out.println("Impressão em ordem crescente de numero de matricula:");
                    System.out.println("");
                    MaryJane.Imprimeemordem(MaryJane.raiz);
                    System.out.println("");
                    resposta="";
                    System.out.println("Deseja exibir a arvore mais uma vez? (S/N)");
                    resposta=SavitchIn.readLineWord();
                    if(resposta.equals("s")||resposta.equals("S")){
                        continua=true;
                    }
                    if(resposta.equals("n")||resposta.equals("N")){
                        continua=false;
                    }
                }
            }
            respostaRepeticao="";
            System.out.println("Deseja realizar outra operacao? (S/N)");
            respostaRepeticao=SavitchIn.readLineWord();
            if(respostaRepeticao.equals("s")||respostaRepeticao.equals("S")){
                repeteOperacao=true;
            }
            if(respostaRepeticao.equals("n")||respostaRepeticao.equals("N")){
                repeteOperacao=false;
            }
        }
    }
}

Classe Árvore

public class Arvore {

No raiz;//atributo do tipo Nó representando a raiz da arvore binaria
    
    public Arvore(){//construtor da classe arvore atribuindo valor inicial pra raiz = null
        this.raiz=null;
    }

public synchronized void insereNo(Aluno inserido){//metodo para inserir nós na árvore
        if(this.raiz==null){//se a raiz é nula
            raiz=new No(inserido);//cria objeto do tipo Nó, com o parametro inserido e cria o primeiro nó da árvore
        }
        else{//se já possuir uma raiz na árvore
            raiz.inserir(raiz, inserido);//chama o método inserir passando a raiz e o valor a ser inserido no novo nó
        }
    }
    public No procuraNo(int matricula){//metodo para procurar um nó específico passando o numero de matricula do aluno
          No current = raiz;//cria uma variavel do tipo Nó representando o nó atual a ser buscado e atribui ao nó o valor do nó raiz
          while(current.valor.matricula != matricula){//enquanto a matricula a ser procurada é diferente da matricula do nó atual, repetir a operação
             if(matricula < current.valor.matricula) //se a matricula a ser procurada for menor do que a matricula do nó atual
                current = current.esquerda;//atribui ao nó atual o valor do nó do lado esquerdo, de modo a repetir a funcao
             else //se a matricula a ser procurada for maior do que a matricula do nó atual
                current = current.direita;//atribui ao nó atual o valor do nó do lado direito, de modo a repetir a funcao
             if(current == null)//se o nó atual é nulo
                return null;//retorna o nó como nulo, já que o mesmo nao foi encontrado.
          }
          return current;                   
    }

public boolean removeNo(int matricula){//metodo para remover nós da árvore, passando o parametro de numero de matricula do aluno a ser removido
          No current = raiz;//cria uma variavel do tipo Nó representando o nó atual a ser buscado
          No parent = raiz;//cria uma variavel do tipo Nó representando o nó pai do nó a ser removido
          boolean isLeftChild = true;//variavel boolean (true=o nó é o filho da esquerda) (false=o nó não é o filho da esquerda)

while(current.valor.matricula != matricula){//igual ao metodo de procura, enquanto o valor da matricula a ser encontrada for diferente do valor da matricula do nó atual a ser buscado, repete a operação
                parent = current;//Nó pai recebe o valor do Nó atual
                if(matricula < current.valor.matricula){//se a matricula a ser procurada for menor do que a matricula do nó atual
                    isLeftChild = true;//a variavel boolean recebe true para indicar que é um filho do lado esquerdo do nó
                    current = current.esquerda;//atribui ao nó atual o valor do nó do lado esquerdo, de modo a repetir a funcao
                }
                else{//se a matricula a ser procurada for maior do que a matricula do nó atual
                    isLeftChild = false;//a variavel boolean recebe false para indicar que não é um filho do lado esquerdo do nó
                    current = current.direita;//atribui ao nó atual o valor do nó do lado direito, de modo a repetir a funcao
                }
                if(current == null)//se o nó atual é nulo
                    return false;//retorna false ja que a matricula nao foi encontrada na árvore
          }
          if(current.esquerda==null && current.direita==null){//se o nó atual não possuir filhos de nenhum dos lados
              if(current == raiz)//se o nó atual é a raiz da árvore
                  raiz = null;//remove o nó raiz transformando a árvore em uma árvore vazia
              else if(isLeftChild)//se o nó for um filho do lado esquerdo
                  parent.esquerda = null;//atribui valor null para o nó do lado esquerdo
              else//se o nó for um filho do lado direito
                  parent.direita = null;//atribui valor null para o nó do lado direito
          }
          else if(current.direita==null)//se apenas o filho do lado direito é nulo
            if(current == raiz)//se o nó atual é igual a raiz
                raiz = current.esquerda;//passa o nó do filho da esquerda para o lugar da raiz
            else if(isLeftChild)//se o nó atual é um filho da esquerda
                parent.esquerda = current.esquerda;//o nó da esquerda do pai recebe o filho da esquerda do nó atual
            else//se o nó atual é um filho da direita
                parent.direita = current.esquerda;//o nó da direita do pai recebe o filho da direita do nó atual
        
          else if(current.esquerda==null)//se apenas o filho do lado esquerdo é nulo
            if(current == raiz)//se o nó atual é igual a raiz
                raiz = current.direita;//passa o nó do filho da direita para o lugar da raiz
            else if(isLeftChild)//se o nó atual é um filho da esquerda
                parent.esquerda = current.direita;//o nó da esquerda do pai recebe o filho da direita do nó atual
            else///se o nó atual é um filho da direita
                parent.direita = current.direita;////o nó da direita do pai recebe o filho da direita do nó atual

else{//se o nó a ser removido possuir dois filhos, então o nó com o numero de matricula seguinte ao nó a ser removido toma seu lugar
                No successor = getSuccessor(current);//chama o metodo getSuccessor que passa o nó atual como parametro e retorna o nó com a matricula seguinte ao nó a ser removido.
                if(current == raiz)//se o nó a ser removido for a raiz
                    raiz = successor;//o nó com numero de matricula seguinte toma o lugar da raiz
                else if(isLeftChild)//se o nó a ser removido é um filho do lado esquerdo
                    parent.esquerda = successor;//o nó com o numero de matricula seguinte toma o lugar do nó filho do lado esquerdo
                else//se o nó a ser removido é um filho do lado direito
                    parent.direita = successor;//o nó com o numero de matricula seguinte toma o lugar do nó filho do lado direito

successor.esquerda = current.esquerda;//o filho do lado esquerdo do nó que possui a matricula seguinte ao nó a ser removido recebe atribuicao ao nó atual do lado esquerdo
          }
          return true;
    }
    public No getSuccessor(No delNode){//metodo que ajuda o metodo de remover, ao achar o nó com o número de matricula posterior ao passado como parametro, esse nó é retornado
                No successorParent = delNode;//variavel do tipo nó representando o nó pai do nó sucessor ao nó a ser removido que recebe por atribuição o valor do nó passado como parametro
		No successor = delNode;//variavel do tipo nó representando o nó sucessor ao nó a ser removido que recebe por atribuição o valor do nó passado como parametro
		No current = delNode.direita;////variavel do tipo nó representando o nó atual que recebe por atribuição o filho do lado direito do nó passado como parametro

while(current != null){//enquanto o nó atual for diferente de nulo, repetir a operação
                        successorParent = successor;//o nó pai do nó sucessor recebe o sucessor
			successor = current;//o nó sucessor recebe o atual
			current = current.esquerda;//e o nó atual recebe o filho do lado esquerdo do nó atual
		}
		if(successor != delNode.direita){//se o nó sucessor for diferente do nó filho do lado direito do nó passado como parametro
			successorParent.esquerda = successor.direita;//o filho do lado esquerdo do nó pai do nó sucessor recebe o filho do lado direito do nó sucessor
		 	successor.direita = delNode.direita;//o nó filho do lado direito do nó sucessor recebe o filho do lado direito do nó passado como parametro
		}
		return successor;//retorna o nó que contem o numero de matricula seguinte ao passado como parametro
    }

public void Imprimeemordem(No nodo){//método para impressao em ordem crescente do numero de matricula
            if(nodo==null) return;//se não existir o nodo, para a execução do metodo

Imprimeemordem(nodo.esquerda);//chama o metodo recursivamente pro lado esquerdo
            if(nodo.valor.aprovado==true){//se o aluno foi aprovado na disciplina exibir:
                System.out.println("Matricula: "+nodo.valor.matricula);
                System.out.println("Nome:"+nodo.valor.nome);
                System.out.println("Disciplina: "+nodo.valor.disciplina);
                System.out.println("Resultado: Aprovado");
                System.out.println("");
            }else{//se o aluno nao foi aprovado na disciplina exibir:
                System.out.println("Matricula: "+nodo.valor.matricula);
                System.out.println("Nome:"+nodo.valor.nome);
                System.out.println("Disciplina: "+nodo.valor.disciplina);
                System.out.println("Resultado: Reprovado");
                System.out.println("");
            }
            Imprimeemordem(nodo.direita);//chama o metodo recursivamente pro lado direito
    }
}

Classe Nó

//classe No com dois filhos e o conteúdo do tipo Aluno
    public class No {

No esquerda;//filho da esquerda
        No direita;//filho da direita
        Aluno valor;//conteúdo do Nó

public No(Aluno valor) {//construtor do Nó atribuindo valor e iniciando os filhos como null
            this.valor = valor;
            this.direita = this.esquerda = null;
        }
        public void inserir(No node, Aluno valor) {//método para inserir nós na árvore
            if(valor.matricula < node.valor.matricula){//se a matricula do aluno a inserir é menor que a do nó atual
                if (node.esquerda != null) {//se já existir um nó do lado esquerdo do nó atual
                    inserir(node.esquerda, valor);//chama a funcao recursiva inserir do lado esquerdo do nó atual
                }else{//se não existir nó do lado esquerdo
                    System.out.println("Inserindo "+valor.matricula+" a esquerda da matricula " + node.valor.matricula);
                    node.esquerda = new No(valor);//cria novo nó com o valor passado em parametro e insere-o na árvore do lado esquerdo do nó atual
                }
            }else if(valor.matricula > node.valor.matricula){//se a matricula do aluno a inserir é maior que a do nó atual
                if (node.direita != null) {//se já existir um nó do lado direito do nó atual
                    inserir(node.direita, valor);//chama a funcao recursiva inserir do lado direito do nó atual
                }else{//se não existir nó do lado direito
                    System.out.println("Inserindo "+valor.matricula+" a direita da matricula " + node.valor.matricula);
                    node.direita = new No(valor);//cria novo nó com o valor passado em parametro e insere-o na árvore do lado direito do nó atual
                }
            }
        }
        
        
    }

Classe Aluno

Notícias, artigos e o maior fórum brasileiro sobre Java