Você está aqui: Java ::: Estruturas de Dados ::: Árvore Binária e Árvore Binária de Busca

Como percorrer uma árvore binária em Java usando o algorítmo depth-first search (DFS) de forma iterativa

Quantidade de visualizações: 1052 vezes

Nesta dica mostrarei como podemos implementar o algorítmo da Busca em Profundidade (DFS, do inglês depth-first search) em Java de forma iterativa, ou seja, sem usar recursão. Não farei a busca, mas sim o percurso, para que você entenda como a lógica dessa busca funciona.

Antes de iniciarmos, veja a árvore binária que vamos usar no exemplo:

Note que esta árvore possui seis nós. O nó 5 é o nó raiz, e possui como filhos os nós 4 e 9. O nó 4, por sua vez, possui apenas um filho, o nó 2, ou seja, o filho da esquerda. O nó 9 possui dois filhos: o nó 3 é o filho da esquerda e o nó 12 é o filho da direita. Os filhos da árvore binária que não possuem outros filhos são chamados de folhas.

Com a abordagem da busca em profundidade, começamos com o nó raiz e viajamos para baixo em uma única ramificação. Se o nó desejado for encontrado naquela ramificação, ótimo. Do contrário, continuamos subindo e pesquisando por nós não visitados. Esse tipo de busca também tem uma notação big O de O(n).

Vamos à implementação? Veja o código para a classe No, que representa um nó na árvore binária:

Este trecho de código ou resolução de exercício faz parte do Super Pack 12.000 Dicas e Truques de Programação e 1.500 Exercícios Resolvidos em Java, Python, VisuAlg, Portugol, Delphi, C#, C, C++, VB.NET, Golang, Pascal, Ruby, PHP, e várias outras linguagens.

Aprenda a programar resolvendo problemas do mundo real. Tudo em português, com comentários em português.

Quero Ser Apoiador(a)

Veja agora o código completo para o exemplo. Note que usei uma implementação não-recursiva, na qual todos os nós expandidos recentemente são adicionados a uma pilha, para realizar a exploração. O uso da pilha permite o retrocesso (backtracking) de forma a reiniciarmos o percurso ou busca no próximo nó.

Para manter o código o mais simples possível, eu usei a classe Stack do Java, juntamente com seus métodos push() e pop() para simular a pilha. Usei também uma ArrayList para guardar os valores da árvore binária na ordem depth-first.

Eis o código:

Ao executarmos este código Java nós teremos o seguinte resultado:

Os valores na ordem Depth-First são: [5, 4, 2, 9, 3, 12]

Compare estes valores com a imagem vista anteriormente para entender ainda melhor o percurso ou busca Depth-First.

Link para compartilhar na Internet ou com seus amigos:

Desafios, Exercícios e Algoritmos Resolvidos de Java

Um programa que lê dois números inteiros e mostra o menor - Exercício Resolvido de Java

Como encontrar o menor valor em um ArrayList de inteiros usando o laço for - Exercício Resolvido de Java

Como testar se um valor está contido em um array em Java - Exercício Resolvido de Java

Como calcular a área de um triângulo usando a Fórmula de Heron em Java - Exercício Resolvido de Java

Escreva um programa Java que leia duas notas obtidas por um aluno na disciplina de Algoritmos e Programação de Computadores, o número de aulas ministradas - Exercício Resolvido de Java

Um programa que lê duas notas, calcula a média aritmética e exibe uma mensagem de reprovado, exame ou aprovado - Exercícios Resolvidos de Java

Como calcular a tabuada de multiplicação para os números de 1 a 9 em Java - Exercícios Resolvidos de Java

Como resolver problemas de razão e proporção em Java - Em uma empresa, a razão entre o número de mulheres e o número - Exercícios Resolvidos de Java

Listando arquivos e diretórios em um diretório informado pelo usuário - Exercícios Resolvidos de Java

Exemplo de interface e polimorfismo em Java - A interface Forma e as classes Retangulo e Circulo - Exercícios Resolvidos de Java

Dado um vetor de inteiros positivos, encontre a maior soma possível de N elementos consecutivos - Exercício Resolvido de Java

A classe Produto (construtores, métodos, getters e setters e encapsulamento) - Exercícios Resolvidos de Java

Como retornar o maior elemento em cada uma das linhas de uma matriz usando Java - Exercício Resolvido de Java

Como adicionar dias à uma data em Java - Escreva um programa Java que adiciona 3 dias à data atual - Exercícios Resolvidos de Java

Escrever um algoritmo que lê o público total de um jogo de futebol e fornece a renda do jogo - Exercícios Resolvidos de Java

Como rotacionar os elementos de um vetor de inteiros n vezes para a direita - Solução usando vetor temporário - Exercícios Resolvidos de Java

Algoritmos Resolvidos de Java - Escreva uma função Java que recebe graus em Celcius e retorna a temperatura correspondente em Fahrenheit - Exercícios Resolvidos de Java

Elabore um programa Java que solicita e armazena 3 notas de 5 alunos em uma matriz 5x3, ou seja, 5 linhas e 3 colunas. Por fim - Exercício Resolvido de Java

Usando o laço while para encontrar o MDC (Máximo Divisor Comum) de dois números - Exercício Resolvido de Java

Usando o laço do...while para pedir ao usuário para informar números inteiros e calcular a quantidade de números positivos, negativos, a soma e a média - Exercício Resolvido de Java

Métodos - Ex. 4 - Um método estático que recebe dois números inteiros e retorna o maior deles - Exercícios Resolvidos de Java

Crie uma classe Esfera contendo um atributo de instância chamado diametro, do tipo double. Defina um construtor público que receberá o valor do diâmetro - Exercícios Resolvidos de Java

Java Básico - Exercícios Resolvidos 28 - Um programa que lê o código e preço de um produto e dá descontos de acordo com uma tabela de faixa de preços - Exercícios Resolvidos de Java

Escreva um programa Java que pede para o usuário informar o dia, mês e ano e construa uma data usando um objeto da classe Calendar - Exercício Resolvido de Java

Uma locadora de carros aluga seus veículos cobrando uma taxa de R$ 25,00 reais a diária mais R$ 0,20 por quilômetro rodado - Exercício Resolvido de Java

A locadora de carros precisa da sua ajuda para cobrar seus serviços. Escreva um programa que pergunte a quantidade de Kms percorridos por um carro alugado - Exercício Resolvido de Java

Como calcular o comprimento de um segmento de reta usando Java - Exercícios Resolvidos de Java

Escreva um programa (algorítmo) Java que usa o laço for para exibir uma tabela de conversões de milhas para quilômetros - Exercício Resolvido de Java

Verifique se as componentes de um vetor de 10 componentes inteiros lidos pelo teclado formam uma progressão aritmética - Exercícios Resolvidos de Java

Como calcular e exibir os 50 primeiros números primos em Java - Exercício Resolvido de Java

Veja mais Dicas e truques de Java

Obter o nome do mês para a data atual

Um exemplo de JTree que obtém os itens a partir de um método (simples mesmo)

Gerando um número aleatório no intervalo de 10 a 20 usando Math.random

Java Swing - Como salvar o conteúdo de um JTextArea em um arquivo (usando um JFileChooser para localizar o diretório e arquivo)

Java para iniciantes - Como usar a classe Date em suas aplicações Java

Como somar os dígitos de um número em Java usando o laço while - Solução para número inteiro de qualquer tamanho

Aprenda a usar a classe Integer em seus programas Java

Exercícios Resolvidos de Java - Escreva um programa Java que mostre a data atual e a data que será daqui a 10 dias, ou seja, a data atual acrescida de 10 dias

Como copiar todos os elementos de um Vector Java para um array

Threads em Java - Como usar a interface Runnable da Java API em suas aplicações

Dicas e truques de outras linguagens

C - Como calcular o volume de chuvas em C - Fórmula do cálculo do volume de chuvas em C

Java - Como calcular o cosseno de um ângulo em Java usando o método cos() da classe Math - Calculadora de cosseno em Java

Java - Como excluir de uma ArrayList todos os elementos contidos em outra ArrayList ou coleção do Java usando o método removeAll()

Ruby - Como usar construtores em Ruby - Programação Orientada a Objetos em Ruby

Java - Manipulação de imagens em Java - Como converter uma imagem JPG colorida para uma imagem na escala cinza (gray scale)

C - Como usar protótipos de função em C

PHP - Como criar diretórios usando PHP - Como usar a função mkdir() da linguagem PHP para criar diretórios - Revisada

Java - Como retornar o menor valor em um array de inteiros em Java

JavaScript - JavaScript para iniciantes - Como obter o valor do maior número possível em JavaScript usando Number.MAX_VALUE

Delphi - Como adicionar ou subtrair dias de uma data em Delphi usando a função IncDay()

E-Books em PDF

E-Book 350 Exercícios Resolvidos de Java - PDF com 500 páginas

Domine lógica de programação e a linguagem Java com o nosso E-Book 350 Exercícios Exercícios de Java, para você estudar onde e quando quiser.

Este e-book contém exercícios resolvidos abrangendo os tópicos: Java básico, matemática e estatística, programação dinâmica, strings e caracteres, entrada e saída, estruturas condicionais, vetores e matrizes, funções, laços, recursividade, internet, arquivos e diretórios, programação orientada a objetos e muito mais.

Ver Conteúdo do E-book

E-Book 650 Dicas, Truques e Exercícios Resolvidos de Python - PDF com 1.200 páginas

Domine lógica de programação e a linguagem Python com o nosso E-Book 650 Dicas, Truques e Exercícios Exercícios de Python, para você estudar onde e quando quiser.

Este e-book contém dicas, truques e exercícios resolvidos abrangendo os tópicos: Python básico, matemática e estatística, banco de dados, programação dinâmica, strings e caracteres, entrada e saída, estruturas condicionais, vetores e matrizes, funções, laços, recursividade, internet, arquivos e diretórios, programação orientada a objetos e muito mais.

Ver Conteúdo do E-book

Linguagens Mais Populares

1º lugar: Java
2º lugar: Python
3º lugar: C#
4º lugar: PHP
5º lugar: C
6º lugar: Delphi
7º lugar: JavaScript
8º lugar: C++
9º lugar: VB.NET
10º lugar: Ruby

Você está aqui: Java ::: Estruturas de Dados ::: Árvore Binária e Árvore Binária de Busca

Como percorrer uma árvore binária em Java usando o algorítmo depth-first search (DFS) de forma iterativa

Questões de Concurso para Engenharia Civil

Exercícios Resolvidos

Bancos de Dados

Questões de Concurso

Frameworks

Projetos e Códigos Fonte

Especializações

Calculadoras

Ferramentas

Todas as Linguagens, Frameworks, Biliotecas e Bancos de Dados

Compre pelo WhatsApp: +55 (062) 98553-6711

E-Book 350 Exercícios Resolvidos de Java - Com comentários em Português

PDF COM 500 PÁGINAS

Apenas R$ 19,90