Para resolver problemas de maneira eficiente, pode-se tentar eliminar soluções inviáveis, encurtando a resolução. A busca binária e a busca em árvore binária são dois exemplos de algoritmos que "podam" soluções errôneas, para encurtar o caminho até uma solução.
OLIVEIRA, Pietro Martins de; LEON, Rogério de. Estrutura de Dados II. Maringá-PR, Unicesumar, 2019.
Considerando uma busca em árvore binária ordenada que se inicie em 20, caso o usuário decida por buscar o valor alvo igual a 25, qual seria a ordem de visitação dos nós?
Alternativas
Alternativa 1:
20, 21, 31, 30
Alternativa 2:
20, 21, 31
Alternativa 3:
20, 3, 8, 7
Alternativa 4:
20, 21, 31, 40
Alternativa 5:
20, 21
Respostas
Resposta:
Alternativa 1:
20, 21, 31, 30
Explicação:
Dado um argumento qualquer, se ele for menor do que a raiz, ou ele não existe, ou ele se encontra na sua subárvore esquerda. Se o valor for maior do que a raiz, ou ele não existe ou está na sua subárvore direita. A partir da raiz vamos descendo pela árvore binária de busca até que o valor seja encontrado ou que encontremos uma folha ou uma subárvore vazia.
Referência, pg. 48.
Considerando uma busca em árvore binária ordenada que se inicie em 20, caso o usuário decida por buscar o valor alvo igual a 25, a ordem de visitação dos nós seria 20, 21, 31, 30. O que é mostrado na alternativa 1.
Árvore binária
Tomando como referência o número 20, observa-se 25 é maior que 20, isto implica que, deve-se caminhar para direita e passar pelo 21, seguindo para direita se terá o número 31.
Como 25 é menor do que 31, deve-se ir pára o nó da esquerda que é 30, completando assim a ordem de visitação dos nós.
Pode-se concluir que a ordem de visitação dos nós seria 20, 21, 31, 30
Saiba mais sobre árvore binária em:
brainly.com.br/tarefa/22409421
Bons estudos!
#SPJ2
20, 21, 31, 30