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) recursivoQuantidade 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 intQuantidade 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 StringBufferQuantidade 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áriosQuantidade 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 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 |
Software 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 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 |