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: 734 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:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

// implementação da classe No
class No{
  public int valor; // o valor do nó
  public No esquerdo; // o filho da esquerda
  public No direito; // o filho da direita
  
  public No(int valor){
    this.valor = valor;
    this.esquerdo = null;
    this.direito = null;
  }
}

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:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

package estudos;

import java.util.ArrayList;

// implementação da classe No
class No{
  public int valor; // o valor do nó
  public No esquerdo; // o filho da esquerda
  public No direito; // o filho da direita
  
  public No(int valor){
    this.valor = valor;
    this.esquerdo = null;
    this.direito = null;
  }
}

public class Estudos{
  public static void main(String[] args){
    // vamos criar os nós da árvore
    No cinco = new No(5); // será a raiz da árvore
    No quatro = new No(4);
    No nove = new No(9);
    No dois = new No(2);
    No tres = new No(3);
    No doze = new No(12);
    
    // vamos fazer a ligação entre os nós
    cinco.esquerdo = quatro;
    cinco.direito = nove;
    quatro.esquerdo = dois;
    nove.esquerdo = tres;
    nove.direito = doze;
    
    // agora já podemos efetuar o percurso depth-first
    ArrayList<Integer> valores = new ArrayList<>();
    percursoDepthFirst(valores, cinco);
    System.out.println("Os valores na ordem Depth-First são: " + valores);
  }
  
  public static void percursoDepthFirst(ArrayList<Integer> valores, No no){
    if(no != null){
      // vamos adicionar o valor deste nó no ArrayList
      valores.add(no.valor);
   
      // passamos para o filho esquerdo
      percursoDepthFirst(valores, no.esquerdo);
      // passamos para o filho direito
      percursoDepthFirst(valores, no.direito);
    }
  }
}

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:

Java ::: Pacote java.lang ::: Integer

Java para iniciantes - Como usar o método parseInt() da classe Integer para converter uma String em um valor do tipo int

Quantidade de visualizações: 95440 vezes
Em algumas situações, principalmente quando estamos lidando com valores informados pelo usuário, nós precisamos converter uma String em um valor inteiro. Para isso podemos usar o método parseInt() da classe Integer. Veja sua assinatura:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

public static int parseInt(String s)
  throws NumberFormatException

A String fornecida como argumento deve conter apenas digitos decimais, exceto que o primeiro caractere pode ser o caractere ASCII sinal de menos "-" ('\u002D') para indicar um valor negativo ou o caractere ASCII sinal de mais "+" ('\u002B') para indicar um valor positivo.

Veja um exemplo no qual usamos o método parseInt() para converter uma String informada pelo usuário em um valor do tipo int:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

import java.util.Scanner;

public class Estudos {
  public static void main(String[] args) {
    // vamos usar um objeto da classe Scanner para ler a idade do usuário
    Scanner entrada = new Scanner(System.in);
    
    // solicita a idade
    System.out.print("Informe sua idade: ");
    int idade = Integer.parseInt(entrada.nextLine());
    
    // mostra o valor lido
    System.out.println("A idade informada foi: " + idade);    
  }
}

Ao executarmos este código teremos o seguinte resultado:

Informe sua idade: 28
A idade informada foi: 28

Há, porém, situações nas quais o usuário pode não seguir as recomendações de não inserir caracteres inválidos, o que inviabiliza a conversão para inteiro. Veja:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

Informe sua idade: osmar
Exception in thread "main" java.lang.NumberFormatException: 
For input string: "osmar"
  at java.lang.NumberFormatException.forInputString(NumberFormatException.
java:48)
  at java.lang.Integer.parseInt(Integer.java:447)
  at java.lang.Integer.parseInt(Integer.java:497)
  at Estudos.main(Estudos.java:10)

Para contornar esta situação nós precisamos fornecer um bloco try...catch para tratar a exceção NumberFormatException. Veja:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

import java.util.Scanner;

public class Estudos {
  public static void main(String[] args) {
    // vamos usar um objeto da classe Scanner para ler a idade do usuário
    Scanner entrada = new Scanner(System.in);
    
    // solicita a idade
    System.out.print("Informe sua idade: ");
    
    try{
      int idade = Integer.parseInt(entrada.nextLine());
    
      // mostra o valor lido
      System.out.println("A idade informada foi: " + idade);
    }
    catch(NumberFormatException nfe){
      System.out.println("Valor inválido: " + nfe.getMessage());	
    }    
  }
}

Agora o programa exibirá uma mensagem de erro caso o usuário forneça uma String que não pode ser convertida para inteiro.


Java ::: Dicas & Truques ::: Strings e Caracteres

Como inserir uma substring em uma string em Java usando o método insert() da classe StringBuffer

Quantidade de visualizações: 23 vezes
Nesta dica mostrarei como podemos usar o método insert() da classe StringBuffer da linguagem Java para inserir uma substring no início, meio ou final de uma string.

Este método recebe o índice no qual queremos inserir a substring e a substring a ser inserida.

Veja o código Java completo para o exemplo:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

package estudos;
 
public class Estudos {
  public static void main(String args[]) {
    // vamos declarar um objeto da classe StringBuffer
    StringBuffer frase = new StringBuffer("Programar em é bom demais");
    System.out.println("A frase original é: " + frase);
    
    // agora vamos inserir a palavra "Java" no índice 13
    frase.insert(13, "Java ");
    
    // e agora mostramos o resultado
    System.out.println("O resultado é: " + frase);
  }
}

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

A frase original é: Programar em é bom demais
O resultado é: Programar em Java é bom demais


Java ::: Desafios e Lista de Exercícios Resolvidos ::: Estruturas de Dados - Listas Ligadas

Exercícios Resolvidos de Java - Como inserir no início de uma lista ligada em Java - Escreva um programa Java que pede para o usuário informar vários

Quantidade de visualizações: 567 vezes
Pergunta/Tarefa:

Este exercício Java demonstra como inserir um nó no início de uma lista ligada. Escreva um programa Java que cria uma lista ligada, ou seja, uma lista dinamicamente encadeada, e pede para o usuário informar vários valores inteiros, colocando os valores sempre no início da lista.

Seu código deverá interromper a leitura dos valores quando o usuário informar o valor -1. Quando isso acontecer, mostre todos os valores contidos na lista ligada, na mesma ordem que foram inseridos (o último valor lido será o primeiro da lista).

Sua saída deve ser parecida com:

Inserindo valores no início da lista

Informe o valor (-1 para sair): 8
Informe o valor (-1 para sair): 2
Informe o valor (-1 para sair): 5
Informe o valor (-1 para sair): 7
Informe o valor (-1 para sair): -1

Valores na lista: 7 -> 5 -> 2 -> 8 -> null
Resposta/Solução:

Veja a resolução comentada deste exercício usando Java:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

package estudos;
  
import java.util.Scanner;

// classe interna usada para representar um
// nó na lista ligada
class No {
  int valor; // valor do nó
  No proximo; // aponta para o novo nó
 
  // construtor da classe No
  No(int valor, No proximo) {
    this.valor = valor;
    this.proximo = proximo;
  }
}

public class Estudos { 
  public static void main(String args[]){
    // para ler a entrada do usuário
    Scanner entrada = new Scanner(System.in);
    
    // vamos criar uma referência para o início da lista
    No inicio = null;
    
    // agora vamos pedir para o usuário informar
    // valores inteiros. O valor -1 sai do laço
    int valor;
    System.out.println("Inserindo valores no início da lista\n");
    do {
      System.out.print("Informe o valor (-1 para sair): ");
      valor = Integer.parseInt(entrada.nextLine());
      if (valor != -1) {
        inicio = inserirInicio(inicio, valor);
      }
    } while(valor != -1);
    
    // vamos exibir os valores na lista ligada
    System.out.print("\nValores na lista: ");
    exibirLista(inicio);
  }
  
  // função que permite adicionar um nó no início da
  // lista ligada
  public static No inserirInicio(No inicio, int valor) {
    // vamos apontar para o nó inicial
    No atual = inicio;
    // criamos um novo nó
    No novo = criarNo(valor);
 
    // a lista ligada ainda está vazia?
    if (atual == null){
      // inicio recebe o novo nó
      inicio = novo;
    }    
    else { // temos um ou mais nós na lista ligada
      // vamos inserir este nó antes do nó que
      // representa o início da lista
      novo.proximo = inicio;
      inicio = novo;
    }
    
    // e retornamos o início da lista
    return inicio;
  }
  
  // função usada para construir e retornar um novo nó
  public static No criarNo(int valor) {
    // cria o novo nó
    No no = new No(valor, null);
    // retorna o nó criado
    return no;
  }
  
  // função usada para percorrer a lista ligada e
  // exibir os valores contidos em seus nós
  public static void exibirLista(No inicio) {
    // vamos apontar para o início da lista
    No temp = inicio;
    
    // a lista está vazia?
    if (temp == null) {
      System.out.println("A lista está vazia.");
    }
    else {
      // esse laço se repete enquanto tempo for
      // diferente de null
      while (temp != null) {
        // vamos mostrar o valor desse nó
        System.out.print(temp.valor + " -> ");
        // avança para o próximo nó
        temp = temp.proximo;
      }
    
      // mostra o final da lista
      System.out.println("null");
    }
  }
}



Vamos testar seus conhecimentos em Python

Qual função é usada para retornar o tamanho de uma string em Python?

A) count_chars()

B) str_len()

C) size()

D) length()

E) len()
Verificar Resposta Estudar Cards Todas as Questões

Vamos testar seus conhecimentos em Python

Qual o resultado da execução do seguinte código Python?

valores = [5, 2, 7, 1, 4, 9, 6]
contador = len(valores)
while contador >= 0:
  print(valores[contador], end="  ")
  contador = contador - 2

A) Erro IndexError: list index out of range na linha 4

B) 6 4 7 5

C) Erro SyntaxError: invalid syntax na linha 5

D) 2 1 9

E) 1 4 9 6
Verificar Resposta Estudar Cards Todas as Questões

Vamos testar seus conhecimentos em Ética e Legislação Profissional

Ética profissional, social, política

Se a maior preocupação de Maquiavel é o Estado, poderíamos dizer que isso o situa no presente temporal.

A respeito disto, afirma Sadek (1995, p. 17): "De fato, sua preocupação em todas as suas obras é o Estado. Não o melhor Estado, aquele tantas vezes imaginado, mas que nunca existiu. Mas o Estado real, capaz de impor a ordem".

A partir do trecho citado, assinale a alternativa correta:

A) Para Maquiavel, o tempo presente do Estado deve ser considerado pela ética.

B) Para Maquiavel, a ética está associada ao exercício da ordem.

C) Para Maquiavel, a ética está atrelada a uma idealização da ação na política.

D) Para Maquiavel, a ordem é fruto de um Estado ético.

E) Para Maquiavel, o Estado existe enquanto mantenedor da ética.
Verificar Resposta Estudar Cards Todas as Questões

Vamos testar seus conhecimentos em

Dimensionamento de pilares de canto

O cobrimento mínimo de um pilar de canto é de grande importância para sua durabilidade, pois tem a função de proteger a armadura do ambiente contra agentes externos que podem causar sua oxidação.

Para um pilar de canto de uma edificação construída em ambiente urbano, qual o valor do cobrimento nominal?

A) Cnom = 50mm.

B) Cnom = 40mm.

C) Cnom = 35mm.

D) Cnom = 30mm.

E) Cnom = 25mm.
Verificar Resposta Estudar Cards Todas as Questões

Vamos testar seus conhecimentos em Hidrologia

O Brasil apresenta um grande volume de usinas hidrelétricas instaladas na sua rede hidrográfica. Marque a alternativa que faça uma associação correta entre o nome da usina hidrelétrica e a sua localização.

A) Usina de Furnas -> Bacia Platina.

B) Usina de Belo Monte -> Bacia Amazônica.

C) Usina de Três Marias -> Bacia do Uruguai.

D) Usina de Sobradinho -> Bacia do Tocantins.

E) Usina de Itaipu -> Bacia do São Francisco.
Verificar Resposta Estudar Cards Todas as Questões

Mais Desafios de Programação e Exercícios e Algoritmos Resolvidos de Java

Veja mais Dicas e truques de Java

Dicas e truques de outras linguagens

Códigos Fonte

Programa de Gestão Financeira Controle de Contas a Pagar e a Receber com Cadastro de Clientes e FornecedoresSoftware de Gestão Financeira com código fonte em PHP, MySQL, Bootstrap, jQuery - Inclui cadastro de clientes, fornecedores e ticket de atendimento
Diga adeus às planilhas do Excel e tenha 100% de controle sobre suas contas a pagar e a receber, gestão de receitas e despesas, cadastro de clientes e fornecedores com fotos e histórico de atendimentos. Código fonte completo e funcional, com instruções para instalação e configuração do banco de dados MySQL. Fácil de modificar e adicionar novas funcionalidades. Clique aqui e saiba mais
Controle de Estoque completo com código fonte em PHP, MySQL, Bootstrap, jQuery - 100% funcional e fácil de modificar e implementar novas funcionalidadesControle de Estoque completo com código fonte em PHP, MySQL, Bootstrap, jQuery - 100% funcional e fácil de modificar e implementar novas funcionalidades
Tenha o seu próprio sistema de controle de estoque web. com cadastro de produtos, categorias, fornecedores, entradas e saídas de produtos, com relatórios por data, margem de lucro e muito mais. Código simples e fácil de modificar. Acompanha instruções para instalação e criação do banco de dados MySQL. Clique aqui e saiba mais

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á 26 usuários muito felizes estudando em nosso site.