Escreva funções não recursivas para realizar os 3 tipos de percurso na árvore binária (dica: use uma pilha):
© pós-ordem

Passo 1

Estamos lidando com percurso pós-ordem (esquerda, direita, raiz) em árvore binária sem usar recursão, e a dica é usar uma pilha.

Passo 2

Para percorrer em pós-ordem sem recursão precisamos simular o comportamento da chamada de pilha do sistema. A ideia central é visitar primeiro o nó mais à esquerda, depois o da direita, e só então processar o nó pai, mantendo uma referência ao último nó visitado.

Passo 3

Vamos usar uma única pilha e um ponteiro auxiliar “lastVisited” que sinaliza qual foi o último nó processado. Sempre que estivermos indo para a esquerda, empilhamos o nó. Quando não há mais para onde ir à esquerda, olhamos o topo da pilha: se ele tiver subárvore direita não visitada, descemos pra direita. Caso contrário, processamos o nó do topo.

Passo 4

O passo a passo do algoritmo é: iniciar current em root e lastVisited em NULL. Enquanto current não for NULL ou pilha não estiver vazia, se current existir empilhe-o e vá para current->left. Senão, olhe o topo sem desempilhar; se seu right for não-NULL e diferente de lastVisited, defina current = top->right; caso contrário, desempilhe, processe o nó (imprima), e atualize lastVisited.

Passo 5

Agora que entendemos a mecânica, implementamos em C definindo a estrutura Node com left, right e data, uma pilha estática e a função postOrder conforme descrito.

Resposta

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
void postOrder(Node* root) {
if (root == NULL) return;
Node* stack[100];
int top = -1;
Node* lastVisited = NULL;
Node* current = root;

while (current != NULL || top != -1) {
    if (current != NULL) {
        stack[++top] = current;
        current = current->left;
    } else {
        Node* peekNode = stack[top];
        if (peekNode->right != NULL && lastVisited != peekNode->right) {
            current = peekNode->right;
        } else {
            printf("%d ", peekNode->data);
            lastVisited = peekNode;
            top--;
        }
    }
}
}

Exercícios relacionados