Diferença entre a árvore binária completa e a árvore binária completa

Árvore binária completa vs Árvore binária completa

Árvore binária é uma árvore em que cada nó tem um ou dois filhos. Em uma árvore binária, um nó não pode ter mais de dois filhos. Em uma árvore binária, os filhos são nomeados como filhos "esquerdo" e "direito". Os nós filhos contêm uma referência ao pai. Uma árvore binária completa é uma árvore binária na qual todos os níveis da árvore binária são completamente preenchidos, exceto o último nível. No nível não preenchido, os nós são anexados a partir da posição mais à esquerda. Uma árvore binária completa é uma árvore na qual todos os nós da árvore têm dois filhos, exceto as folhas da árvore..

O que é a árvore binária completa?

Árvore binária completa é uma árvore binária na qual todos os nós da árvore têm exatamente zero ou dois filhos. Em outras palavras, todos os nós da árvore, exceto as folhas, têm exatamente dois filhos. A Figura 1 abaixo mostra uma árvore binária completa. Em uma árvore binária completa, o número de nós (n), o número de laves (l) e o número de nós internos (i) é relacionado de uma maneira especial, de modo que, se você conhece algum deles, pode determinar os outros dois valores da seguinte maneira:

1. Se uma árvore binária completa possui i nós internos:

- Número de folhas l = i + 1

- Número total de nós n = 2 * i + 1

2. Se uma árvore binária completa tiver nós:

- Número de nós internos i = (n-1) / 2

- Número de folhas l = (n + 1) / 2

3. Se uma árvore binária completa tiver l folhas:

- Número total de nós n = 2 * l-1

- Número de nós internos i = l-1

O que é a árvore binária completa?

Como mostra a figura 2, uma árvore binária completa é uma árvore binária na qual todos os níveis da árvore são completamente preenchidos, exceto o último nível. Além disso, no último nível, os nós devem ser conectados a partir da posição mais à esquerda. Uma árvore binária completa de altura h satisfaz as seguintes condições:

- No nó raiz, o nível acima do último nível representa uma árvore binária completa de altura h-1

- Um ou mais nós no último nível podem ter 0 ou 1 filho

- Se a, b são dois nós no nível acima do último nível, então a tem mais filhos que b se e somente se a estiver situado à esquerda de b

Qual é a diferença entre Árvore Binária Completa e Árvore Binária Completa?

Árvores binárias completas e árvores binárias completas têm uma diferença clara. Enquanto uma árvore binária completa é uma árvore binária na qual todo nó tem zero ou dois filhos, uma árvore binária completa é uma árvore binária na qual todos os níveis da árvore binária são completamente preenchidos, exceto o último nível. Algumas estruturas de dados especiais, como heaps, precisam ser árvores binárias completas, enquanto não precisam ser árvores binárias completas. Em uma árvore binária completa, se você souber o número total de nós ou o número de laves ou o número de nós internos, poderá encontrar os outros dois com muita facilidade. Mas uma árvore binária completa não possui uma propriedade especial relacionando esses três atributos.