 |
|
Você está aqui: Python ::: Estruturas de Dados ::: Árvore Binária e Árvore Binária de Busca |
Como percorrer uma árvore binária em Python usando o algorítmo depth-first search (DFS) de forma iterativaQuantidade de visualizações: 85 vezes |
|
Nesta dica mostrarei como podemos implementar o algorítmo da Busca em Profundidade (DFS, do inglês depth-first search) em Python de forma iterativa, ou seja, sem usar recursividade. 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:
# construtor da classe
def __init__(self, valor):
# o valor do nó
self.valor = valor
# o filho da esquerda
self.esquerdo = None
# o filho da direita
self.direito = None
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 List do Python, juntamente com seus métodos append() e pop() para simular a pilha. Usei também uma List 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)
----------------------------------------------------------------------
# implementação da classe No
class No:
# construtor da classe
def __init__(self, valor):
# o valor do nó
self.valor = valor
# o filho da esquerda
self.esquerdo = None
# o filho da direita
self.direito = None
# função principal do programa Python
def main():
# vamos criar os nós da árvore
cinco = No(5) # será a raiz da árvore
quatro = No(4)
nove = No(9)
dois = No(2)
tres = No(3)
doze = 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
valores = percurso_depth_first(cinco)
print("Os valores na ordem Depth-First são: {0}".format(valores))
# função que permite realizar a pesquisa depth-first search (DFS)
def percurso_depth_first(no):
# vamos usar uma List para retornar os elementos
# na ordem Depth-First
valores = list()
# vamos criar uma nova instância de uma list para representar uma pilha
pilha = list()
# já vamos adicionar o primeiro nó recebido, que é a raiz
pilha.append(no)
# enquanto a pilha não estiver vazia
while len(pilha) > 0:
# vamos obter o elemento no topo da pilha
atual = pilha.pop()
# adicionamos este valor na List
valores.append(atual.valor)
# vamos colocar o filho direito na pilha
if atual.direito != None:
pilha.append(atual.direito)
# vamos colocar o filho esquerdo na pilha
if atual.esquerdo != None:
pilha.append(atual.esquerdo)
return valores # retorna os valores da árvore
if __name__== "__main__":
main()
Ao executarmos este código Python 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 ::: Dicas & Truques ::: Trigonometria - Funções Trigonométricas |
Como calcular o arco cosseno de um número em Python usando o método acos() do módulo mathQuantidade de visualizações: 3324 vezes |
|
O arco cosseno, (também chamado de cosseno inverso) pode ser representado por cos-1 x, arccos x ou acos x. Esta função é a inversa do cosseno, ou seja, se o cosseno é a relação entre o cateto adjacente ao ângulo e a hipotenusa, o arco cosseno parte desta relação para encontrar o valor do ângulo. Em Python, o arco cosseno de um número pode ser obtido por meio do método acos() da classe Math. Este método recebe um valor double e retorna também um double, na faixa 0 <= x <= PI, onde PI vale 3.1416. Veja um código Python completo no qual informamos um número e em seguida calculamos o seu arco-cosseno: ----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------
# vamos importar o módulo Math
import math as math
def main():
numero = 0.5
print("O arco cosseno de %f é %f" % (numero, math.acos(numero)))
if __name__== "__main__":
main()
Ao executar este código nós teremos o seguinte resultado: O arco cosseno de 0.500000 é 1.047198 Não se esqueça de que as funções trigonométricas são usadas para modelar o movimento das ondas e fenômenos periódicos, como padrões sazonais. Elas formam a base para análises avançadas em engenharia elétrica, processamento digital de imagem, radiografia, termodinâmica, telecomunicações e muitos outros campos da ciência e da tecnologia. |
Python ::: Pandas Python Library (Biblioteca Python Pandas) ::: DataFrame |
Como acessar uma linha específica em um DataFrame do Pandas da linguagem Python usando o método iloc()Quantidade de visualizações: 10947 vezes |
|
Em várias situações nós precisamos investigar o conteúdo de uma determinada linha, ou seja, um registro específico contido em um DataFrame do Pandas. Para isso podemos usar o método iloc() do objeto DataFrame. Este método recebe um valor inteiro representando o índice da linha a ser retornada. É possível também fornecer uma list contendo vários índices, e até mesmo intervalos, mas isso é assunto para outras dicas. O retorno do método é uma Series ou um DataFrame, dependendo dos parâmetros usados. Vamos ver um exemplo? Analise o código a seguir: ----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------
# importamos a biblioteca Pandas
import pandas as pd
def main():
# vamos carregar os dados do arquivo .csv
dados = pd.read_csv("emprestimos.csv",
delimiter=";")
# vamos mostrar o DataFrame resultante
print(dados)
# agora vamos mostrar o conteúdo da terceira linha
linha = dados.iloc[2]
# mostramos o conteúdo da terceira linha
print("\nConteúdo da terceira linha:\n")
print(linha)
if __name__== "__main__":
main()
Ao executarmos este código nós teremos o seguinte resultado:
id nome idade sexo renda valor parc pont ap
0 1 HELENA508 39 F 6500 8000 6 87 S
1 2 JESSICA631 65 F 3000 500 48 2 N
2 3 FELIPE768 39 M 10200 20000 24 40 S
3 4 AMANDA515 90 F 800 1500 30 87 N
4 5 LAURA312 61 F 1800 15000 50 8 N
5 6 CARLOS291 84 M 970 11000 6 59 N
6 7 CARLOS859 64 F 970 500 12 1 N
Conteúdo da terceira linha:
id 3
nome FELIPE768
idade 39
sexo M
renda 10200
valor 20000
parc 24
pont 40
ap S
Name: 2, dtype: object
Veja que o conteúdo da linha é exibido na vertical. Se quisermos exibí-lo na horizontal, basta passarmos o índice da linha como uma list. Veja: ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- # agora vamos mostrar o conteúdo da terceira linha linha = dados.iloc[[2]] Agora o resultado será: Conteúdo da terceira linha: id nome idade sexo renda valor parc pont ap 2 3 FELIPE768 39 M 10200 20000 24 40 S Para testarmos se o retorno do método iloc() foi mesmo uma Series, basta usarmos a função type() do Python: ----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------
# vamos checar o retorno do método iloc()
linha = dados.iloc[[2]]
print("Tipo do retorno:", type(linha))
Este código exibirá um resultado parecido com: Tipo do retorno: <class 'pandas.core.frame.DataFrame'> |
Python ::: Dicas & Truques ::: Data e Hora |
Como adicionar dias à uma data em Python usando a função timedelta() da classe datetimeQuantidade de visualizações: 8922 vezes |
|
Nesta dica mostrarei como é possível usar o método timedelta() da classe datetime do Python para adicionar um determinado número de dias a uma data. O truque aqui é fornecer apenas o dia para o método timedelta(), obter o resultado e somá-lo com a data que já temos. Veja o código completo para o exemplo: ----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------
import datetime
# função principal do programa
def main():
# dias a serem adicionados
quant_dias = 2
# Obtém a data de hoje
hoje = datetime.date.today()
print("Hoje é:", hoje)
# Adiciona dias à data
dias = datetime.timedelta(days=quant_dias)
hoje = hoje + dias
# Exibe o resultado
print("Daqui à", quant_dias, "dias será", hoje)
if __name__== "__main__":
main()
Ao executarmos este código Python nós teremos o seguinte resultado: Hoje é: 2021-03-11 Daqui à 2 dias será 2021-03-13 |
Desafios, Exercícios e Algoritmos Resolvidos de Python |
Veja mais Dicas e truques de Python |
Dicas e truques de outras linguagens |
|
AutoLISP - Como retornar o nome da layer atual do AutoCAD usando AutoLISP e a variável de sistema CLAYER Delphi - Como calcular MDC em Delphi |
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 atendimentoDiga 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 funcionalidadesTenha 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 |
