Construa uma árvore enraizada ordenada cujo caminhamento em pré-ordem é:
a,b,k,l,m,z,c,d,e,f,g,h,i,j,o,p,q,r
onde:
  • a, b e g têm 3 filhos cada;
  • e, c e o possuem 2 filhos cada;
  • m e q possuem um filho cada;
  • todos os outros vértices são folhas.
    Qual o caminhamento em pós-ordem?

Passo 1

Beleza, vamos recapitular o que a questão pede. A gente tem:
• Um caminhamento em pré-ordem:
a, b, k, l, m, z, c, d, e, f, g, h, i, j, o, p, q, r
• Informação de quantos filhos cada vértice tem (grau de saída):
- a, b e g têm 3 filhos
- c, e e o têm 2 filhos
- m e q têm 1 filho
- todo mundo mais é folha (0 filhos)
Conteúdo: árvores enraizadas ordenadas e seus percursos (pré- e pós-ordem).
O que precisaremos: entender definição de pré-ordem e pós-ordem, usar o número de filhos para montar a árvore pela lista pré-ordem, e depois “varrer” em pós-ordem.

Passo 2

Antes de encarar a montagem, bora lembrar:
• Pré-ordem de uma árvore = visita nó raiz, depois recorre recursivamente a cada subárvore da esquerda pra direita.
• Pós-ordem = recorre cada subárvore da esquerda pra direita e só depois visita a raiz.
Como temos o número exato de filhos de cada nó, dá pra “ler” a lista pré-ordem e ir construindo recursivamente: ao encontrar um nó que tem k filhos, a gente sabe que os próximos k blocos da pré-ordem são as subárvores (na ordem) daquele nó.

Passo 3

Vamos fazer isso “no braço”:
  1. Começa em a (3 filhos).
  2. Os três blocos seguintes são as subárvores de a. Primeiro bloco inicia em b (3 filhos), segundo em c (2 filhos), terceiro em o (2 filhos).
    2.1. Subárvore de b (3 filhos):
    • filho1 = k (0 filhos) → folha
    • filho2 = l (0 filhos) → folha
    • filho3 = m (1 filho): seu único filho é z (0 filhos)
      → subárvore de b montada.
    2.2. Subárvore de c (2 filhos):
    • filho1 = d (0 filhos)
    • filho2 = e (2 filhos):
      • e→filho1 = f (0)
      • e→filho2 = g (3 filhos): h, i, j (todas folhas)
    2.3. Subárvore de o (2 filhos):
    • filho1 = p (0 filhos)
    • filho2 = q (1 filho): q→filho = r (0 filhos)
Pronto, árvore reconstruída.

Passo 4

Agora, para o pós-ordem, a regra é: para cada nó,
(i) passo por todas as subárvores da esquerda pra direita,
(ii) só então imprimo o próprio nó.
Aplicando recursivamente:
  1. Subárvore de b: filhos k, l, m(z) →
    k, l, z, m, b
  2. Subárvore de c:
    • d → d
    • e(f, g(h, i, j)) → f, h, i, j, g, e
      → junta: d, f, h, i, j, g, e, c
  3. Subárvore de o: p, q® → p, r, q, o
  4. Por fim a

Resposta

O caminhamento em pós-ordem fica:
k, l, z, m, b, d, f, h, i, j, g, e, c, p, r, q, o, a.

Exercícios relacionados