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

• Pesquisadores acompanham há três anos o avanço de resíduos flutuantes em um trecho de rio urbano. Em uma simulação para…
• — O caminhão não pode ir a uma rua em dia errado — explicou a agente de limpeza durante a reunião do bairro. O município…
• — Nem toda travessia precisa emitir som ao mesmo tempo — explicou a técnica responsável pelos sinais acessíveis da…
• Na porta de um centro comunitário, voluntários recebem pedidos de doação e querem reduzir erros na hora de separar e…
• Em pseudocódigo, para um loop 'enquanto' que percorre índices i iniciando em 1 para acessar lista[1..n], qual condição…
• Projete em pseudocódigo um algoritmo que valide a força de uma senha recebida como dado: a senha deve ter pelo menos 8…

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