O que é uma árvore binária completa?
Uma árvore binária completa pode ser definida como um árvore binária em que todos os nós têm 0 ou dois filhos. Em outras palavras, a árvore binária completa pode ser definida como uma árvore binária na qual todos os nós têm dois filhos, exceto os nós folha.
A árvore abaixo é uma árvore binária completa:
função de substring java
A árvore acima é uma árvore binária completa, pois todos os nós, exceto os nós folha, têm dois filhos.
Teorema da árvore binária completa:
Considere uma árvore binária T como uma árvore não vazia então:
- Sejam I nós internos em uma árvore e L um nó folha em uma árvore, então o número de nós folha seria igual a:
eu = eu + 1 - Se T tiver I número de nós internos e N for o número total de nós, então o número total de nós seria igual a:
N = 2I + 1 - Se T contiver 'N' o número total de nós e 'I' for o número de nós internos, então o número de nós internos seria igual a:
Eu = (N-1)/2 - Se 'T' tiver 'N' número total de nós e 'L' for um número de nós folha, então o número de nós folha seria igual a:
L = (N+1)/2 - Se 'T' contiver um número 'L' de nós folha, então o número total de nós seria igual a:
N = 2L - 1 - Se 'T' tiver um número 'L' de nós folha e 'I' for um número de nós internos, então o número de nós internos seria igual a:
eu = eu - 1
O que é uma árvore binária completa?
Uma árvore binária é considerada uma árvore binária completa quando todos os níveis estão completamente preenchidos, exceto o último nível, que é preenchido a partir da esquerda.
A árvore abaixo é uma árvore binária completa:
A árvore binária completa é semelhante à árvore binária completa, exceto pelas duas diferenças fornecidas abaixo:
- O preenchimento do nó folha deve começar pelo lado esquerdo.
- Não é obrigatório que o último nó folha tenha o irmão correto.
Vamos entender os pontos acima através de um exemplo:
Considere a árvore abaixo:
A árvore acima é uma árvore binária completa, mas não uma árvore binária completa, pois o nó 6 não tem seu irmão direito.
Criação de árvore binária completa
Suponha que temos um array de 6 elementos mostrado abaixo:
A matriz acima contém 6 elementos, ou seja, 1, 2, 3, 4, 5, 6. A seguir estão as etapas a serem usadas para criar uma árvore binária completa:
Passo 1: Primeiro, selecionaremos o primeiro elemento do array, ou seja, 1, e faremos um nó raiz da árvore. O número de elementos disponíveis no primeiro nível é 1.
Passo 2: Agora, selecionaremos o segundo e o terceiro elementos do array. Mantenha o segundo elemento e o terceiro elemento da matriz como os filhos esquerdo e direito do nó raiz, respectivamente, mostrados abaixo:
Como podemos observar acima que o número de elementos disponíveis no segundo nível é 2.
Etapa 3: Agora, selecionaremos os próximos dois elementos do array, ou seja, 4 e 5. Mantenha esses dois elementos à esquerda e à direita do nó 2 mostrado abaixo:
Como podemos observar acima, os nós 4 e 5 são filhos esquerdo e direito do nó 2, respectivamente.
Passo 4: Agora, selecionaremos o último elemento do array, ou seja, 6, e mantê-lo-emos como filho esquerdo do nó 3, pois sabemos que em uma árvore binária completa, os nós são preenchidos do lado esquerdo mostrado abaixo:
Como podemos observar que o segundo nível contém 3 elementos.
Vamos entender as diferenças entre a árvore binária completa e completa através das imagens.
string para caractere java
- A árvore binária mostrada abaixo não é uma árvore binária completa nem completa. Não é uma árvore binária completa porque o nó 3 possui apenas um filho. Também não é uma árvore binária completa, pois os nós devem ser preenchidos do lado esquerdo, mas o nó 3 tem um filho direito e não tem um filho esquerdo.
- A árvore binária mostrada abaixo é uma árvore binária completa, mas não uma árvore binária completa. É uma árvore binária completa porque todos os nós têm 0 ou 2 filhos. Não é uma árvore binária completa porque o nó 3 não tem filhos enquanto o nó 2 tem seus filhos e sabemos que os nós devem ser preenchidos do lado esquerdo em uma árvore binária completa.
- A árvore binária mostrada abaixo é uma árvore binária completa, mas não uma árvore binária completa. É uma árvore binária completa, pois todos os nós ficam preenchidos. Não é uma árvore binária completa, pois o nó 2 possui apenas um filho.
- A árvore binária mostrada abaixo é uma árvore binária completa e completa. É uma árvore binária completa, pois todos os nós ficam preenchidos. É uma árvore binária completa, pois todos os nós têm 0 ou 2 filhos.
