Questão FC266065
Considere que as chaves 33, 15, 41, 38, 34, 47, 49 e 43 foram inseridas, nessa ordem, em uma árvore binária de busca. Assinale a alternativa que contém o percurso em pré-ordem da á
Algoritmos e Lógica de Programação
IDECAN · 2019
Considere que as chaves 33, 15, 41, 38, 34, 47, 49 e 43 foram inseridas, nessa ordem, em uma árvore binária de busca.
Assinale a alternativa que contém o percurso em pré-ordem da árvore binária de busca criada.
- 15, 33, 34, 38, 41, 43, 47, 49
- 33, 15, 41, 38, 34, 47, 43, 49
- 15, 34, 38, 43, 49, 47, 41, 33
- 33, 41, 47, 49, 43, 38, 34, 15
- 33, 15, 41, 34, 38, 43, 47, 49
Mostrar resposta e comentário
Gabarito
B
Comentário do professor
Ao inserir as chaves na ordem dada, o primeiro elemento, 33, torna-se a raiz. Pela regra da árvore binária de busca, valores menores vão para a esquerda e maiores para a direita.
A árvore final fica, em termos de posição: raiz 33; à esquerda 15; à direita 41. Em 41: à esquerda 38 (que tem à esquerda 34) e à direita 47 (que tem à esquerda 43 e à direita 49).
O percurso em pré-ordem visita primeiro a raiz da subárvore, depois recursivamente a subárvore da esquerda e, por fim, a da direita. Aplicando isso:
Visita 33 (raiz), depois 15 (subárvore esquerda), depois a subárvore direita começando em 41 → 38 → 34, e então 47 → 43 → 49.
Assim obtém-se a sequência: 33, 15, 41, 38, 34, 47, 43, 49, correspondente à alternativa correta.
Conteúdo do catálogo FC Concursos · Atualizado em