Em uma árvore binária de busca (BST), qual percurso produz os valores dos nós em ordem crescente de chave?
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Explorar e construir a solução de problemas por meio da reutilização de partes de soluções existentes.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em uma árvore binária de busca (BST), qual percurso produz os valores dos nós em ordem crescente de chave?
- A) O percurso em nível (level-order) garante a ordenação dos nós.
- B) Percurso em-ordem (in-order): visitar subárvore esquerda, raiz, subárvore direita.
- C) A ordem dos nós não pode ser garantida por nenhum tipo de percurso.
- D) Percurso pré-ordem (pre-order) gera sequência em ordem crescente.
- E) Percurso pós-ordem (post-order) produz valores em ordem crescente.
✅ Resposta correta: alternativa B
Resolução passo a passo
- Em uma árvore binária de busca, para todo nó, as chaves da subárvore esquerda são menores que a chave da raiz, e as chaves da subárvore direita são maiores.
- O percurso em-ordem visita primeiro a subárvore esquerda, depois a raiz e por fim a subárvore direita. Aplicando isso recursivamente, cada subárvore esquerda é impressa inteira antes da raiz, e a direita depois, o que produz as chaves em ordem crescente.
- Exemplo: na árvore com raiz 5, filhos 3 e 8, o in-ordem gera 3, 5, 8.
- A alternativa A está errada, pois o percurso em nível visita os nós por níveis (profundidade), não pela ordem das chaves, e não garante ordenação.
- A alternativa C está errada, pois o percurso em-ordem garante a ordenação justamente por causa da propriedade da BST.
- A alternativa D está errada, pois o pré-ordem visita a raiz antes das subárvores, gerando 5, 3, 8 no exemplo, que não está ordenado.
- A alternativa E está errada, pois o pós-ordem visita a raiz por último, gerando 3, 8, 5 no exemplo, também fora de ordem.
- Logo, o gabarito B está correto.
💡 Dica: Lembre-se do método de percurso em árvore binária.
Alternativa por alternativa
Acredita que, como o percurso em nível visita os nós de cima para baixo e da esquerda para a direita, a sequência resultante fica ordenada pelas chaves. Não percebe que a ordem por níveis depende da forma da árvore, não dos valores.
Por que engana: Confundir os diferentes tipos de percurso em árvores binárias e suas respectivas ordens de visitação.
O percurso em-ordem visita primeiro a subárvore esquerda e depois a raiz; em uma BST isso gera a sequência de chaves ordenada.
Supõe que a estrutura da árvore torna impossível obter uma ordem global dos valores por qualquer percurso. Desconhece que a propriedade de busca da BST permite essa ordenação com o percurso adequado.
Confunde a ordem em que a raiz é visitada: no pré-ordem a raiz vem antes das subárvores, o que não respeita a sequência esquerda-raiz-direita necessária para ordenar.
Acredita que visitar a raiz por último garante que os valores menores sejam impressos primeiro. Não considera que a raiz fica depois das subárvores, portanto antes de nós menores que ela estarem na ordem certa.
Raio-X da questão
percurso em árvore binária
avaliacao
árvores binárias · percurso em árvore
Revisar os tipos de percursos em árvores binárias.
Confundir os diferentes tipos de percurso em árvores binárias e suas respectivas ordens de visitação.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Para percorrer recursivamente uma árvore binária em um algoritmo e processar cada nó antes de seus filhos, qual percurso…
- Em uma árvore binária de busca, os valores menores que um nó ficam à esquerda, e os maiores ficam à direita. Para…
- Considere uma árvore binária. Em linguagem corrente ou pseudocódigo, descreva a ordem de visita do percurso pré-ordem…
- Em um algoritmo de busca em profundidade em uma árvore, qual é o principal fator que determina a ordem da exploração dos…
- Em um algoritmo, qual a vantagem de usar uma árvore binária para organizar dados?
- Descreva um algoritmo em pseudocódigo que, dada uma árvore enraizada onde cada nó mantém uma lista arbitrária de filhos…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog