Introdução

A travessia de árvores binárias pode ser implementada iterativamente utilizando estruturas de dados auxiliares. Abordaremos quatro variações: pré-ordem, em-ordem, pós-ordem e em nível.

Pré-Ordem

Visita o nó atual antes de seus descendnetes. Utiliza-se uma pilha para rastrear nós pendentes. A lógica consiste em:

1. Empilhra a raiz
2. Enquanto a pilha não estiver vazia:
   • Desempilhar um nó e processar seu valor
   • Empilhar o filho direito (se existir)
   • Empilhar o filho esquerdo (se existir)

def preordem_iterativa(raiz):
    if not raiz:
        return []
    pilha = [raiz]
    resultado = []
    while pilha:
        no = pilha.pop()
        resultado.append(no.valor)
        if no.direita:
            pilha.append(no.direita)
        if no.esquerda:
            pilha.append(no.esquerda)
    return resultado

Em-Ordem

Visita a subárvore esquerda, depois o nó atual e finalmente a direita. Mantém um ponteiro para o nó atual e uma pilha:

def emordem_iterativa(raiz):
    pilha = []
    atual = raiz
    resultado = []
    while atual or pilha:
        while atual:
            pilha.append(atual)
            atual = atual.esquerda
        atual = pilha.pop()
        resultado.append(atual.valor)
        atual = atual.direita
    return resultado

Pós-Ordem

Visita os filhos antes do nó atual. Requer um ponteiro adicional para rastrear o último nó visitado:

def posordem_iterativa(raiz):
    pilha = []
    atual = raiz
    ultimo = None
    resultado = []
    while atual or pilha:
        while atual:
            pilha.append(atual)
            atual = atual.esquerda
        topo = pilha[-1]
        if not topo.direita or topo.direita == ultimo:
            resultado.append(topo.valor)
            ultimo = pilha.pop()
        else:
            atual = topo.direita
    return resultado

Em Nível

Visita nós nível por nível usendo uma fila. Implementação BFS clássica:

def nivel_iterativo(raiz):
    if not raiz:
        return []
    fila = [raiz]
    resultado = []
    while fila:
        no = fila.pop(0)
        resultado.append(no.valor)
        if no.esquerda:
            fila.append(no.esquerda)
        if no.direita:
            fila.append(no.direita)
    return resultado

Estruturas de Suporte

Implementações básicas para nó da árvore e estruturas auxiliares:

class No:
    def __init__(self, val):
        self.valor = val
        self.esquerda = None
        self.direita = None

# Pilha otimizada usando deque
from collections import deque

class Pilha(deque):
    def empilhar(self, item):
        self.append(item)
    
    def topo(self):
        return self[-1] if self else None

class Fila(deque):
    def enfileirar(self, item):
        self.append(item)
    
    def desenfileirar(self):
        return self.popleft() if self else None