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) de forma iterativa

Quantidade de visualizações: 714 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 iterativa, ou seja, sem usar recursão. Não farei a busca, mas sim o percurso, para que você entenda como a lógica dessa busca funciona.

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 usei uma implementação não-recursiva, na qual todos os nós expandidos recentemente são adicionados a uma pilha, para realizar a exploração. O uso da pilha permite o retrocesso (backtracking) de forma a reiniciarmos o percurso ou busca no próximo nó.

Para manter o código o mais simples possível, eu usei a classe Stack do Java, juntamente com seus métodos push() e pop() para simular a pilha. Usei também 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;
import java.util.Stack;

// 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 = percursoDepthFirst(cinco);
    System.out.println("Os valores na ordem Depth-First são: " + valores);
  }
  
  public static ArrayList<Integer> percursoDepthFirst(No no){
    // vamos usar uma ArrayList para retornar os elementos
    // na ordem Depth-First
    ArrayList<Integer> valores = new ArrayList<>();
    
    // vamos criar uma nova instância de uma pilha
    Stack<No> pilha = new Stack<>();
    // já vamos adicionar o primeiro nó recebido, que é a raiz
    pilha.push(no);
    
    // enquanto a pilha não estiver vazia
    while(pilha.size() > 0){
      // vamos obter o elemento no topo da pilha
      No atual = pilha.pop();
      // adicionamos este valor no ArrayList
      valores.add(atual.valor);
	  
      // vamos colocar o filho direito na pilha
      if(atual.direito != null){
        pilha.push(atual.direito);
      }
      
      // vamos colocar o filho esquerdo na pilha
      if(atual.esquerdo != null){
        pilha.push(atual.esquerdo);
      }
    }
    
    return valores; // retorna os valores da árvore
  }
}

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:

Python ::: Tkinter GUI Toolkit ::: Círculos, Ovais e Elípses

Como desenhar círculos no Tkinter usando a função create_oval() do componente Canvas

Quantidade de visualizações: 829 vezes
Em várias situações nós precisamos desenhar círculos não preenchidos e preenchidos em Tkinter. Para isso nós podemos usar a função create_oval() do componente Canvas.

Em sua forma mais simples, a função create_oval() requer as coordenadas x e y a partir das quais o círculo ou elípse será desenhada e a largura e a altura do retângulo dentro do qual o círculo estará contido. Para desenhar uma oval ou elípse, basta manipular a largura ou altura desse retângulo.

Veja um trecho de código no qual usamos a função create_oval() para desenhar um círculo com 5 pixels de largura da linha de desenho:

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

# vamos importar o módulo Tkinter
from tkinter import *
from tkinter.ttk import *
 
# método principal
def main():
  # cria a janela principal da aplicação
  janela_principal = Tk() 
  
  # define as dimensões da janela
  janela_principal.geometry("400x350")
  
  # define o título da janela
  janela_principal.title("Uso do controle Canvas")
 
  # vamos criar o objeto Canvas
  canvas = Canvas(janela_principal, bg="white", width=400, height=350)
 
  # colocamos o Canvas na janela principal
  canvas.grid(row=0, column=0)
 
  # agora vamos desenhar um círculo no Canvas começando nas
  # coordenadas x=20 e y=30 centro de um retângulo de largura
  # 150 pixels por uma altura de 150 pixels e largura da linha
  # de 5 pixels
  canvas.create_oval(20, 30, 150, 150, width="5")
 
  # entramos no loop de eventos 
  janela_principal.mainloop()
 
if __name__== "__main__":
  main()

Note que a largura da linha de desenho foi informada por meio do parâmetro width. Se quisermos definir também a cor da linha do desenho, basta usarmos o parâmetro outline e fornecer a cor desejada.


Python ::: Dicas & Truques ::: Matemática e Estatística

Como testar se um número é primo em Python

Quantidade de visualizações: 3356 vezes
O Número Primo é o número maior que 1 e que só pode ser dividido por 1 e por ele mesmo, ou seja, números primos não podem ser divididos por outros números, a não ser por ele mesmo e pelo número 1. Dessa forma, 2, 3, 5, 7, 11, 13, 17, etc, são todos números primos.

É importante observar que 0 e 1 não são números primos, e que o número 2 é o único número primo par.

Veja agora um código Python completo que pede para o usuário informar um número inteiro positivo e mostra uma mensagem indicando se o número informado é primo ou não:

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

def main():
  primo = True # vamos assumir que o número é primo

  # vamos solicitar um número inteiro positivo
  numero = int(input("Informe um número inteiro positivo: "))

  # o número é negativo?
  if numero < 0:
    print("Número inválido.")
  # é 0 ou 1?
  elif (numero == 0) or (numero == 1):
    print("Número válido, mas não é primo.")
  # passou até aqui. Vamos testar se o número é primo
  else:
    for i in range(2, int((numero / 2))):
      # se passar no teste, não é primo
      if numero % i == 0:
        primo = False # recebe false
        break

    if primo:
      print("O número informado é primo")
    else:
      print("O número informado não é primo")
    
if __name__== "__main__":
  main()

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

Informe um número inteiro positivo: 9
O número informado não é primo


Python ::: Desafios e Lista de Exercícios Resolvidos ::: Ordenação e Pesquisa (Busca)

Exercícios Resolvidos de Python - Como usar a Ordenação da Bolha em Python para ordenar os valores de um vetor em ordem crescente ou decrescente

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

A Ordenação da Bolha, ou ordenação por flutuação (literalmente "por bolha"), também chamada de Bubble Sort, é um algoritmo de ordenação dos mais simples. A ideia é percorrer o array diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento da sequência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.

No melhor caso, o algoritmo executa n operações relevantes, onde n representa o número de elementos do vetor. No pior caso, são feitas n2 operações. A complexidade desse algoritmo é de ordem quadrática. Por isso, ele não é recomendado para programas que precisem de velocidade e operem com quantidade elevada de dados.

Escreva um programa Python que declara, constrói um vetor de 10 inteiros e peça para o usuário informar os valores de seus elementos. Em seguida use a ordenação da bolha para ordenar os elementos em ordem crescente.

Sua saída deverá ser parecida com:

Informe o valor para o índice 0: 84
Informe o valor para o índice 1: 23
Informe o valor para o índice 2: 9
Informe o valor para o índice 3: 5
Informe o valor para o índice 4: 11
Informe o valor para o índice 5: 3
Informe o valor para o índice 6: 50
Informe o valor para o índice 7: 7
Informe o valor para o índice 8: 2
Informe o valor para o índice 9: 73

O array informado foi:

84   23   9   5   11   3   50   7   2   73   

O array ordenado é:

2   3   5   7   9   11   23   50   73   84
Resposta/Solução:

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

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

# função principal do programa
def main():
  # vamos declarar e construir um vetor de 10 elementos
  valores = [0 for x in range(10)]
  	  
  # vamos pedir que o usuário informe os valores
  for i in range(0, len(valores)):
    valores[i] = int(input("Informe o valor para o índice {0}: ".format(i)))
    
  # vamos mostrar o vetor informado
  print("\nO array informado foi:\n\n")
  for i in range(0, len(valores)):
    print(valores[i], end="   ")
    
  # vamos ordenar os elementos do vetor usando a ordenação da bolha
  # laço externo de trás para frente
  for i in range(len(valores) - 1, 0, -1):
    for j in range(0, i): # laço interno vai no fluxo normal
      if valores[j] > valores[j + 1]: # temos que trocá-los de lugar 
        temp = valores[j]
        valores[j] = valores[j + 1]
        valores[j + 1] = temp
    
  # vamos exibir o vetor já ordenado
  print("\n\nO array ordenado é:\n\n")
  for i in range(0, len(valores)):
    print(valores[i], end="   ")
  
  print("\n")

if __name__== "__main__":
  main()



C++ ::: Dicas & Truques ::: Recursão (Recursividade)

Como calcular fatorial em C++ usando recursividade

Quantidade de visualizações: 9330 vezes
O fatorial de um determinado número, representado por n! equivale a multiplicar este número por seus antecessores. Assim, o fatorial de 4 (4!) pode ser calculado da seguinte forma:

4 x 3 x 2 x 1 = 24

Sempre que falamos de recursão, o cálculo de fatorial nos auxilia na exemplicação por ser relativamente fácil de se entender todas as etapas do processo. O código abaixo mostra uma função recursiva em C++ que calcula o fatorial de qualquer número. Tenha cuidado. Calcular o fatorial de um número maior que 10 pode tornar sua máquina extremamente lenta, além de, muitas vezes, não retornar os resultados esperados.

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

#include <iostream>

using namespace std;

// função recursiva para calcular o fatorial
// de um determinado número
int fatorial(int n){
  if(n == 0)
    return 1;
  else
    return n * fatorial(n - 1);
}

int main(int argc, char *argv[]){
  // vamos calcular o fatorial de 5
  int res = fatorial(5);

  // exibe o resultado
  cout << "O fatorial de 5 é: " << res << endl;

  system("PAUSE"); // pausa o programa
  return EXIT_SUCCESS;
}



Elixir ::: Dicas de Estudo e Anotações ::: Passos Iniciais

Como instalar a linguagem de programação Elixir no Windows

Quantidade de visualizações: 354 vezes
Está curioso(a) para aprender um pouco mais sobre a linguagem de programação Elixir? Nesta dica mostrarei como instalar, configurar e testar o ambiente de programação desta linguagem.

O primeiro passo para instalar a Elixir no Windows é verificar se você já tem uma instalação do ambiente de programação Erlang. Se ainda não tiver, veja a nossa dica correspondente.

Como baixar e instalar a Elixir

Para baixar a Elixir e as ferramentas necessárias, acesse a URL https://elixir-lang.org/install.html#windows e baixe o instalador elixir-websetup.exe. Em seguida dê duplo-clique neste instalador e siga as instruções apresentadas. Não se preocupe. Basta aceitar as opções padrões que o instalador fará a instalação completa, inclusive incluindo o diretório bin na variável de ambiente PATH.

Como testar a instalação da Elixir

Para testar se sua instalação da linguagem de programação Elixir ocorreu sem problemas, abra uma nova janela de terminal e dispare o seguinte comando:

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

C:\Users\Osmar>elixirc --version

Se tudo correu bem você verá o seguinte resultado:

Erlang/OTP 25 [erts-13.2] [source] [64-bit] [smp:4:4] [ds:4:4:10] [async-threads:1] [jit:ns]

Elixir 1.14.3 (compiled with Erlang/OTP 25)

Pronto! Agora é só seguir as nossas dicas e truques de Elixir e ficar fluente em mais essa linguagem de programação. Bons estudos!


Veja mais Dicas e truques de Elixir

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