Lista de Exercícios Resolvidos: Java | Python | VisuAlg | Portugol | C | C# | VB.NET | C++
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) recursivo

Quantidade de visualizações: 465 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 recursiva. Em outra dica desta seção que mostrei como fazer a mesma travessia de forma iterativa e usando uma pilha para backtracking (retrocesso).

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 da Coleção 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.

Apenas R$ 32.90 (1 Ano de Acesso)

Quero Ser Apoiador(a)


Veja agora o código completo para o exemplo. Note que estamos usando recursividade nesta dica. Observe também o uso de uma ArrayList para guardar os valores da árvore binária na ordem depth-first.

Eis o código:

Este trecho de código ou resolução de exercício faz parte da Coleção 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.

Apenas R$ 32.90 (1 Ano de Acesso)

Quero Ser Apoiador(a)


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

Veja mais Dicas e truques de Java

Dicas e truques de outras linguagens

Quem Somos

Osmar J. Silva
Programador Freelancer
WhatsApp +55 (062) 98553-6711

Goiânia-GO
Programador Freelancer - Full Stack Developer, Professional Java Developer, PHP, C/C++, Python Programmer, wxWidgets Professional C++ Programmer, Freelance Programmer. Formado em Ciência da Computação pela UNIP (Universidade Paulista Campus Goiânia) e cursando Engenharia Civil pela PUC-Goiás. Possuo conhecimentos avançados de Java, Python, JavaScript, C, C++, PHP, C#, VB.NET, Delphi, Android, Perl, e várias tecnologias que envolvem o desenvolvimento web, desktop, front-end e back-end. Atuo há mais de 20 anos como programador freelancer, atendendo clientes no Brasil, Portugal, Argentina e vários outros paises.
Entre em contato comigo para, juntos, vermos em que posso contribuir para resolver ou agilizar o desenvolvimento de seus códigos.
José de Angelis
Programador Freelancer
WhatsApp +55 (062) 98243-1195

Goiânia-GO
Programador Freelancer - Formado em Sistemas de Informação pela Faculdade Delta, Pós graduado em Engenharia de Software (PUC MINAS), Pós graduado Marketing Digital (IGTI) com ênfase em Growth Hacking. Mais de 15 anos de experiência em programação Web. Marketing Digital focado em desempenho, desenvolvimento de estratégia competitiva, analise de concorrência, SEO, webvitals, e Adwords, Métricas de retorno. Especialista Google Certificado desde 2011 Possui domínio nas linguagens PHP, C#, JavaScript, MySQL e frameworks Laravel, jQuery, flutter. Atualmente aluno de mestrado em Ciência da Computação (UFG)
Não basta ter um site. É necessário ter um site que é localizado e converte usuários em clientes. Se sua página não faz isso, Fale comigo e vamos fazer uma analise e conseguir resultados mais satisfatórios..

Linguagens Mais Populares

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



© 2024 Arquivo de Códigos - Todos os direitos reservados
Neste momento há 17 usuários muito felizes estudando em nosso site.