Estruturando dados: árvores em python na prática

Olá, seja muito bem vindo(a), nos artigos anteriores nós conhecemos na teoria um pouco sobre a estrutura chamada árvores: https://programacao-descomplicada.blogspot.com/2022/11/estruturando-dados-o-que-e-uma.html. Se revermos o artigo linkado anteriormente, podemos perceber que cada nó da árvore tem dois filhos, um da esquerda e o outro da direita, essas são as ligações da nossa árvore.

  Primeiro iremos criar nossa classe de árvore, tendo como primeira função a responsável por criar nossos nós. Abaixo podemos criar a raiz da nossa árvore e seus filhos, tendo um código final dessa forma:

class NoArvore:

def __init__(self, chave=None, esquerda=None, direita=None):

  self.chave = chave

  self.esquerda = esquerda

  self.direita = direita



raiz = NoArvore(3)

raiz.esquerda = NoArvore(5)

raiz.direita = NoArvore(1)

  No artigo anterior: https://programacao-descomplicada.blogspot.com/2022/11/estruturando-dados-arvore-binaria-de.html, eu mostrei uma imagem de uma árvore binária de busca, usando nossa classe de criar nós, vamos reproduzir ela em código:

raiz = NoArvore(40)

raiz.esquerda = NoArvore(20)

raiz.direita = NoArvore(60)



raiz.direita.esquerda = NoArvore(50)

raiz.direita.direita  = NoArvore(70)

raiz.esquerda.esquerda = NoArvore(10)

raiz.esquerda.direita = NoArvore(30)

  Agora, lembrando do que aprendemos no artigo sobre formas de percorrer nossa árvore: https://programacao-descomplicada.blogspot.com/2022/11/estrutrando-dados-formas-de-percorrer.html, no qual vamos ver agora a Em-ordem. Nele, começamos percorrendo a árvore na esquerda, depois visitamos a raiz e vamos para a direita.

def em_ordem(raiz):

if not raiz:

  return

em_ordem(raiz.esquerda)

print(raiz.chave)

em_ordem(raiz.direita)

  Colocamos essa função em_ordem fora da nossa classe, no qual passamos nossa raiz como parâmetro. A função irá descer a árvore até chegar no último nó esquerdo do lado esquerdo (10) e começar daí, obtendo o seguinte caminho: 10, 20, 30, 40, 50, 60, 70. 

  Com base no que vimos até aqui, será que você conseguiria desenvolver as funções pré-ordem e pós-ordem? Fica como exercício, vou ficando por aqui, um abraço e até a próxima.

Artigo Original: https://programacao-descomplicada.blogspot.com/2022/11/estruturando-dados-arvores-em-python-na.html