A travessia de árvores binárias é uma operação fundamental em estruturas de dados. Embora a recursão seja a forma mais intuitiva de implementar esses algoritmos, o uso de uma abordagem iterativa com uma pilha mannual oferece maior controle sobre a memória e evita riscos de estouro de pilha (stack overflow) em árvores de grande profundidade.

Estrutura da Pilha Encadeada

Para suportar a travessia, definimos primeiro uma pilha encadeada genérica. Esta estrutura permite armazenar diferentes tipos de dados através da inclusão de um nó de controle nas structs personalizadas.

#include <stdio.h>
#include <stdlib.h>

// Estrutura básica do nó da pilha
typedef struct NoPilha {
    struct NoPilha* proximo;
} NoPilha;

// Descritor da pilha
typedef struct {
    NoPilha cabeca;
    int tamanho;
} PilhaEncadeada;

// Inicialização
PilhaEncadeada* criar_pilha() {
    PilhaEncadeada* pilha = (PilhaEncadeada*)malloc(sizeof(PilhaEncadeada));
    pilha->cabeca.proximo = NULL;
    pilha->tamanho = 0;
    return pilha;
}

// Operação de Empilhar (Push)
void empilhar(PilhaEncadeada* pilha, NoPilha* dado) {
    if (pilha == NULL || dado == NULL) return;
    dado->proximo = pilha->cabeca.proximo;
    pilha->cabeca.proximo = dado;
    pilha->tamanho++;
}

// Operação de Desempilhar (Pop)
void desempilhar(PilhaEncadeada* pilha) {
    if (pilha == NULL || pilha->tamanho == 0) return;
    NoPilha* topo = pilha->cabeca.proximo;
    pilha->cabeca.proximo = topo->proximo;
    pilha->tamanho--;
}

// Obter o topo
NoPilha* topo_pilha(PilhaEncadeada* pilha) {
    if (pilha == NULL || pilha->tamanho == 0) return NULL;
    return pilha->cabeca.proximo;
}

Estrutura da Árvore Binária e Lógica de Travessia

Para a travessia iterativa, utilizamos um "nó de controle" na pilha que contém o ponteiro para o nó da árvore e um sinalizador (flag). Este sinalizador indica se o nó já foi processado ou se seus filhos ainda precisam ser explorados.

// Definição do nó da árvore binária
typedef struct NoArvore {
    char dado;
    struct NoArvore* esq;
    struct NoArvore* dir;
} NoArvore;

// Pacote para armazenamento na pilha
typedef struct {
    NoPilha link;
    NoArvore* nodo;
    int visitado;
} ItemPilha;

// Função auxiliar para criar o item da pilha
ItemPilha* criar_item_pilha(NoArvore* nodo, int status) {
    ItemPilha* novo = (ItemPilha*)malloc(sizeof(ItemPilha));
    novo->nodo = nodo;
    novo->visitado = status;
    return novo;
}

// Algoritmo de Travessia Não-Recursiva
void travessia_iterativa(NoArvore* raiz) {
    if (raiz == NULL) return;

    PilhaEncadeada* pilha = criar_pilha();
    empilhar(pilha, (NoPilha*)criar_item_pilha(raiz, 0));

    while (pilha->tamanho > 0) {
        ItemPilha* atual = (ItemPilha*)topo_pilha(pilha);
        desempilhar(pilha);

        if (atual->nodo == NULL) {
            free(atual);
            continue;
        }

        if (atual->visitado) {
            printf("%c ", atual->nodo->dado);
            free(atual);
        } else {
            // Para Pré-ordem: Direita -> Esquerda -> Raiz
            // Como a pilha é LIFO, a ordem de inserção é inversa ao processamento
            
            // 1. Inserir subárvore direita
            empilhar(pilha, (NoPilha*)criar_item_pilha(atual->nodo->dir, 0));
            
            // 2. Inserir subárvore esquerda
            empilhar(pilha, (NoPilha*)criar_item_pilha(atual->nodo->esq, 0));
            
            // 3. Reinserir nó atual marcado como visitado
            atual->visitado = 1;
            empilhar(pilha, (NoPilha*)atual);
        }
    }
    free(pilha);
}

Exemplo de Uso e Construção da Árvore

O exemplo abaixo demonstra a criação manual de uma árvore binária e a execução da travessia iterativa utilizando a lógica implementada.

void executar_demonstracao() {
    // Instanciação dos nós
    NoArvore nA = {'A', NULL, NULL}, nB = {'B', NULL, NULL}, nC = {'C', NULL, NULL};
    NoArvore nD = {'D', NULL, NULL}, nE = {'E', NULL, NULL}, nF = {'F', NULL, NULL};
    NoArvore nG = {'G', NULL, NULL}, nH = {'H', NULL, NULL};

    // Configuração das relações pai-filho
    nA.esq = &nB; nA.dir = &nF;
    nB.dir = &nC;
    nC.esq = &nD; nC.dir = &nE;
    nF.dir = &nG;
    nG.esq = &nH;

    printf("Iniciando travessia iterativa:\n");
    travessia_iterativa(&nA);
    printf("\n");
}

int main() {
    executar_demonstracao();
    return 0;
}

Nesta implementação, a ordem de processamento pode ser facilmente alterada para Em-ordem ou Pós-ordem apenas modificando a sequência de empilhamento dentro do bloco else da função travessia_iterativa.