Considere uma árvore binária cuja estrutura é percorrida em...
existe algum macete para montar uma árvore a partir do seu percurso?
Força Guerreiro!!!!!!
olhar para a raiz ......tranquilo
Em ordem -> preencher da esquerda para a direita
(visualmente é só colocar a posição dos nós direto na lista)
ex:
-----1-----
2--------3
fica: [2,1,3]
pré-ordem -> desce da esquerda para direita e para cada nó que passar já coloca na lista
ex:
-----1-----
2--------3
fica: [1,2,3]
pós-ordem -> desce da esquerda para a direita só coloca um nó na lista quando ele não tem mais filhos
ex:
-----1-----
2--------3
fica: [2,3,1]
Eu tinha muita dificuldade em entendem o percurso de uma árvore porque as explicações eram muito técnicas.
No link abaixo tem uma forma de não esquecer nunca:
https://uploaddeimagens.com.br/imagens/wl31-_s
A alternativa D é a correta.
Vamos entender por que essa alternativa está correta e como a questão aborda o tema de percursos em árvore binária.
Primeiramente, é importante saber que existem três tipos principais de percursos em árvores binárias: pré-ordem (preorder), em-ordem (inorder) e pós-ordem (postorder).
- Pré-ordem (preorder): Visita a raiz, depois a subárvore esquerda e, por fim, a subárvore direita.
- Em-ordem (inorder): Visita a subárvore esquerda, depois a raiz e, por fim, a subárvore direita.
- Pós-ordem (postorder): Visita a subárvore esquerda, depois a subárvore direita e, por fim, a raiz.
Na questão, foram fornecidos os percursos em em-ordem [d, b, e, a, f, c, g] e pré-ordem [a, b, d, e, c, f, g].
Para encontrar o percurso pós-ordem, precisamos seguir a lógica de construção da árvore e depois aplicar a regra do percurso pós-ordem.
Primeiro, construímos a árvore usando os percursos em-ordem e pré-ordem:
Passo 1: A raiz é o primeiro elemento do percurso pré-ordem: a.
Passo 2: No percurso em-ordem, os elementos à esquerda de a (ou seja, [d, b, e]) formam a subárvore esquerda. Os elementos à direita (ou seja, [f, c, g]) formam a subárvore direita.
Passo 3: Repetimos o processo para cada subárvore.
Após construir a árvore, aplicamos o percurso pós-ordem:
- Subárvore esquerda de a: [d, e, b]
- Subárvore direita de a: [f, g, c]
Visita em pós-ordem:
1. Subárvore esquerda de a:
Visite a subárvore esquerda de b (d), depois a direita (e), e finalmente b:
d, e, b
2. Subárvore direita de a:
Visite a subárvore esquerda de c (f), depois a direita (g), e finalmente c:
f, g, c
3. Finalmente, visitamos a raiz a:
a
Portanto, o percurso pós-ordem é: d, e, b, f, g, c, a, que corresponde à alternativa D.
Vamos analisar por que as outras alternativas estão incorretas:
- Alternativa A: [d, e, f, g, b, c, a]
- Erra ao posicionar f e g antes de b.
- Alternativa B: [e, d, b, f, g, c, a]
- Erra na ordem de d e e.
- Alternativa C: [e, d, b, g, f, c, a]
- Erra na ordem de f e g.
- Alternativa E: "Nenhuma das anteriores" é incorreta, pois a alternativa D é a correta.
Espero que esta explicação tenha ajudado a entender melhor como resolver questões que envolvem percursos em árvore binária. Qualquer dúvida, estou à disposição!