Representação de árvores binárias
As árvores binárias são uma estrutura de dados fundamental, amplamente utilizadas em ciência da computação. São particularmente úteis para criar algoritmos eficientes em tarefas como pesquisa, ordenação e percorrer dados.
As árvores binárias são compostas por nós, onde cada nó tem no máximo dois filhos – um filho à esquerda e outro filho à direita. Cada um destes filhos pode também ter os seus próprios filhos esquerdo e direito, e essa estrutura prolonga-se até que não haja mais nós na árvore.
O nó que fica no topo de uma árvore binária chama-se raiz, enquanto os elementos ao fundo são chamados folhas.
Esta ideia simples permite representar, de forma surpreendentemente eficiente, muitos tipos diferentes de dados e é fácil de implementar em várias linguagens de programação:
class Node: # Objeto Node para armazenar os dados de cada nó
def __init__(self, value): # O valor que cada nó vai conter (pode ser qualquer coisa)
self.left = None # Inicialmente, left e right são None
self.right = None
self.value = value # Armazena o valor num objeto
# Criar manualmente todos os nós
root = Node(1)
root.left, root.right = Node(2), Node(3)
root.left.left, root.left.right = Node(4), Node(5)
root.left.right.left, root.left.right.right = Node(7), Node(8)
root.right.right = Node(6)
# Em seguida, podemos percorrer recursivamente toda a árvore binária
# Vamos calcular a soma de todos os nós
def treesum(node: Node | None) -> int:
if node is None:
return 0
# Retornar a soma da subárvore esquerda, da subárvore direita e do nó atual
return treesum(node.left) + treesum(node.right) + node.value
print(treesum(root)) # Imprime 36Neste exemplo, percorremos todos os nós a partir de
root. Se o nó atual for None, isso significa que chegámos ao fim da subárvore nesse ramo, por isso podemos retornar 0 como soma. Caso contrário, podemos calcular a soma da subárvore esquerda, da subárvore direita e do nó atual, adicionando tudo.Desafio: Criar manualmente uma árvore binária
Dada a árvore binária na imagem, pede-se que a crie manualmente.
Escreva um código que construa a árvore binária. Não precisa de imprimir nada; essa parte é tratada automaticamente.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB