Hoje vou falar um pouco sobre árvores binárias. Que são estruturas de dados bem interessantes para vários casos reais de desenvolvimento de software.

Uma árvore binária é uma estrutura de dados que é capaz de agrupar informações em formato de árvore, na verdade uma árvore binária é bem parecida com um grafo, mas com a ressalva de que ela possui apenas cada nó com apenas dois filhos e um ponto que é pai de todos os outros indiretamente, que é chamado de raiz.

Podemos usar árvores para diversas situações, desde sistema para cálculos de probabilidade de vitórias em campeonatos de futebol, até sistema de listagem de dados dinamicamente agrupados a partir de opções vindas do usuário.

Em uma árvore binária encontramos alguns nomes específicos para classificar alguns tipos características e informações, veremos algumas das principais delas.

Nó = é um dado armazenado em uma árvore binária, é de um tipo específico ao qual a árvore está preparada para armazenar, uma árvore é um container para N nós semelhantes em sua estrutura.

Raiz = é o primeiro item de uma árvore binária, ele começa uma estrutura que se repete da seguinte forma: cada item tem 0, 1 ou 2 itens relacionados à eles, dessa forma a raiz é denominada pai e os itens relacionados são os seus filhos. Cada filho pode ter outros filhos, até o final da árvore.

Subárvores = são partes da árvore principal que usam como raiz qualquer nó que não seja a raiz inicial e criam outras árvores menores, são árvores sempre menores que a árvore principal e que tem as mesmas características estruturais dessa árvore, dessa forma é fácil entender que uma árvore binária é a soma de todos os nos da subárvore com a raiz sendo o seu filho esquerdo e a subárvore com a raiz sendo o seu filho direito. 

Folha = é um nó que não possui filhos.

Altura de um nó = a quantidade de pais que é necessária para se chegar até a raiz é a altura desse nó, por exemplo se tivermos uma árvore com uma configuração dessa forma: A tem B e C como filhos, B tem X e Y como filhos, teríamos o seguinte: A tem altura 0, B e C, 1 e X e Y, com altura 2.

Grau de um nó = é semelhante a altura mas sendo que é a contagem inversa. Ao invés de a quantidade de pais até a raiz, a contagem se baseia pela quantidade de filhos até a folha mais longe. No exemplo acima, teríamos: A com grau 2, B e C com grau 1 e X e Y com grau 0.

Árvores binárias completas = são árvores binárias onde cada nó que não é folha possui exatos dois filhos.

Percursos = são os algoritmos (normalmente algoritmos recursivos) que passam por todos os nós da árvore, existem 3 percursos recursivos principais: em ordem (simétrica), pré-ordem e pós-ordem. Suas estruturas de recursão são bem parecidas, se diferenciam apenas na ordem de acesso aos nós.

As árvores binárias, tem de serem bem úteis praticamente falando,  têm propriedades matemáticas que a fazem assunto para muitos livros e publicações acadêmicas completas. No próximo artigo mostrarei algumas aplicações práticas e algumas otimizações nessas estruturas de dados.