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

Árvore Binária Completa vs Árvore Binária Completa

Árvore binária é uma árvore onde cada nó possui um ou dois filhos. Em uma árvore binária, um nó não pode ter mais de dois filhos. Em uma árvore binária, as crianças são nomeadas como crianças "à esquerda" e "direita". Os nós secundários contêm uma referência para seus pais. Uma árvore binária completa é uma árvore binária em que cada nível da árvore binária está completamente preenchido, 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 em que cada nó na árvore tem dois filhos, exceto as folhas da árvore.

O que é Árvore Binária Completa?

Árvore binária completa é uma árvore binária na qual cada nó na árvore tem exatamente zero ou dois filhos. Em outras palavras, cada nó na árvore, exceto as folhas, tem 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 laudos (l) eo número de nós internos (i) estão relacionados de forma especial, de modo que, se você conhece algum deles, você pode determinar os outros dois valores da seguinte forma:

1. Se uma árvore binária completa tiver 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 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:

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

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

O que é árvore binária completa?

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

- Do 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 crianças

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

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

Árvores binárias completas e árvores binárias completas têm uma clara diferença. Enquanto uma árvore binária completa é uma árvore binária em que cada nó tem zero ou dois filhos, uma árvore binária completa é uma árvore binária em que cada nível da árvore binária está completamente preenchido, exceto o último nível. Algumas estruturas de dados especiais, como montes, precisam ser árvores binárias completas, enquanto elas não precisam ser árvores binárias completas. Em uma árvore binária completa, se você conhece o número de nós totais ou o número de laudos ou o número de nós internos, você pode encontrar os outros dois com muita facilidade.Mas uma árvore binária completa não possui uma propriedade especial relacionada com esses três atributos.