Em uma árvore binária de busca, os valores menores que um nó ficam à esquerda, e os maiores ficam à direita…

Questão

Em uma árvore binária de busca, os valores menores que um nó ficam à esquerda, e os maiores ficam à direita. Para encontrar um valor, é preciso comparar o valor procurado com os nós visitados. A busca termina quando o valor é encontrado ou quando o próximo nó é NULL. Qual sequência de passos apresenta corretamente uma busca por um valor em uma árvore binária de busca?

1. A) Começar pela raiz; visitar primeiro todos os nós da esquerda; depois visitar todos os nós da direita; parar ao encontrar o valor ou chegar a NULL.
2. B) Começar pela raiz; comparar o valor procurado com o nó; ir para a esquerda se for menor, ou para a direita se for maior; repetir até encontrar o valor ou chegar a NULL.
3. C) Começar pela raiz; comparar o valor procurado com o nó; ir para a direita se for menor, ou para a esquerda se for maior; repetir até encontrar o valor ou chegar a NULL.
4. D) Começar pela raiz; comparar o valor procurado com o nó; declarar que não foi encontrado quando os valores forem diferentes; encerrar a busca.
5. E) Começar por uma folha; comparar o valor procurado com o nó; seguir para a esquerda ou para a direita; repetir até encontrar o valor ou chegar a NULL.

✅ Resposta correta: alternativa B

Resolução passo a passo

1. Na árvore binária de busca, a propriedade é que valores menores ficam à esquerda de um nó e valores maiores ficam à direita. Portanto, a busca precisa usar essa propriedade para descartar metade da árvore a cada comparação.
2. O procedimento correto começa pela raiz, pois ela é o primeiro nó visitado. Em seguida, compara-se o valor procurado com o valor do nó atual.
3. Se o valor procurado for menor que o nó, a busca continua na subárvore da esquerda; se for maior, continua na subárvore da direita. Se for igual, o valor foi encontrado.
4. O processo se repete a partir do novo nó até encontrar o valor ou até que o próximo nó seja NULL, o que indica que o valor não está na árvore. Essa é exatamente a sequência descrita na alternativa B, que é a correta.
5. A alternativa A está errada, pois visitar todos os nós da esquerda e depois todos os da direita é uma travessia completa, ineficiente e que ignora a propriedade de ordenação. A alternativa C está errada porque inverte as direções: valores menores devem ir para a esquerda, não para a direita. A alternativa D está errada porque declara 'não encontrado' ao primeiro valor diferente, sem seguir a árvore. A alternativa E está errada porque a busca começa pela raiz, não por uma folha.

💡 Dica: Liste os passos para a busca em árvore binária.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Em uma árvore binária de busca (BST), qual percurso produz os valores dos nós em ordem crescente de chave?
• Para percorrer recursivamente uma árvore binária em um algoritmo e processar cada nó antes de seus filhos, qual percurso…
• Durante um experimento de programação, em um laboratório de informática, observa-se o funcionamento de um algoritmo de…
• O que caracteriza um algoritmo de busca binária?
• Durante uma atividade de observação, analise um algoritmo de busca linear aplicado à lista [3, 7, 2, 9] para encontrar o…
• Considere uma árvore binária. Em linguagem corrente ou pseudocódigo, descreva a ordem de visita do percurso pré-ordem…

Todas as questões de Programação - Linguagem de programação