Escreva sua definição dos seguintes conceitos abaixo:
Árvore binária completa

Passo 1

O enunciado pede a definição de “árvore binária completa”, que é um conceito de estruturas de dados, mais especificamente de árvores binárias.

Passo 2

Começamos lembrando que uma árvore binária é uma estrutura que consiste em nós, em que cada nó tem no máximo dois filhos, chamados de filho esquerdo e filho direito.
Definimos o nível de um nó como a sua distância em arestas até a raiz, sendo que a raiz está em nível 0 e seus filhos em nível 1, e assim por diante.

Passo 3

Uma árvore binária é dita completa se satisfaz duas condições simultâneas:
  1. Todos os níveis de 0 até o penúltimo h-1, onde h é a altura da árvore) estão completamente preenchidos (ou seja, têm 2^i nós no nível i.
  2. No último nível h, todos os nós estão “empurrados” para a esquerda, sem lacunas entre eles.
    Em outras palavras, numa árvore binária completa não pode haver um nó vazio à esquerda de um nó existente no mesmo nível, e todos os níveis anteriores devem estar cheios.

Resposta

Uma árvore binária completa é aquela em que todos os níveis, exceto possivelmente o último, estão totalmente preenchidos e, no último nível, os nós aparecem da esquerda para a direita sem lacunas.

Exercícios relacionados