A árvore binária significa que o nó pode ter no máximo dois filhos. Aqui, o próprio nome binário sugere que 'dois'; portanto, cada nó pode ter 0, 1 ou 2 filhos.
Vamos entender a árvore binária através de um exemplo.
strings para inteiros
A árvore acima é uma árvore binária porque cada nó contém no máximo dois filhos. A representação lógica da árvore acima é fornecida abaixo:
Na árvore acima, o nó 1 contém dois ponteiros, ou seja, um ponteiro esquerdo e um ponteiro direito apontando para o nó esquerdo e direito, respectivamente. O nó 2 contém ambos os nós (nó esquerdo e direito); portanto, possui dois ponteiros (esquerdo e direito). Os nós 3, 5 e 6 são nós folha, portanto todos esses nós contêm NULO ponteiro nas partes esquerda e direita.
Propriedades da árvore binária
- Em cada nível de i, o número máximo de nós é 2eu.
- A altura da árvore é definida como o caminho mais longo do nó raiz até o nó folha. A árvore mostrada acima tem altura igual a 3. Portanto, o número máximo de nós na altura 3 é igual a (1+2+4+8) = 15. Em geral, o número máximo de nós possíveis na altura h é (20+ 21+ 22+….2h) = 2h+1-1.
- O número mínimo de nós possíveis na altura h é igual a h+1 .
- Se o número de nós for mínimo, a altura da árvore será máxima. Por outro lado, se o número de nós for máximo, a altura da árvore será mínima.
Se houver 'n' número de nós na árvore binária.
A altura mínima pode ser calculada como:
Como sabemos disso,
n = 2h+1-1
n+1 = 2h+1
Pegando toras de ambos os lados,
registro2(n+1) = log2(2h+1)
registro2(n+1) =h+1
h = registro2(n+1) - 1
A altura máxima pode ser calculada como:
Como sabemos disso,
n =h+1
h = n-1
Tipos de árvore binária
Existem quatro tipos de árvore binária:
1. Árvore binária completa/adequada/estrita
A árvore binária completa também é conhecida como árvore binária estrita. A árvore só pode ser considerada uma árvore binária completa se cada nó contiver 0 ou 2 filhos. A árvore binária completa também pode ser definida como a árvore em que cada nó deve conter 2 filhos, exceto os nós folha.
Vejamos o exemplo simples da árvore Full Binary.
Na árvore acima, podemos observar que cada nó contém zero ou dois filhos; portanto, é uma árvore binária completa.
Propriedades da árvore binária completa
- O número de nós folha é igual ao número de nós internos mais 1. No exemplo acima, o número de nós internos é 5; portanto, o número de nós folha é igual a 6.
- O número máximo de nós é igual ao número de nós na árvore binária, ou seja, 2h+1-1.
- O número mínimo de nós na árvore binária completa é 2*h-1.
- A altura mínima da árvore binária completa é registro2(n+1) - 1.
- A altura máxima da árvore binária completa pode ser calculada como:
n= 2*h - 1
n+1 = 2*h
h = n+1/2
Árvore binária completa
A árvore binária completa é uma árvore na qual todos os nós estão completamente preenchidos, exceto o último nível. No último nível, todos os nós devem estar o mais à esquerda possível. Em uma árvore binária completa, os nós devem ser adicionados a partir da esquerda.
Vamos criar uma árvore binária completa.
como converter int em string
A árvore acima é uma árvore binária completa porque todos os nós estão completamente preenchidos e todos os nós no último nível são adicionados primeiro à esquerda.
Propriedades da árvore binária completa
- O número máximo de nós na árvore binária completa é 2h+1- 1.
- O número mínimo de nós na árvore binária completa é 2h.
- A altura mínima de uma árvore binária completa é registro2(n+1) - 1.
- A altura máxima de uma árvore binária completa é
Árvore Binária Perfeita
Uma árvore é uma árvore binária perfeita se todos os nós internos tiverem 2 filhos e todos os nós folhas estiverem no mesmo nível.
Vejamos um exemplo simples de uma árvore binária perfeita.
A árvore abaixo não é uma árvore binária perfeita porque todos os nós folhas não estão no mesmo nível.
Nota: Todas as árvores binárias perfeitas são árvores binárias completas e também árvores binárias completas, mas vice-versa não é verdade, ou seja, todas as árvores binárias completas e árvores binárias completas são árvores binárias perfeitas.
Árvore binária degenerada
A árvore binária degenerada é uma árvore na qual todos os nós internos possuem apenas um filho.
Vamos entender a árvore binária Degenerada através de exemplos.
A árvore acima é uma árvore binária degenerada porque todos os nós têm apenas um filho. Também é conhecida como árvore inclinada à direita, pois todos os nós têm apenas um filho certo.
contém método java
A árvore acima também é uma árvore binária degenerada porque todos os nós têm apenas um filho. Também é conhecida como árvore inclinada à esquerda, pois todos os nós têm apenas um filho esquerdo.
Árvore binária balanceada
A árvore binária balanceada é uma árvore na qual as árvores esquerda e direita diferem em no máximo 1. Por exemplo, AVL e Árvores Rubro-Negras são árvores binárias balanceadas.
Vamos entender a árvore binária balanceada através de exemplos.
A árvore acima é uma árvore binária balanceada porque a diferença entre a subárvore esquerda e a subárvore direita é zero.
A árvore acima não é uma árvore binária balanceada porque a diferença entre a subárvore esquerda e a subárvore direita é maior que 1.
Implementação de árvore binária
Uma árvore binária é implementada com a ajuda de ponteiros. O primeiro nó da árvore é representado pelo ponteiro raiz. Cada nó da árvore consiste em três partes, ou seja, dados, ponteiro esquerdo e ponteiro direito. Para criar uma árvore binária, primeiro precisamos criar o nó. Criaremos o nó definido pelo usuário conforme mostrado abaixo:
struct node { int data, struct node *left, *right; } Na estrutura acima, dados é o valor, ponteiro esquerdo contém o endereço do nó esquerdo e ponteiro direito contém o endereço do nó certo.
Programa de árvore binária em C
#include struct node { int data; struct node *left, *right; } void main() { struct node *root; root = create(); } struct node *create() { struct node *temp; int data; temp = (struct node *)malloc(sizeof(struct node)); printf('Press 0 to exit'); printf('
Press 1 for new node'); printf('Enter your choice : '); scanf('%d', &choice); if(choice==0) { return 0; } else { printf('Enter the data:'); scanf('%d', &data); temp->data = data; printf('Enter the left child of %d', data); temp->left = create(); printf('Enter the right child of %d', data); temp->right = create(); return temp; } } O código acima chama a função create() recursivamente e cria um novo nó em cada chamada recursiva. Quando todos os nós são criados, ele forma uma estrutura de árvore binária. O processo de visitar os nós é conhecido como travessia de árvore. Existem três tipos de travessias usadas para visitar um nó:
- Travessia em ordem
- Passagem de pré-encomenda
- Travessia de vale postal