Uma árvore binária é uma estrutura hierárquica em que cada nó tem no máximo dois filhos, chamados left e . Possui uma única ; nós sem filhos são . É a base para BSTs, heaps e árvores de expressão.
Uma árvore binária é uma estrutura hierárquica em que cada nó tem no máximo dois filhos, chamados left e . Possui uma única ; nós sem filhos são . É a base para BSTs, heaps e árvores de expressão.
right 1 depth 0 (root)
/ \
2 3 depth 1
/ \
4 5 depth 2 (leaves: 4,5,3)
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def inorder(n): # left, node, right -> 4 2 5 1 3
if n:
inorder(n.left); print(n.val); inorder(n.right)
def preorder(n): # node, left, right -> 1 2 4 5 3
if n:
print(n.val); preorder(n.left); preorder(n.right)
def postorder(n): # left, right, node -> 4 5 2 3 1
if n:
postorder(n.left); postorder(n.right); print(n.val)
Uma travessia level-order (BFS) usa uma fila e visita profundidade por profundidade.
| Travessia | Ordem | Uso comum |
|---|---|---|
| Inorder | L, N, R | saída ordenada de um BST |
| Preorder | N, L, R | copiar/serializar uma árvore |
| Postorder | L, R, N | deletar uma árvore, avaliar expressão |
| Level-order | por profundidade | BFS, caminho mais curto em árvore |
Cada travessia visita cada nó uma vez → O(n) tempo, O(h) espaço de pilha onde h é a altura da árvore.
Árvores binárias modelam naturalmente dados hierárquicos (sistemas de arquivos, árvores de análise, árvores de decisão) e sustentam estruturas eficientes de busca e ordenação.
Dominar as quatro travessias é essencial — a maioria dos problemas de entrevista de árvore é uma variação de uma delas.