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

Vamos testar seus conhecimentos em Python

Qual a saída do seguinte programa Python?

valor = 0.0043563
print("Valor: %e" % valor)

A) Erro de execução na linha 2

B) Valor: 0.004356

C) Valor: 4.356300e-03

D) Valor: 0

E) Valor: 0.0044
Verificar Resposta Estudar Cards Todas as Questões

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

Noções de licitação pública

Licitação pública é o procedimento por meio do qual a administração pública adquire ou vende bens e contrata serviços. Sobre a licitação pública, assinale a alternativa correta.

A) É dever do órgão licitante garantir a igualdade entre os competidores durante todo o certame a fim de assegurar a isonomia, que é um princípio fundamental do processo licitatório.

B) Na legislação que regulamenta as licitações, não há previsão para o estabelecimento, nos processos licitatórios, de margem de preferência para bens e serviços com tecnologia desenvolvida no Brasil.

C) É prevista em lei a permissão para a realização de licitação cujo objeto inclua bens sem similaridade ou de marcas, de características e de especificações exclusivas, salvo em casos específicos previstos em legislação.

D) Na aquisição pública de materiais mediante processo licitatório, a administração pública pode descumprir as normas e as condições do edital, visando à celeridade no recebimento dos materiais.

E) A licitação é um procedimento utilizado para dar a oportunidade aos vários interessados em manifestar propostas à administração pública, que, ao final, vai selecionar a considerada mais barata.
Verificar Resposta Estudar Cards Todas as Questões

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

Ética profissional, social, política

A delimitação do que é ético e do que é moral é motivo de grande confusão. Ao longo da história do pensamento humano, podemos identificar que, por estarem em relação constituinte um do outro, ambos os domínios da vida humana são pensados como a mesma coisa. Contudo, ética e moral têm os seus sentidos e práticas distintas.

A respeito disso, assinale a alternativa correta:

A) A moral é ausente de normas de condutas sociais.

B) A ética é um exercício subjetivo sempre guiado pela moral.

C) A moral diz respeito a um conjunto de normas e tradições universais.

D) Ética se aplica à ação no âmbito profissional e público.

E) A ética tem um caráter universal e a moral, um caráter particular.
Verificar Resposta Estudar Cards Todas as Questões

Vamos testar seus conhecimentos em Python

Qual função é usada para converter uma string em letras maiúsculas em Python?

A) toUpper()

B) upper()

C) upper_case()

D) toUpperCase()

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

Vamos testar seus conhecimentos em Java

Analise o seguinte código Java

double a = 3.0 / 0;
System.out.println(a);

Qual é o resultado de sua execução?

A) Infinity

B) NaN

C) Uma exceção java.lang.ArithmeticException: / by zero

D) 0
Verificar Resposta Estudar Cards Todas as Questões

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: 525 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");
    }
  }
}



Java ::: Dicas & Truques ::: Programação Orientada a Objetos

Como usar encapsulamento em Java - Programação Orientada a Objetos em Java

Quantidade de visualizações: 37752 vezes
Encapsulamento é a técnica de transformar os objetos que compõem uma aplicação em verdadeiras caixas-pretas. De fato, se pensarmos em termos de informática, é possível para um usuário comum usar todas as funcionalidades de uma impressora sem nem mesmo entender seu funcionamento interno. Imagine o desastre que seria se todos os usuários resolvessem abrir suas impressoras para investigar o que há dentro delas.

Da mesma forma, ao construir uma classe, devemos fazê-lo de forma que o usuário desta classe tenha acesso apenas aos métodos que permitem ler informações da classe ou fornecer os dados necessários para sua correta operação. Dados relativos ao funcionamento interno da classe devem permanecer ocultos e acessíveis somente aos métodos da própria classe.

O encapsulamento deve ser aplicado de forma a permitir que alterações na estrutura interna de uma classe não prejudique o funcionamento do código externo que a usa. Veja um exemplo:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------
 
  class Pedido{
    public List obterProdutos(){
      // monta uma lista de produtos
      // pertecentes a este pedido
      return lista;
    }
  }

A classe Pedido contém um método chamado obterProdutos() que retorna uma lista de produtos pertencentes a um determinado pedido. É aqui que o encapsulamento se torna importante. O código que usa esta classe desconhece completamente como esta lista de produtos é montada. Tudo que nos interessa é a lista de produtos que o método retorna. O programador da classe pode decidir a qualquer momento, talvez para melhorar o desempenho da classe, alterar a forma de montagem da lista. Uma vez que o nome e retorno do método (incluindo a estrutura da lista retornada) continuem sendo os mesmos, o código que usa a classe continuará funcionando como anteriormente.


Java ::: Pacote java.lang ::: String

Curso de Java - Como usar a classe String da linguagem Java

Quantidade de visualizações: 7211 vezes
A classe String, presente no pacote java.lang, permite a representação de cadeias (strings) de caracteres. Todos os strings literais em Java, tais como "abc", são implementados como instâncias desta classe.

Por pertencer ao pacote java.lang, não precisamos importar nenhum pacote para poder usar esta classe em nossos programas Java. Veja um exemplo de como declarar e inicializar uma variável do tipo String:

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

public class Main {
  public static void main(String[] args) {
    String nome = "Osmar J. Silva";
    System.out.println(nome);
  }
}

Veja a posição desta classe na hierarquia de classes da plataforma Java:

java.lang.Object
java.lang.String

Esta classe implementa as interfaces Serializable, CharSequence e Comparable<String>.

Objetos do tipo String são constantes, ou seja, seus valores não podem ser alterados depois de criados. Assim, se você tiver um código parecido com:

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

public class Main {
  public static void main(String[] args) {
    // ambas as variáveis apontam para uma mesma string
    // há somente uma cópia de "Osmar J. Silva" na memória
    String nome = "Osmar J. Silva";
    String nome2 = "Osmar J. Silva";
	
    // agora uma nova string é criada e a anterior é preservada
    nome2 = "Marcos de Souza Gomes";
  }
}

Note que o compilador, com o propósito de poupar recursos do sistema, cria apenas uma string "Osmar J. Silva" e a coloca no pool de strings. No momento que alteramos o valor da variável nome2, uma nova string "Marcos de Souza Gomes" é criada e a anterior permanece intacta.

A classe String inclui métodos para examinar os caracteres individuais da sequencia, para a comparação de strings, pesquisar, extrair substrings e também criar uma cópia da string com todos os caracteres convertidos para letras maiúsculas ou minúsculas. O mapeamente das letras maiúsculas e minúsculas é feito com base na versão Unicode Standard especificada na classe Character.

A linguagem Java fornece suporte especial para a concatenação de strings, usando o operador (+) e para a conversão de outros objetos em strings. A concatenação é implementada por meio da classe StringBuilder (ou StringBuffer) e seu método append(). As conversões de strings são implementadas por meio do método toString(), definido na classe Object e herdado por todas as demais classes Java.

Quando não devidamente observado, passar um argumento null para o construtor ou método da classe String fará com que uma exceção do tipo NullPointerException seja atirado.

A classe String representa uma string no formato UTF-16, no qual caracteres suplementares são representados por pares prepostos. Valores de índice referem-se às unidades de código de caracteres. Assim, caracteres suplementares usam duas posições em uma String.


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