Qual o número máximo de folhas em uma arvore estritamente binária com altura h? Justifique sua resposta.

Passo 1

O enunciado pede o máximo de folhas que uma árvore estritamente binária pode ter, em função da sua altura h. Aqui “árvore estritamente binária” significa que todo nó interno tem exatamente dois filhos, e a altura h é o número máximo de arestas num caminho da raiz até alguma folha. Vamos usar raciocínio por indução (ou o fato de que cada nível duplica o número de nós) para obter o resultado.

Passo 2

Para h=0 a árvore consiste apenas da raiz, que é também folha. Logo o número máximo de folhas é
2^{0}=1,
o que confere com as possibilidades de uma árvore sem arestas.

Passo 3

Suponha que em toda árvore estritamente binária de altura h-1 o máximo de folhas seja 2^{h-1}. Considere agora uma árvore de altura h. A raiz tem dois subárvores, cada uma de altura no máximo h-1. Pelo passo de indução, cada subárvore pode ter no máximo 2^{h-1} folhas, e como são disjuntas, o total de folhas é
2^{h-1} + 2^{h-1} = 2\cdot 2^{h-1} = 2^{h}.

Resposta

O número máximo de folhas em uma árvore estritamente binária de altura h é 2^{h}.

Exercícios relacionados