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: 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 Javadouble 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áriosQuantidade 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 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 JavaQuantidade 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 JavaQuantidade 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 |
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 |