Estruturando dados: Inserindo elementos em uma árvore de busca binária em python
- #Estrutura de dados
Olá, seja muito bem vindo(a), no artigo anterior sobre estrutura de dados: https://programacao-descomplicada.blogspot.com/2022/11/estruturando-dados-arvores-em-python-na.html, desenvolvemos nossos primeiros códigos relacionados a estrutura de dados em python. Porém, nossas adições de nós na nossa árvore foram de forma manual, vamos desenvolver agora uma função para fazer essas adições.
Primeiro pegamos nossa classe árvore, que já construímos na aula passada no qual temos uma função no qual criamos os nós:
class Arvore:
def __init__(self, chave=None, esquerda=None, direita=None):
self.chave = chave
self.esquerda = esquerda
self.direita = direita
Abaixo dessa classe vamos construir uma nova função chamada insere no qual passamos como parâmetro, a raiz da nossa árvore e o nó que queremos adicionar. Se a raiz resultar em Nome é porque a árvore está vazia, daí o nó que passamos inicialmente seria a raiz, se não ainda temos outra condição. Se o valor da raiz for menor que o valor do nó, passamos o nó para a direita da raiz, se não passamos o valor para a esquerda.
def insere(raiz, nodo):
if raiz is None:
raiz = nodo
elif raiz.chave < nodo.chave:
if raiz.direita is None:
raiz.direita = nodo
else:
insere(raiz.direita, nodo)
else:
if raiz.esquerda is None:
raiz.esquerda = nodo
else:
insere(raiz.esquerda, nodo)
Podemos testar passando um laço for para adicionar números nessa árvore, porém nesse nosso caso todos os nós vão ir para a direita o que resulta em uma estrutura linear, estrutura de árvores não são usadas para isso, mas só a caráter de teste o código seria esse:
tree = Arvore(0)
for i in range(1, 10):
no = Arvore(i)
insere(tree, no)
Vou ficando por aqui, se você curte conteúdo digital sobre programação mais curtinhos para acompanhar durante uma horinha de folga, não deixa de me seguir no instagram: https://www.instagram.com/francileudo.frontend/, deixo um abraço para você e até a próxima.
Artigo Original: https://programacao-descomplicada.blogspot.com/2022/11/estruturando-dados-inserindo-elementos.html