Escreva sua definição dos seguintes conceitos abaixo:
Árvore binária completa
Á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 e seus filhos em nível
, e assim por diante.
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
Passo 3
Uma árvore binária é dita completa se satisfaz duas condições simultâneas:
- Todos os níveis de
até o penúltimo , onde é a altura da árvore) estão completamente preenchidos (ou seja, têm nós no nível . - No último nível
, 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.