Arvore binaria

Arvore Binária
A arvore binária é uma arvore cujo nós tem dois filhos, ou seja, duas outras sub –arvores, esses filhos podem ser vazios ou não e cada filho é designado filho a esquerda e filho a direita, uma arvore binária pode ser completa e incompleta.

Figura 1 Exemplo de arvore binária incompleta.
Uma arvore binária completa é aquela que cada nó possui exatamente dois filhos e que as folhas estão exatamente no mesmo nível. Se uma arvore binária é completa a raiz está no nível 1 e seus filhos não – vazios estão no nível dois e assim por diante, observando esse fato a quantidade de nós nesse tipo de arvore pode ser determinado pela fórmula 2i onde i é o nível superior do nó, por exemplo se o nó está no nível 1 tem-se 20 = 1 nó se tiver no nível 2 será 21 = 2 nós e assim por diante.
Este tipo de arvore pode acelerar o processo de pesquisa pois o processo pode ser reduzido.
Implementando as Arvores Binárias.
As arvores binárias podem ser implementadas pelo menos de duas maneiras: como matrizes e como estruturas ligadas. Para implementar uma arvore como matriz o nó é declarado como uma estrutura que possui 3 campos 1 de informação e outros dois de referência (ponteiro). Esses ponteiros guardam os índices da matriz no qual os filhos à esquerda e a direita são armazenados.
Esse tipo de implementação pode às vezes se tornar um problema, pois o tamanho da matriz teria que ser determinado no programa com isso os dados poderiam transbordar se pouco espaço é determinado ou poderia ser um desperdício de memória se for determinado muito espaço. Por outro lado às vezes esse tipo de implementação pode ser bem vindo por ser de fácil entendimento.
Para implementar como estrutura ligada segue-se o conceito de alocação dinâmica, funciona como uma lista duplamente encadeada, cujo o qual também possui 3 campos 1 de informação e os outros dois de ponteiro, onde cada ponteiro aponta para o endereço de memória dos filhos a esquerda e a direita, se não tiver filhos