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 iterativa

Quantidade 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.

Link para compartilhar na Internet ou com seus amigos:

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 string

Quantidade 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 QMainWindow

Quantidade 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 Python

Quantidade 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

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: C
6º lugar: Delphi
7º lugar: JavaScript
8º lugar: C++
9º lugar: VB.NET
10º lugar: Ruby



© 2025 Arquivo de Códigos - Todos os direitos reservados
Neste momento há 57 usuários muito felizes estudando em nosso site.