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
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:
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
):
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).
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.