Alternativa E - É impossível imprimir os números de 1 a 7, em ordem ascendente, utilizando este método
Análise da Questão
A questão pede para identificar qual combinação de chamadas recursivas produzirá uma saída ordenada ($1, 2, 3, 4, 5, 6, 7$) em uma árvore binária específica.
Para resolver, precisamos entender a estrutura da árvore e o comportamento dos algoritmos de travessia (percurso).
1. Estrutura da Árvore
Observando a imagem, temos uma árvore completa onde os valores aumentam conforme descemos os níveis:
- Nível 0 (Raiz): 1
- Nível 1: 2, 3
- Nível 2: 4, 5, 6, 7
O objetivo é obter a sequência 1, 2, 3, 4, 5, 6, 7. Isso corresponde a uma travessia por Nível (BFS - Breadth-First Search), onde visitamos todos os nós de um nível antes de descer para o próximo.
2. Comportamento do Código
O método fornecido é recursivo. Funções recursivas padrão em árvores realizam travessias de profundidade (DFS - Depth-First Search). Elas exploram um ramo até o fim antes de voltar e explorar outro.
- Não é possível implementar uma travessia por nível estrita usando apenas essa assinatura recursiva simples sem estruturas auxiliares como filas.
3. Testando as Opções
Vamos analisar o que cada opção gera ao ser executada na árvore dada:
| Opção | Ordem das Instruções | Tipo de Travessia | Sequência Gerada | Correta? |
|---|
| I | Esq \rightarrow Imprimir \rightarrow Dir | In-Ordem | 4, 2, 5, 1, 6, 3, 7 | Não |
| II | Imprimir \rightarrow Esq \rightarrow Dir | Pré-Ordem | 1, 2, 4, 5, 3, 6, 7 | Não |
| III | Dir \rightarrow Esq \rightarrow Imprimir | Pós-Ordem (Reverso) | 7, 6, 3, 5, 4, 2, 1 | Não |
| IV | Dir \rightarrow Imprimir \rightarrow Esq | In-Ordem (Reverso) | 7, 3, 6, 1, 5, 2, 4 | Não |
Por que a Opção II falha?
A Opção II (Pré-Ordem) começa corretamente imprimindo a raiz (1). Em seguida, ela recursivamente chama o filho esquerdo (2). Antes de visitar o irmão direito (3), ela precisa terminar toda a subárvore esquerda.
- Após o 1, visita-se o 2.
- Para o 2, visita-se seu filho esquerdo 4.
- Depois o filho direito 5.
- Só então volta para visitar o filho direito da raiz, que é o 3.
- Resultado parcial: 1, 2, 4, 5, 3... (O número 3 aparece depois de 4 e 5).
Como nenhuma das combinações recursivas consegue visitar o nó 3 antes de visitar os nós 4 e 5, é tecnicamente impossível obter a ordem ascendente desejada com este método específico.
Conclusão
A única alternativa que reflete a impossibilidade técnica de obter a sequência exata através de uma travessia DFS recursiva simples é a letra E.