Escreva funções não recursivas para realizar os 3 tipos de percurso na árvore binária (dica: use uma pilha):
(b) em-ordem
(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
iniciado na raiz. Enquanto
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:
- Inicialize
e uma pilha vazia. - Enquanto
ou pilha não vazia:
a. Se: empilhe e faça .
b. Senão (): desempilhe um nó, imprima seu valor, e atribua . - 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;
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;
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;
}
}