Question

Rafael decidiu fazer um programa para cadastrar todos os seus jogos de X-Box One, para ele poder emprestar os jogos para os seus amigos, sem correr o risco de esquecer quem está com determinado jogo, quando foi emprestado, quando será devolvido, etc. Para agilizar a busca, ele decidiu organizar seus jogos no formato de uma árvore binária e fazer a implementação em um vetor.

Considere que, no vetor abaixo, o primeiro elemento é a raiz da árvore e cada elemento está posicionado no vetor a partir das seguintes regras:


Filho Esquerdo = 2 * P + 1
Filho Direito = 2 * P + 2

Considere também que P é a posição do Pai e a primeira posição do vetor tem o índice 0.
Preencha o vetor correspondente à árvore binária abaixo, colocando “V” nas posições em que a árvore não tem nenhum nó.

Answer 1

Resposta:

1 - 2 - 3 - 4 - V - 5 - 6 - 7 - 8 - V - V - V - 9 - V - 0

Explicação:

Fórmula:

2 x (Posição do pai na memória) + 1 se for adicionar a esquerda ou + 2 se for adicionar a direita.