Escreva funções não recursivas para realizar os 3 tipos de percurso na árvore binária (dica: use uma pilha):
© pós-ordem
© 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>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
int data;
struct Node* left;
struct Node* right;
} Node;
void postOrder(Node* root) {
if (root == NULL) return;
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--;
}
}
}
}