GabaritoD — n =2h -1
Gabarito: letra D. Uma árvore binária cheia (full binary tree) de altura (h) (medida como número de níveis, com a raiz no nível 1) possui exatamente (n = 2^h - 1) nós, pois todos os níveis estão completamente preenchidos. Por exemplo, uma árvore de altura 1 tem 1 nó ((2^1 - 1 = 1)); altura 2 tem 3 nós ((2^2 - 1 = 3)); altura 3 tem 7 nós, e assim por diante.
(n = 2h) é uma relação linear, enquanto o número de nós em uma árvore cheia cresce exponencialmente com a altura.
A expressão (n = 2n^{-1}) está malformada (provavelmente um erro de digitação na questão). De qualquer forma, não corresponde à fórmula correta.
(n = 2h + 1) também é linear, não reflete o crescimento exponencial.
(n = 2^h - 1) é a relação exata para uma árvore binária cheia.
(n = 2^h + 1) acrescenta uma unidade a mais; para uma árvore cheia o número de nós é uma unidade a menos que a potência de 2.
Memorize a fórmula (n = 2^h - 1) para árvore binária cheia (full) e (n = 2^{h+1} - 1) quando a altura é contada como número de arestas. Nas provas, verifique como a altura é definida (níveis ou arestas).
Gabarito: letra D.
Link permanente: /questoes/fg089771