Uma das características mais interessantes de vetores estáticos é que podemos utilizar formulas matemáticas para acessar as posições do respectivo vetor como se ele fosse uma árvore binária.
OLIVEIRA, Pietro Martins de; LEON, Rogério de. Estrutura de Dados II. Maringá-PR, Unicesumar, 2019.
A árvore representada na ilustração acima pode ser representada de acordo com o seguinte vetor estático:
Assim sendo, se inseríssemos um novo nó G à direita do nó D, em qual posição do vetor o novo nó G se encontraria?
Alternativas
Alternativa 1:
15
Alternativa 2:
6
Alternativa 3:
9
Alternativa 4:
8
Alternativa 5:
11
Respostas
Resposta:
Alternativa 4: 8
Explicação:
O nó C é uma folha, podemos dizer que ele não tem filhos ou que seus filhos
são árvores vazias. Como o nosso objetivo é manter o vetor ordenado, a posição dos filhos de C será reservada
Os espaços 7 e 8 são reservados para os filhos de D.
Ficando assim, o G no espaço 8.
Livro página 27
Resposta:
Alternativa 4: 8
Explicação:
Para facilitar as buscas em árvores binárias os nós precisam estar indexados. Considerando que uma árvore binária cresce de forma geométrica posto que cada nó tem dois filhos, que por sua vez, são duas subárvores que podem estar vazias ou não. Independente de o filho existir, seu espaço precisa ser reservado no vetor (NULL).
Como todo nó em uma árvore binária tem dois filhos, a fórmula 2*p+1 é a posição do nó à esquerda do nó pai e 2*p+2 é a posição do nó à direita do nó pai, onde p é o índice do nó pai.
Sendo assim, para sabermos a posição do nó G que será inserido à direita do nó D que está na posição 3, fazemos:
Posição de G = 2*3+2 = 8