Escreva funções não recursivas para realizar os 3 tipos de percurso na árvore binária (dica: use uma pilha):
(a) pré-ordem
(a) pré-ordem
Passo 1
Vamos recapitular: o exercício pede uma função não recursiva para percorrer uma árvore binária em pré-ordem (ou seja, visitar nó, depois subárvore esquerda e depois subárvore direita), usando uma pilha.
Passo 2
Na abordagem recursiva, a gente faria assim: visitar o nó, chamar recursivamente o filho esquerdo e depois o filho direito. Para transformar isso em não recursivo, precisamos simular a pilha de chamadas com uma pilha explícita.
Passo 3
A ideia-chave é: empilhar o nó raiz; enquanto a pilha não estiver vazia, desempilhar um nó, visitá-lo e então empilhar primeiro o filho direito e depois o esquerdo. Assim, o próximo nó desempilhado é sempre o da subárvore esquerda (respeitando pré-ordem).
Passo 4
A seguir, o pseudocódigo detalhado da função não recursiva de pré-ordem.
Resposta
função preOrdemIterativa(raiz):
se raiz = null então
retorne
S ← pilha vazia
empilha(S, raiz)
enquanto não vazia(S):
nodo ← desempilha(S)
imprime nodo.valor // visita o nó
se nodo.direita ≠ null então
empilha(S, nodo.direita)
se nodo.esquerda ≠ null então
empilha(S, nodo.esquerda)
se raiz = null então
retorne
S ← pilha vazia
empilha(S, raiz)
enquanto não vazia(S):
nodo ← desempilha(S)
imprime nodo.valor // visita o nó
se nodo.direita ≠ null então
empilha(S, nodo.direita)
se nodo.esquerda ≠ null então
empilha(S, nodo.esquerda)