Este artigo explora técnicas para manipular árvores binárias, contrastando abordagens recursivas com implementações iterativas baseadas em pilha. Os conceitos são demonstrados em código.

1. Troca Recursiva dos Filhos Esquerdo e Direito

A seguinte função percorre a árvore recursivamente. Para cada nó visitado, ela troca suas subárvores esquerda e direita. A recursão continua até que todos os nós sejam processados.

typedef struct no_arvore_binaria {
    int valor;
    struct no_arvore_binaria *filho_esq;
    struct no_arvore_binaria *filho_dir;
} NoArvore;

void troca_subarvores_recursivo(NoArvore *raiz) {
    if (raiz == NULL) {
        return;
    }

    // Troca os filhos no nó atual.
    NoArvore *auxiliar = raiz->filho_esq;
    raiz->filho_esq = raiz->filho_dir;
    raiz->filho_dir = auxiliar;

    // Processa recursivamente as subárvores.
    troca_subarvores_recursivo(raiz->filho_esq);
    troca_subarvores_recursivo(raiz->filho_dir);
}

2. Troca Iterativa usando uma Pilha

Esta versão substitui a chamada recursiva por uma estrutura de dados pilha explícita. O algoritmo empilha o nó raiz e, em seguida, entra em um loop que processa os nós da pilha, trocanod seus filhos e empilhando seus descendentes.

#include <stdlib.h>

typedef struct elemento_pilha {
    NoArvore *no;
    struct elemento_pilha *proximo;
} ElementoPilha;

typedef struct {
    ElementoPilha *topo;
} Pilha;

void inicializar_pilha(Pilha *p) {
    p->topo = NULL;
}

int pilha_vazia(Pilha *p) {
    return (p->topo == NULL);
}

void empilhar(Pilha *p, NoArvore *no) {
    ElementoPilha *novo = malloc(sizeof(ElementoPilha));
    novo->no = no;
    novo->proximo = p->topo;
    p->topo = novo;
}

NoArvore* desempilhar(Pilha *p) {
    if (pilha_vazia(p)) return NULL;
    ElementoPilha *topo_antigo = p->topo;
    NoArvore *no = topo_antigo->no;
    p->topo = topo_antigo->proximo;
    free(topo_antigo);
    return no;
}

void troca_subarvores_pilha(NoArvore *raiz) {
    if (raiz == NULL) return;

    Pilha pilha_processamento;
    inicializar_pilha(&pilha_processamento);
    empilhar(&pilha_processamento, raiz);

    while (!pilha_vazia(&pilha_processamento)) {
        NoArvore *atual = desempilhar(&pilha_processamento);

        // Operação principal: trocar filhos.
        NoArvore *temp = atual->filho_esq;
        atual->filho_esq = atual->filho_dir;
        atual->filho_dir = temp;

        // Empilha os filhos para processamento posterior.
        if (atual->filho_esq != NULL) {
            empilhar(&pilha_processamento, atual->filho_esq);
        }
        if (atual->filho_dir != NULL) {
            empilhar(&pilha_processamento, atual->filho_dir);
        }
    }
}

3. Travessia Pré-Ordem Iterativa (Raiz-Esquerda-Direita)

A travessia pré-ordem visita a raiz primeiro. A implementação iterativa utiliza uma pilha e um padrão onde, após desempilhar um nó, seus filhos direito e esquerdo são empilhados (nessa ordem) para garentir que o filho esquerdo seja processado antes.

void percurso_preordem(NoArvore *raiz, void (*visita)(int)) {
    if (raiz == NULL) return;

    Pilha pilha;
    inicializar_pilha(&pilha);
    empilhar(&pilha, raiz);

    while (!pilha_vazia(&pilha)) {
        NoArvore *corrente = desempilhar(&pilha);
        visita(corrente->valor);

        // Empilha primeiro o filho direito.
        if (corrente->filho_dir != NULL) {
            empilhar(&pilha, corrente->filho_dir);
        }
        // Empilha o filho esquerdo por último, para ser processado primeiro.
        if (corrente->filho_esq != NULL) {
            empilhar(&pilha, corrente->filho_esq);
        }
    }
}

4. Travessia Em-Ordem Iterativa (Esquerda-Raiz-Direita)

A travessia em-ordem requer uma abordagem diferante. O algoritmo deve percorrer o caminho mais à esquerda, empilhando os nós encontrados, antes de visitá-los e explorar suas subárvores direitas. O nó atual é mantido por uma variável separada da pilha.

void percurso_emordem(NoArvore *raiz, void (*visita)(int)) {
    Pilha pilha;
    inicializar_pilha(&pilha);
    NoArvore *corrente = raiz;

    while (corrente != NULL || !pilha_vazia(&pilha)) {
        // Desce até a folha mais à esquerda, empilhando o caminho.
        while (corrente != NULL) {
            empilhar(&pilha, corrente);
            corrente = corrente->filho_esq;
        }

        // A folha mais à esquerda é desempilhada e visitada.
        corrente = desempilhar(&pilha);
        visita(corrente->valor);

        // A exploração move-se para a subárvore direita.
        corrente = corrente->filho_dir;
    }
}