Questão de Tecnologia da Informação · CESGRANRIO BB 01/2022 (nº 67)

Pré-ordem significa visitar primeiro a raiz, depois a subárvore esquerda inteira, e por último a subárvore direita inteira. A sequência 80 84 55 76 72 começa com 80, então 80 é a raiz; em seguida, tudo que vem antes de voltar para a direita pertence ao lado esquerdo.

• (A) Correta: A raiz é 80, o filho esquerdo é 84, e os filhos de 84 são 55 (esquerda) e 76 (direita); depois de visitar toda a esquerda, visita-se 72 à direita de 80. A ordem exata bate: 80 → 84 → 55 → 76 → 72.
• (B) Incorreta: Nesta árvore, após 80 e 84, o próximo seria 72 (filho direito de 80), mas a sequência exige 55 antes de 72, então a ordem ficaria 80 84 72 ....
• (C) Incorreta: Aqui a raiz 80 tem 84 à esquerda e 55 à direita; a pré-ordem seria 80 84 ... 55, mas 55 aparece antes de 76 e 72, o que não condiz com a sequência dada.
• (D) Incorreta: Se 80 tivesse 84 à direita, a pré-ordem seria 80 84 ..., mas 55 e 76 estariam na subárvore direita de 84, gerando 80 84 55 76 ... e depois 72 como filho direito de 80 — porém na árvore D, 72 está à esquerda de 84, o que inverteria a ordem final.
• (E) Incorreta: A raiz 80 tem 84 à esquerda e 72 à direita; a pré-ordem seria 80 84 ... 72, mas 55 e 76 não aparecem na posição correta (eles estariam dentro da subárvore de 84, mas a ordem exigida coloca 55 antes de 76 e 72 no final).

Armadilha da banca: A pegadinha mais tentadora é a letra B, porque ela também começa com 80 84 e muitos alunos param de conferir a partir do terceiro elemento. A banca coloca 72 como filho direito de 80 logo cedo, fazendo parecer que a sequência 80 84 55 76 72 poderia ser 80 → 84 → 55 → 76 → 72, mas na B o 72 é visitado antes de 55 e 76, pois ele é filho direto da raiz — então a ordem real seria 80 84 72 .... Sempre percorra a árvore inteira mentalmente, nó por nó, antes de marcar.