Uma árvore é uma estrutura de dados hierárquica e não linear, composta por um conjunto finito de elementos chamados nós. Entre esses nós, há sempre um nó especial denominado raiz, que serve como ponto de partida da estrutura.

Cada nó pode estar ligado a zero ou mais subárvores, formando uma relação de pai e filhos, em que cada filho tem exatamente um pai, mas um pai pode ter vários filhos. Essa característica torna a árvore ideal para representar relações hierárquicas, como organogramas, sistemas de arquivos, classificações e expressões matemáticas.

Na ilustração acima, temos:

• 🌼 Raiz (em amarelo): é o nó principal da árvore, de onde partem todos os demais.
• 🍃 Nós folha (em vermelho): são os nós que não possuem filhos, ou seja, representam os “fins” dos ramos.
• 🌳 Nós internos (em verde): são os nós que possuem pelo menos um filho, chamados também de pais.

Além desses conceitos básicos, é importante conhecer três propriedades fundamentais:

• Altura da árvore: é a maior distância (em número de arestas) entre a raiz e qualquer nó folha.
• Nível de um nó: representa a profundidade em que o nó se encontra, sendo a raiz o nível 0.
• Grau de um nó: indica o número de filhos que esse nó possui.

Essas propriedades são essenciais para o desempenho de operações sobre a árvore, como buscas, inserções e remoções, que variam de acordo com o tipo de árvore utilizada (binária, balanceada, AVL, B-tree, etc.).

Classificação das Árvores Binárias

As árvores binárias são estruturas de dados hierárquicas e versáteis, amplamente utilizadas em algoritmos e sistemas computacionais.
Elas podem ser classificadas em diferentes tipos, de acordo com as propriedades de seus nós e a forma como os níveis estão organizados..

1. Árvore Binária

Uma árvore binária é uma estrutura de dados hierárquica em que cada nó possui, no máximo, dois filhos, denominados:

• Filho esquerdo (Left child)
• Filho direito (Right child)

Nem todos os nós precisam ter dois filhos — alguns podem ter um ou nenhum.

💡 Usos:

Comumente utilizada em:

• Árvores de busca binária (BSTs)
• Expressões matemáticas

2. Árvore Estritamente Binária (ou Árvore Binária Própria)

Uma árvore estritamente binária (ou full binary tree) é uma árvore em que cada nó possui exatamente 0 ou 2 filhos — nunca apenas um.

Ou seja:

• Se o nó não é folha, deve ter dois filhos.
• Todos os níveis intermediários são preenchidos de forma completa.

💡 Usos:

Ideal para representar expressões lógicas e matemáticas, em que cada operação (nó interno) tem dois operandos (filhos).

🌳 3. Árvore Binária Completa

Uma árvore binária completa é uma árvore em que todos os níveis estão completamente preenchidos, exceto possivelmente o último, que é preenchido da esquerda para a direita.

Ou seja:

• Nenhum nó é “pulando posições” no último nível.
• Todos os nós do último nível ficam o mais à esquerda possível.

💡 Usos:

Muito usada em heaps binários, filas de prioridade e implementações de árvores com vetores.