Questão 41671

• Banca: FCC
• Órgão: TRE-PI
• Ano: 2009
• Provas: FCC - 2009 - TRE-PI - Analista Judiciário - Tecnologia da Informação - Análise de Sistemas
• Disciplina: Algoritmos e Estrutura de Dados

Uma árvore binária completa, estritamente binária, cuja raiz está no nível 0 e a altura da árvore é 5, possui uma quantidade de nós igual a

• A. 63.
• B. 62.
• C. 32.
• D. 31.
• E. 30.

Gabarito: A

Comentários

• nó 0 : 2 elv 0 = 1
  nó 1 : 2 elv 1 = 2
  nó 2 : 2 elv 2 = 4
  nó 3 : 2 elv 3 = 8
  nó 4 : 2 elv 4 = 16
  nó 5 : 2 elv 5 = 32
  Altura 5 árvore completa
  Soma : 1+2+4+8+16+32 = 63 resposta
• O nível da árvore binária equivale à sua altura e começa a contar de zero.Logo, se tem 5 de altura, conta-se de 0 a 5.Não esquecer: NIVEL = ALTURA. Inicia-se em ZERO (0).
• Para facilitar mais ainda basta usar a fórmula:2^(altura+1) - 1^ = Elevado
• Para encontrar o número de nós de uma árvore binária completa basta usar a fórmula n = 2^(h+1) - 1 onde h é altura da árvore e n o número total de nós.
• O número de nós de uma árvore completa é igual a 2^h+1-1, onde h é a altura da árvore:
  2⁵⁺¹-1 = 64-1 = 63 nós

• Lembrando que este conceito apresentado na verdade não é o de árvore completa, e sim o de árvore CHEIA. A árvore completa pode ter diferença de níveis, contanto que esteja balanceada. Já a cheia tem que ter todos as folhas no mesmo nível. A fórmula n = 2^(h+1) - 1 é para calcular arvore cheia ou então o máximo possível de uma completa.