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
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?
a,b,k,l,m,z,c,d,e,f,g,h,i,j,o,p,q,r
onde:
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.
• 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 filhos, a gente sabe que os próximos
blocos da pré-ordem são as subárvores (na ordem) daquele nó.
• 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
Passo 3
Vamos fazer isso “no braço”:
-
Começa em a (3 filhos).
-
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:
(i) passo por todas as subárvores da esquerda pra direita,
(ii) só então imprimo o próprio nó.
Aplicando recursivamente:
- Subárvore de b: filhos k, l, m(z) →
k, l, z, m, b - 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
- Subárvore de o: p, q® → p, r, q, o
- 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.
k, l, z, m, b, d, f, h, i, j, g, e, c, p, r, q, o, a.