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

Passo 1

O enunciado pede uma versão não recursiva do percurso em-ordem (left–root–right) em uma árvore binária, usando uma pilha para simular a recursão. Estamos em Estruturas de Dados e precisamos usar explicitamente uma pilha de ponteiros para nós.

Passo 2

A ideia central é manter um ponteiro auxiliar current iniciado na raiz. Enquanto current não for nulo ou a pilha não estiver vazia, descer à esquerda, empilhando cada nó visitado; quando não houver mais filhos à esquerda, desempilhar, visitar o nó e então passar para a subárvore direita.

Passo 3

Passo a passo do algoritmo:
  1. Inicialize current = root e uma pilha vazia.
  2. Enquanto current neq NULL ou pilha não vazia:
    a. Se current neq NULL: empilhe current e faça current = current-><=ft.
    b. Senão ( current == NULL): desempilhe um nó, imprima seu valor, e atribua current = nó->rightó.
  3. Repita até terminar.

Passo 4

Traduzindo para C (ou linguagem similar), temos uma função que recebe a raiz, usa uma pilha explícita (vetor ou lista) de ponteiros para os nós e realiza o laço acima. A visitação (impressão) ocorre no momento em que o nó é desempilhado.

Resposta

// Estrutura básica do nó
typedef struct Node {
int value;
struct Node *left, *right;
} Node;
// Percurso em-ordem não recursivo usando pilha
void inorderNonRec(Node *root) {
// pilha de ponteiros para Node
Node *stack[100]; // ou alocar dinamicamente conforme necessidade
int top = -1;
Node *current = root;
// enquanto houver nó atual ou pilha não vazia
while (current != NULL || top >= 0) {
    // desce toda a subárvore à esquerda
    while (current != NULL) {
        stack[++top] = current;
        current = current->left;
    }
    // desempilha o último nó à esquerda
    current = stack[top--];
    // visita (imprime) o nó
    printf("%d ", current->value);
    // agora explora a subárvore direita
    current = current->right;
}
}

Exercícios relacionados