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:

Esquerdo = 2 x P + 1   |   Direito = 2 x P + 2

Answer 2

Resposta:

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

Explicação:

O NÓ 1 COMEÇA NO ÍNDICE 0 ENTÃO  (2 Fe 2*0+1 = 1)

(3 Fd 2*0+2 = 3)  - (4 é Fe do nó 2 então 2*1+1=3)  

a formula:

Fe= 2*P+1  VAI SER DUAS VEZES A POSIÇÃO DO PAI NO VETOR + 1

Fd= 2*P+2 DUAS VEZES A POSIÇÃO DO PAI NO VETOR + 2