QUESTÕES:

3 - (POSCOMP 2024 - Adaptado) No caminhamento de uma árvore T , a raiz de T é visitada em primeiro lugar, e então as subárvores enraizadas nos seus filhos são percorridas recursivamente. Assinale a alternativa que preenche corretamente a lacuna do trecho acima:
A) simétrico
B) em largura
C) central
D) pré-ordem
E) pós-ordem

Passo 1

Beleza, o exercício diz assim: “No caminhamento ____ de uma árvore T, a raiz de T é visitada em primeiro lugar, e então as subárvores enraizadas nos seus filhos são percorridas recursivamente.” A gente precisa identificar qual é esse tipo de caminhamento em árvores. Isso faz parte da matéria de estruturas de dados — especificamente, percorrimentos (ou “traversals”) de árvores. Para resolver, vamos relembrar o que cada travessia faz e ver qual bate com “visitar a raiz primeiro e depois as subárvores”.

Passo 2

O que é pré-ordem (pre-order)?
Em teoria de árvores, os percursos mais comuns são:
  • pré-ordem (pre-order): visita primeiro a raiz, depois recursivamente cada subárvore;
  • em-ordem ou simétrico (in-order): recorre a subárvore esquerda, depois visita a raiz, depois a subárvore direita (só faz sentido em árvores binárias);
  • pós-ordem (post-order): visita primeiro todas as subárvores e só depois a raiz;
  • em largura (breadth-first ou level-order): visita nível a nível, da raiz para baixo.
Em LaTeX, a ideia do pré-order fica assim (para uma árvore de grau genérico com filhos preOrder(v): visitar(v), para cada filho u de v faça preOrder(u) ):
ç
Repara: a definição fala exatamente “visitar o nó raiz primeiro” e só depois fazer a recursão nas subárvores.

Passo 3

Vamos eliminar as outras opções:
A) simétrico = in-order: raiz no meio (não bate).
B) em largura = level-order: não é recursivo por subárvore, é por níveis.
C) central = outro nome de in-order (não bate).
E) pós-ordem = primeiro subárvores, depois raiz (o oposto).
Sobrou “pré-ordem”, que é a única que visita a raiz antes de tudo e depois entra nas subárvores recursivamente.

Resposta

A alternativa correta é a D) pré-ordem.

Exercícios relacionados