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: 126 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. |
![]() |
Python ::: Dicas & Truques ::: Formatação de datas, strings e números |
Python para iniciantes - Como inserir uma determinada quantidade de espaços à direita de uma stringQuantidade de visualizações: 8446 vezes |
Este trecho de código mostra como inserir uma determinada quantidade de espaços à direita de uma string. Esta técnica é muito útil para formatar a saída em tela ou em arquivos. Veja o código completo para a dica: ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- def main(): palavra1 = "Estudando" palavra2 = "Python" palavra3 = "C++" palavra4 = "Delphi" print("%-12s %s" % (palavra1, palavra2)) print("%-12s %s" % (palavra3, palavra4)) if __name__== "__main__": main() Ao executarmos este código Python nós teremos o seguinte resultado: Estudando Python C++ Delphi |
Python ::: PyQt GUI Toolkit ::: QMainWindow |
Como criar a janela principal de uma aplicação Python PyQt usando a classe QMainWindowQuantidade de visualizações: 1362 vezes |
Em geral toda aplicação GUI, ou seja, uma aplicação de interface visual, rodando no Window, Linux, MAC, etc, possui uma janela principal. No PyQt tal janela é criada como uma instância da classe QMainWindow. Veja a posição desta classe na hierarquia de classes do PyQt: QObject, QPaintDevice QWidget QMainWindow Uma janela QMainWindow possui o seu próprio layout, no qual podemos adicionar uma barra de ferramentas QToolBar, um QDockWidget (que serve para controles que "grudam" em lados diferentes da tela), uma barra de menus QMenuBar e uma barra de status QStatusBar. O layout oferecido pela classe QMainWindow possui uma área central que pode ser ocupada por qualquer tipo de controle visual. É nessa área central que podemos colocar outros tipos de gerenciadores de layouts, que servirão como containers para os componentes visuais da aplicação. Veja uma aplicação PyQt completa na qual temos uma janela principal QMainWindow e um botão QPushButton. Observe como tiramos proveito da programação orientada em Python para criar uma classe JanelaPrincipal que herda de QMainWindow: ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- # vamos importar os módulos necessários import sys from PyQt6.QtCore import * from PyQt6.QtGui import * from PyQt6.QtWidgets import * # vamos criar uma classe que herda de QMainWindow class JanelaPrincipal(QMainWindow): # construtor da classe def __init__(self): super().__init__() # definimos o título da janela self.setWindowTitle("Cadastro de Produtos") # vamos criar um botão QPushButton botao = QPushButton("Novo Produto") # definimos este botão como o controle central # da janela principal self.setCentralWidget(botao) if __name__== "__main__": # cria a aplicação app = QApplication(sys.argv) # cria a janela principal e a coloca visível janela_principal = JanelaPrincipal() janela_principal.show() # executa a aplicação app.exec() |
Python ::: Dicas & Truques ::: Data e Hora |
Datas e horas em Python - Como obter o nome do dia da semana no formato longo (segunda-feira, terça-feira, etc) usando a função strftime() do PythonQuantidade de visualizações: 8794 vezes |
Nesta dica eu mostro como podemos usar a função strftime() da linguagem Python para obter e exibir o nome do dia da semana no formato longo e em português, ou seja, segunda-feira, terça-feira, quarta-feira, etc. 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) ---------------------------------------------------------------------- from datetime import datetime import locale # função principal do programa def main(): # Configurações do usuário locale.setlocale(locale.LC_ALL, '') # Obtém um datatime da data e hora atual hoje = datetime.today() # Exibe o nome do dia da semana no formato # longo print("O dia da semana é:", hoje.strftime("%A")) if __name__== "__main__": main() Ao executarmos este código nós teremos o seguinte resultado: O dia da semana é: quinta-feira |
Desafios, Exercícios e Algoritmos Resolvidos de Python |
Veja mais Dicas e truques de Python |
Dicas e truques de outras linguagens |
Códigos Fonte |
![]() 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 |
![]() 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 |