Seja T uma árvore binária completa com n nós e altura h. O v...

Alternativa Correta: D - n = 2^h - 1

Vamos entender o que é uma árvore binária completa e como ela se relaciona com o tema da questão. Em estruturas de dados, uma árvore binária completa é uma árvore em que todos os níveis, exceto possivelmente o último, estão completamente preenchidos com nós. No último nível, todos os nós estão o mais à esquerda possível.

Quando falamos de uma árvore cheia, referimo-nos a um caso específico da árvore binária completa, onde todos os níveis, incluindo o último, estão completamente preenchidos. A fórmula para determinar o número de nós (n) em uma árvore cheia de altura h é dada por n = 2^h+1 - 1. Isso porque em cada nível da árvore, o número de nós dobra, começando por 1 no nível 0.

Justificativa da Alternativa Correta:

A alternativa D indica corretamente a fórmula n = 2^h - 1 para descrever uma árvore cheia. Isto está de acordo com a definição, onde, ao somar todos os nós de cada nível de uma árvore binária completa, chegamos a essa quantidade total de nós.

Análise das Alternativas Incorretas:

• A - n = 2^h: Esta fórmula indica erroneamente o número de nós até o nível h, mas não reflete uma árvore cheia, pois não considera que cada nível deve estar completamente preenchido até h.
• B - n = 2^n-1: Esta fórmula está incorreta e não segue a lógica do crescimento exponencial em uma árvore binária.
• C - n = 2^h+1: Esta fórmula duplicaria a quantidade de nós que na verdade deveria ser 2^h+1 - 1 para uma árvore cheia.
• E - n = 2^{h + 1}: Similar à alternativa C, ignora a subtração de 1 necessária para contar corretamente todos os nós até o nível h inclusive.

Compreender essas fórmulas é essencial para quem estuda Estruturas de Dados, especialmente ao lidar com árvores binárias e conceitos de cálculos de complexidade. Saber identificar corretamente a estrutura e suas propriedades é crucial para a resolução de questões em concursos públicos.

Gostou do comentário? Deixe sua avaliação aqui embaixo!

Desenhe uma árvore binária cheia com 7 nós, sendo o primeiro nó o raiz, que tem dois filhos. Cada nó filho tem outros dois filhos no limite inferior da árvore (afinal, ela é cheia). Ao desenhar essa árvore você perceberá que a altura (h) é igual a 3. Se você elevar 2^3 = 8. Se o número total de nós da árvore cheia é 7, então (2^h)-1 = 7, o que corresponde exatamente a alternativa D.

rubens, uma arvore com 7 nós teria h=2...

essa questão é passivel de anulação ao meu ver, a formula do numero de nós pela definição é: n=((2^(h+1))-1)

Existem autores que considerama raiz como nível 0 e autores que consideram com nível 1.

Logo, existem duas possibilidade de achar a altura da arvore

h = (2^n) - 1

h = (2^n) - 2

como o gabarito não apresenta outra alternativa que poderia levar o candidato a ter dúvida a questão não é passível de anulação