Questão de Tecnologia da Informação · FGV TJ-AP 2024 (nº 62)

Uma árvore binária é uma estrutura de dados onde cada nó (elemento) pode ter no máximo dois filhos: um filho à esquerda e um filho à direita. Os percursos (ou varreduras) são formas de visitar todos os nós de uma árvore, seguindo ordens específicas: pré-ordem (Raiz, Esquerda, Direita), in-ordem (Esquerda, Raiz, Direita) e pós-ordem (Esquerda, Direita, Raiz).

Vamos calcular os percursos para a Árvore (I) conforme a imagem:

• Árvore (I):
  • Pré-ordem (Raiz, Esquerda, Direita): 10, 5, 3, 7, 15, 12, 18
  • In-ordem (Esquerda, Raiz, Direita): 3, 5, 7, 10, 12, 15, 18
  • Pós-ordem (Esquerda, Direita, Raiz): 3, 7, 5, 12, 18, 15, 10

A imagem mostra a Árvore (II) idêntica à Árvore (I). No entanto, para que a alternativa (C) seja correta, a Árvore (II) precisa ser distinta e ter um percurso em pré-ordem específico. Isso sugere que a imagem da Árvore (II) pode ser enganosa ou que a questão se refere a uma Árvore (II) hipotética que satisfaz a condição.

Para que a varredura da Árvore (I) em in-ordem (3, 5, 7, 10, 12, 15, 18) seja equivalente à varredura da Árvore (II) em pré-ordem, a Árvore (II) teria que ser uma árvore binária degenerada (inclinada para a direita):
3

5

7

10

12

15

18

• Árvore (II) (hipotética):
  • Pré-ordem (Raiz, Esquerda, Direita): 3, 5, 7, 10, 12, 15, 18
  • In-ordem (Esquerda, Raiz, Direita): 3, 5, 7, 10, 12, 15, 18
  • Pós-ordem (Esquerda, Direita, Raiz): 18, 15, 12, 10, 7, 5, 3

Com base nesta interpretação (necessária para validar o gabarito), vamos analisar as alternativas:

• (A) Incorreta: "disjuntas" é falso, pois ambas as árvores (a Árvore I e a Árvore II hipotética) contêm os mesmos elementos. Além disso, Árvores B são estruturas diferentes (árvores multi-way) e não se aplicam aqui.
• (B) Incorreta: Se as árvores fossem "equivalentes" (o que a imagem sugere, mas a alternativa C contradiz), a primeira parte seria verdadeira. No entanto, a varredura da árvore (I) em pós-ordem (3, 7, 5, 12, 18, 15, 10) não é a mesma que a varredura da árvore (II) em in-ordem (3, 5, 7, 10, 12, 15, 18, seja a da imagem ou a hipotética).
• (C) Correta: A pegadinha aqui é que, para esta alternativa ser verdadeira, a Árvore (II) não pode ser a que está desenhada na imagem, mas sim uma árvore diferente.
  • "distintas": Sim, a Árvore (I) (balanceada) e a Árvore (II) hipotética (degenerada) são estruturalmente distintas.
  • "a operação de varredura da árvore (I) em in-ordem equivale à varredura da árvore (II) em pré-ordem":
    • In-ordem de (I): 3, 5, 7, 10, 12, 15, 18
    • Pré-ordem da Árvore (II) hipotética: 3, 5, 7, 10, 12, 15, 18
    • As sequências são idênticas. Portanto, a afirmação é verdadeira sob essa interpretação.
• (D) Incorreta: Ambas as árvores (I e a II hipotética) são Árvores Binárias de Busca (BSTs), o que significa que seus elementos são "ordenados" (a varredura in-ordem resulta em uma sequência ordenada). Portanto, a afirmação "desordenadas" é falsa. A segunda parte da afirmação ("pré-ordem gera um conjunto em notação pós-fixa de (II) invertido") é verdadeira apenas para a Árvore (II) hipotética (3,5,7... é o inverso de ...7,5,3), mas a primeira parte já invalida a alternativa.
• (E) Incorreta: "ordenadas" é verdadeiro, pois são BSTs. No entanto, a varredura em in-ordem produz uma sequência ordenada, mas não é uma "ordenação por seleção direta". Seleção direta é um algoritmo de ordenação, não o resultado de um percurso de árvore. O percurso apenas visita os nós em uma ordem específica.