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 é 2^eu.
• 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 é (2⁰+ 2¹+ 2²+….2^h) = 2^h+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 = 2^h+1-1

n+1 = 2^h+1

Pegando toras de ambos os lados,

registro₂(n+1) = log2(2^h+1)

registro₂(n+1) =h+1

h = registro₂(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:

Árvore binária completa/adequada/estrita Árvore binária completa Árvore binária perfeita Árvore binária degenerada Árvore binária balanceada

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, 2^h+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 é registro₂(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 é 2^h+1- 1.
• O número mínimo de nós na árvore binária completa é 2^h.
• A altura mínima de uma árvore binária completa é registro₂(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