Como será a impressão pós-ordem dos nós de uma árvore binári...

Para resolver essa questão, é fundamental entender o conceito de árvore binária de busca e o pós-ordem de uma árvore. Em uma árvore binária de busca, cada nó tem no máximo dois filhos e segue o princípio onde, para cada nó, todos os valores dos nós à esquerda são menores, e todos os valores dos nós à direita são maiores.

A traversal pós-ordem (ou pós-fixada) significa visitar primeiro o filho à esquerda, depois o filho à direita, e por último o nó pai. Para resolver a questão, é necessário construir a árvore binária de busca a partir da sequência de inserção dada e, em seguida, realizar a travessia pós-ordem.

A alternativa correta é a letra C: 1 – 4 – 3 – 10 – 8 – 5 – 16 – 20 – 18 – 25 – 31 – 22 – 12.

Justificativa:

Vamos construir a árvore binária de busca com os valores na seguinte ordem: 12, 5, 22, 8, 3, 31, 4, 25, 1, 18, 10, 20, 16:

• 12 é o primeiro valor e se torna a raiz.
• 5 é menor que 12, vai à esquerda.
• 22 é maior que 12, vai à direita.
• 8 é maior que 5, vai à direita de 5.
• 3 é menor que 5, vai à esquerda de 5.
• 31 é maior que 22, vai à direita de 22.
• 4 é maior que 3, vai à direita de 3.
• 25 é menor que 31, vai à esquerda de 31.
• 1 é menor que 3, vai à esquerda de 3.
• 18 é menor que 22, vai à esquerda de 22.
• 10 é maior que 8, vai à direita de 8.
• 20 é maior que 18, vai à direita de 18.
• 16 é menor que 18, vai à esquerda de 18.

Realizando a travessia pós-ordem, visitamos os nós na seguinte ordem: 1 – 4 – 3 – 10 – 8 – 5 – 16 – 20 – 18 – 25 – 31 – 22 – 12, que corresponde à alternativa C.

Alternativas Incorretas:

A: 1 – 3 – 4 – 5 – 8 – 10 – 12 – 16 – 18 – 20 – 22 – 25 – 31. Essa sequência corresponde a uma traversal in-ordem, não pós-ordem.

B: 31 – 25 – 22 – 20 – 18 – 16 – 12 – 10 – 8 – 5 – 4 – 3 – 1. Esta é uma traversal pré-ordem invertida e não representa uma pós-ordem.

D: 1 – 4 – 10 – 16 – 20 – 25 – 3 – 8 – 18 – 31 – 5 – 22 – 12. Esta sequência não segue a lógica da travessia pós-ordem da árvore construída.

Espero que esta explicação tenha tornado o processo mais claro. Gostou do comentário? Deixe sua avaliação aqui embaixo!

GABARITO C

A questão trata de uma árvore binária de busca. Nessa árvore, os valores são ordenados em uma sub árvore esquerda e uma sub árvore direita. Sendo assim, teremos 13 elementos para organizar: 1,3,4,5,8,10,12, 16, 18, 20 , 22, 25 e 31. Os valores mais a esquerda são menores e os valores a direita são. maiores. O elemento central será a raiz. No caso da nossa árvore a raiz será o 12 que está no meio. 

Dito isso, a questão pede que se faça uma busca pós ordem nessa árvore. Nessa busca, seguimos a lógica E - D -RAIZ. A raiz sempre fica por último tanto na árvore principal quanto nas subárvores. Dessa maneira, sabe-se que o 12 é o último. Ficamos entre C e D. gora, vejamos qual é a correta:

c)  1 – 4 – 3 – 10 – 8 – 5 – 16 – 20 – 18 – 25 – 31 – 22 – 12. // Essa é a correta, já que o 5 não está próximo ao final, pois é um elemento de valor baixo na sequência.

d)  1 – 4 – 10 – 16 – 20 – 25 – 3 – 8 – 18 – 31 – 5 – 22 – 12.

A árvore binária de busca segue a regra de que todos nós possuem subárvores a sua esquerda com valores menores que o seu e subárvores a direita com valores maiores que o seu, com exceção dos nós folhas. É importante destacar que nem toda árvore binária de busca é estritamente binária, isto é, possui todos os seus nós com grau 2 ou 0, ou seja, a ordem em que os elementos aparecem importa. 12 (raiz), 5(esquerda raiz), 22(direita raiz), 8(direita 5), 3 (esquerda 5), 31(direita 31), 4(direita 3), 25(esquerda 31), 1(esquerda 3), 18(esquerda 22), 10 (direita 8), 20(direita 18), 16(esquerda 18).

Para verificar se está em pré-ordem, ordem ou pós-ordem eu uso o seguinte macete: Desenhe a árvore a ser analisada, faça um ponto à esquerda, abaixo e a direita de todos os números, agora, se você desejar saber se os elementos estão em ordem, a partir da esquerda da raiz, contorne todos os ponto até que todos os pontos da esquerda sejam conectados. Para ordem, a partir da esquerda da raiz acompanhe o contorno da árvore até que o primeiro ponto inferior apareça e a partir dele conecte todos. Por fim, na pré-ordem, a partir da esquerda da raiz acompanhe o contorno da árvore até que o primeiro ponto da direita apareça e a partir dele conecte os demais. A ordem de conexão dos pontos é a ordem que a árvore busca deve apresentar na questão.

Pré-Ordem: RAIZ - Esquerda - Direita

In-Ordem: Esquerda - RAIZ - Direita

Pós-Ordem: Esquerda - Direita - RAIZ

Primeiro montar a Árvore

            12

          /   \

        5      22

       / \      / \

      3   8    18  31

     / \       / \   /

    1   4     16 20   25

Complementando as respostas dos colegas, irei fazer para nível de estudo as respostas do Pré- Ordem e In-Ordem.

• Pré-Ordem: 12, 5, 3, 1, 4, 8, 10, 22, 31, 25, 18, 16, 20
• In-Ordem: 1, 3, 4, 5, 8, 10, 12, 16, 18, 20, 22, 25, 31

Pré-ordem: 12, 5, 3, 1, 4, 8, 10, 22, 18, 16, 20, 31, 25