Trabalhando com árvores binárias em Java

Você precisa estar logado para dar um feedback. Clique aqui para efetuar o login
Para efetuar o download você precisa estar logado. Clique aqui para efetuar o login
Confirmar voto
0
 (8)  (1)

Veja neste artigo o que é uma árvore binária, suas propriedades, seus usos nas aplicações existentes e exemplos de implementação e execução.

Introdução

Existem os mais diferentes tipos de árvores, no entanto, as árvores binárias são especiais e muito utilizadas nas mais diversas aplicações porque quando ordenadas permitem que pesquisas, inclusões e exclusões de dados em sua estrutura sejam extremamente rápidas.

Conceitos

As árvores são estruturas de dados baseadas em listas encadeadas que possuem um nó superior também chamado de raiz que aponta para outros nós, chamados de nós filhos, que podem ser pais de outros nós.

Uma árvore de busca binária tem as seguintes propriedades:

  • todos os elementos na subárvore esquerda de um determinado nó n são menores que n;
  • todos os elementos na subárvore direita de um determinado nó n são maiores ou iguais a n.

Segue abaixo uma ilustração de um exemplo de árvore binária:

Exemplo ilustrativo de uma Árvore Binária

Figura 1: Exemplo ilustrativo de uma Árvore Binária

No exemplo acima tem-se uma árvore binária onde a raiz é o elemento 8, o filho da esquerda do elemento 8 é o elemento 3, o filho da direita é o elemento número 10. Nota-se que todos elementos da árvore binária possuem no máximo dois filhos, sendo o da esquerda sempre menor e o da direita sempre maior que o elemento pai.

Implementação

Agora que já se conhece um pouco mais sobre o que é e como funciona uma árvore binária, vejamos abaixo os algoritmos para inserção e exclusão em árvores binárias implementados na linguagem Java.

Segue abaixo o código de exemplo para inserção em árvores binárias:

Listagem 1: Exemplo de inserção em árvores binárias

    public void inserir(No node, int valor) {
      //verifica se a árvore já foi criada
       if (node != null) {
        //Verifica se o valor a ser inserido é menor que o nodo corrente da árovre, se sim vai para subarvore esquerda
        if (valor < node.valor) {
            //Se tiver elemento no nodo esquerdo continua a busca
            if (node.esquerda != null) {
                inserir(node.esquerda, valor);
            } else {
                //Se nodo esquerdo vazio insere o novo nodo aqui
                System.out.println("  Inserindo " + valor + " a esquerda de " + node.valor);
                node.esquerda = new No(valor);
            }
        //Verifica se o valor a ser inserido é maior que o nodo corrente da árvore, se sim vai para subarvore direita
        } else if (valor > node.valor) {
            //Se tiver elemento no nodo direito continua a busca
            if (node.direita != null) {
                inserir(node.direita, valor);
            } else {
                //Se nodo direito vazio insere o novo nodo aqui
                System.out.println("  Inserindo " + valor + " a direita de " + node.valor);
                node.direita = new No(valor);
            }
        }
      }
    }

Pode-se notar que o algoritmo funciona recursivamente, chamando a função repetidas vezes. Os detalhes do código estão exemplificados através dos comentários no seu corpo.

Abaixo apresenta-se um algoritmo alternativo para exclusão em árvores binárias:

Listagem 2: Exemplo de exclusão em árvores binárias

    public No removeValorMinimoDaArvore(No node) {
        if (node == null) {
            System.out.println("  ERRO ");
        } else if (node.esquerda != null) {
            node.esquerda = removeValorMinimoDaArvore(node.esquerda);
            return node;
        } else {
        	//Se não tiver elemento esquerdo só nós resta o da direita
            return node.direita;
        }
        return null;
    }

No código acima nota-se que o menor elemento da árvore está sendo excluído, o código também poderia ser implementado recebendo um nó a ser excluído, procurar este nó e excluir da árvore. O caminhamento em árvores será descrito a seguir. Nota-se que os elementos filhos tomam a posição do elemento excluído.

Caminhamentos

Uma árvore binária pode ser percorrida utilizando caminhamento prefixado, pós-fixado e em ordem, todos serão detalhados abaixo.

Caminhamento Prefixado

Basicamente no caminhamento prefixado será utilizado o algoritmo abaixo:

Executa-se a ação a ser realizada
Recursivamente percorre-se a subárvore esquerda
Recursivamente percorre-se a subárvore direita

O algoritmo utilizando recursão torna-se extremamente simples. Portanto vejamos na prática como isso é feito em linguagem Java, dado que o método recebe a raiz da árvore.

Listagem 3: Exemplo de caminhamento prefixado em árvores binárias

    public void prefixado(No no) {
        if(no != null){
            System.out.print(no.valor + " ");
            prefixado(no.esquerda);
            prefixado(no.direita);
        }
    }

Para o exemplo da árvore acima ter-se-ia a seguinte ordem de visita dos nós: 8, 3, 1, 6, 4, 7, 10, 14, 13.

Para o leitor entender um pouco melhor como funciona esse algoritmo e os demais para caminhamentos em árvores binárias, será detalhada a pilha de chamadas para esta árvore. Portanto, para a árvore dada anteriormente temos a seguinte linha de execução:

  • imprime(8) //inicialmente executa-se a impressão do valor

  • preordem(8.esquerda) //chama prefixado(no.esquerda);
  • Imprime(3) //ao chamar novamente o método imprime o 3 que é o nó corrente
  • preordem(3.esquerda) //chama prefixado(no.esquerda);
  • Imprime(1) //ao chamar novamente o método imprime o 1 que é o nó corrente
  • preordem(1.esquerda) //chama prefixado(no.esquerda);
  • preordem(1.dir) //como prefixado(no.esquerda) retornou null, executa-se agora o prefixado(no.direita)
  • preordem(3.dir) //como prefixado(no.direita) é null, volta-se para o elemento anterior que é o 3 (antes do 1). Como o 1 também já executou o prefixado(no.esquerda) executa-se agora o prefixado(no.direita)
  • Imprime(6) //ao chamar novamente o método imprime o 6 que é o nó corrente
  • preordem(6.esquerda) //chama prefixado(no.esquerda) que ainda não foi chamado para este elemento.
  • Imprime(4) //ao chamar novamente o método imprime o 4 que é o nó corrente
  • preordem(4.esquerda) //chama prefixado(no.esquerda) que ainda não foi chamado para este elemento.
  • preordem(4.direita) //como prefixado(no.esquerda) retornou null, executa-se agora o prefixado(no.direita).
  • preordem(6.direita) //como prefixado(no.direita) é null, volta-se para o elemento anterior que é o 6 (antes do 4). Como o 6 também já executou o prefixado(no.esquerda) executa-se agora o prefixado(no.direita)
  • Imprime(7) //ao chamar novamente o método imprime o 7 que é o nó corrente.
  • preordem(7.esquerda) //chama prefixado(no.esquerda) que ainda não foi chamado para este elemento.
  • preordem(7.direita) //como prefixado(no.esquerda) retornou null, executa-se agora o prefixado(no.direita).
  • preordem(8.direita) //como prefixado(no.direita) é null, volta-se para o elemento anterior que é o 8. Como o 8 também já executou o prefixado(no.esquerda) executa-se agora o prefixado(no.direita)
  • Imprime(10) //ao chamar novamente o método, imprime-se o 10 que é o nó corrente
  • preordem(10.esquerda) //chama prefixado(no.esquerda) que ainda não foi chamado para este elemento.
  • preordem(10.direita) //como prefixado(no.esquerda) retornou null, executa-se agora o prefixado(no.direita).
  • Imprime(14) //ao chamar novamente o método, imprime-se o 14 que é o nó corrente
  • preordem(14.esquerda) //chama prefixado(no.esquerda) que ainda não foi chamado para este elemento.
  • Imprime(13) //ao chamar novamente o método, imprime-se o 13 que é o nó corrente
  • preordem(13.esquerda) //chama prefixado(no.esquerda) que ainda não foi chamado para este elemento.
  • preordem(13.direita) //como prefixado(no.esquerda) retornou null, executa-se agora o prefixado(no.direita).
  • preordem(14.direita) //como prefixado(no.direita) é null, volta-se para o elemento anterior que é o 14. Como o 14 também já executou o prefixado(no.esquerda) executa-se agora o prefixado(no.direita) que também é null. Agora nota-se que não há mais nada na pilha, todos os elementos e seus filhos esquerdos e direitos já foram executados, portanto está finalizado o algoritmo.

Caminhamento Pós-fixado

Basicamente no caminhamento Pós-fixado será utilizado o algoritmo abaixo:

Recursivamente percorre-se a subárvore esquerda
Recursivamente percorre-se a subárvore direita
Executa-se a ação a ser realizada

Pois vejamos também para o algoritmo acima na prática como isso é feito em linguagem Java, dado que o método recebe a raiz da árvore.

Listagem 4: Exemplo de caminhamento posfixado em árvores binárias


    public void posfixado(No no) {
        if(no != null){
        	posfixado(no.esquerda);
        	posfixado(no.direita);
            System.out.print(no.valor + " ");
        }
    }

Para o exemplo da árvore acima ter-se-ia a seguinte ordem de visita dos nós: 1, 4, 7, 6, 3, 13, 14, 10, 8.

Baseando-se na pilha de execução explicada anteriormente fica muito simples de entender o que esse algoritmo faz e qual ordem ele segue.

Caminhamento Em Ordem

Basicamente no caminhamento Em Ordem será utilizado o algoritmo abaixo:

Recursivamente percorre-se a subárvore esquerda
Executa-se a ação a ser realizada
Recursivamente percorre-se a subárvore direita

Então vejamos também para o algoritmo acima na prática como isso é feito em linguagem Java, dado que o método também recebe a raiz da árvore.

Listagem 5: Exemplo de caminhamento em ordem em árvores binárias

    public void emordem(No no) {
        if(no != null){
        	emordem(no.esquerda);
		System.out.print(no.valor + " ");
        	emordem(no.direita);
        }
    }

Para o exemplo da árvore acima ter-se-ia a seguinte ordem de visita dos nós: 1, 3, 4, 6, 7, 8, 10, 13, 14.

Aplicações

Árvores binárias são largamente utilizadas em diversas aplicações. Entre as aplicações pode-se citar as árvores de decisão usadas na Inteligência Artificial. Outra aplicação é na representação de expressões aritméticas. No caso da representação das expressões aritméticas pode-se utilizar um caminhamento pós-fixado para resolver o problema, onde, por exemplo, para uma árvore binária de expressões aritméticas ter-se-ia para cada nó externo um valor associado e para cada nó interno um operador aritmético associado, esse algoritmo calcularia facilmente o resultado da expressão. Sugerimos ao leitor tentar este exercício e em caso de dúvidas contate o autor para fornecer as respostas para as dúvidas.

Conclusão

Neste artigo procurou-se demonstrar alguns conceitos e como essa importante estrutura de dados é implementada na prática na linguagem de programação Java. As suas vantagens, peculiaridades que lhe fazem ser uma árvore binária, sua implementação e detalhes da sua execução foram demonstradas neste artigo.

Pessoal, como observação reitero que eu não coloquei o código completo com a execução (a partir de um método main) e a estrutura do nó por ser extremamente simples e para fins de não alongar muito o tamanho do artigo. Se quiserem o código completo não deixem de me contatar no meu e-mail que eu passo o código sem problemas. Continuo atendendo à solicitações de artigos dos amigos leitores, este é mais um dos tantos requeridos e espero outra sugestões.

Bibliografia

PREISS, Bruno R. Estruturas de dados e algoritmos: Padrões de projetos orientados a objeto com Java; tradução de Elizabeth Ferreira. Rio de Janeiro: Campus, 2000.

 
Você precisa estar logado para dar um feedback. Clique aqui para efetuar o login
Ficou com alguma dúvida?