Este guia explora os conceitos e implementações de árvores binárias, um tópico fundamental em estruturas de dados e algoritmos, especialmente relevante no contexto de Big Data. Abordaremos desde os fundamentos teóricos até exemplos práticos de código.

1. Conceitos Fundamentais de Árvores

Antes de nos aprofundarmos em árvores binárias, é essencial entender o conceito geral de árvores em ciência da computação. Uma árvore é uma estrutura de dados não linear composta por um conjunto de nós interconectados, organizados hierarquicamente.

• Nó Raiz: O nó superior da árvore, sem antecessores.
• Subárvores: A partir de um nó, os nós descendentes formam subárvores.
• Grau de um Nó: O número de subárvores (ou filhos) que um nó possui.
• Nó Folha (Terminal): Um nó com grau zero.
• Nó Interno (Não Terminal): Um nó com grau maior que zero.
• Nó Pai: O nó imediatamente superior a um determinado nó.
• Nó Filho: Os nós diretamente descendentes de um nó.
• Nós Irmãos: Nós que compartilham o mesmo nó pai.
• Grau da Árvore: O maior grau entre todos os nós da árvore.
• Nível de um Nó: A distância do nó raiz, onde a raiz está no nível 1.
• Altura da Árvore: O nível máximo de qualquer nó na árvore.
• Ancestrais: Todos os nós no caminho da raiz até um nó específico.
• Descendentes: Todos os nós em uma subárvore com um nó específico como raiz.
• Floresta: Um conjunto de árvores disjuntas.

Uma estrutura é considerada uma árvore se:

• As subárvores são disjuntas.
• Cada nó, exceto a raiz, possui exatamente um pai.
• Uma árvore com N nós possui N-1 arestas.

2. Conceitos e Estrutura de Árvores Binárias

2.1. Definição de Árvore Binária

Uma árvore binária é uma coleção finita de nós que é ou vazia, ou consiste em um nó raiz e duas subárvores binárias: a subárvore esquerda e a subárvore direita.

2.2. Características das Árvores Binárias

• Cada nó pode ter no máximo duas subárvores (esquerda e direita).
• A ordem das subárvores (esquerda e direita) é importante e não pode ser invertida.

2.3. Tipos Especiais de Árvores Binárias

• Árvore Binária Completa (Full Binary Tree): Uma árvore binária onde cada nó tem 0 ou 2 filhos. Alternativamente, todos os nós em cada nível estão preenchidos, exceto possivelmente o último nível, que é preenchido da esquerda para a direita.
• Árvore Binária Perfeita: Uma árvore binária onde todos os nós internos têm dois filhos e todas as folhas estão no mesmo nível.
• Árvore Binária Cheia: Uma árvore onde todos os níveis estão completamente preenchidos, exceto possivelmente o último, que está preenchido da esquerda para a direita.

3. Implementação de Árvores Binárias

3.1. Estruturas de Armazenamento

Árvores binárias podem ser armazenadas de duas maneiras principais:

• Estrutura Sequencial (Array): Geralmente utilizada para representar árvores binárias completas de forma eficiente, como em heaps. A indexação do array permite calcular facilmente as posições dos pais e filhos.
• Estrutura Encadeada (Linked List): Cada nó contém dados e ponteiros para seus filhos esquerdo e direito. Esta é a abordagem mais flexível e comum para representar árvores binárias em geral.

3.2. Implementação da Estrutura Encadeada

A implementação de uma árvore binária usando a estrutura encadeada geralmente envolve os seguintes componentes:

1. Definição da estrutura do nó.
2. Criação de uma árvore de exemplo.
3. Implementação de traversals (percursos): pré-ordem, em-ordem e pós-ordem.
4. Funções para contar nós e nós follha.

3.2.1. Definição da Estrutura do Nó

A estrutura do nó para uma árvore binária encadeada normalmente inclui um campo para os dados e dois ponteiros para os nós filhos.

typedef char BTDataType; // Tipo de dado dos nós

typedef struct BinaryTreeNode {
   struct BinaryTreeNode* left;  // Ponteiro para o filho esquerdo
   struct BinaryTreeNode* right; // Ponteiro para o filho direito
   BTDataType data;             // Dado armazenado no nó
} BTNode;
   

3.2.2. Criação de uma Árvore de Exemplo

Vamos criar uma árvore binária simples para demonstrar as operações. Esta árvore terá nós rotulados de 'A' a 'E'.

// Alocação e inicialização dos nós
BTNode* nodeA = (BTNode*)malloc(sizeof(BTNode));
nodeA->data = 'A';
nodeA->left = NULL;
nodeA->right = NULL;

BTNode* nodeB = (BTNode*)malloc(sizeof(BTNode));
nodeB->data = 'B';
nodeB->left = NULL;
nodeB->right = NULL;

BTNode* nodeC = (BTNode*)malloc(sizeof(BTNode));
nodeC->data = 'C';
nodeC->left = NULL;
nodeC->right = NULL;

BTNode* nodeD = (BTNode*)malloc(sizeof(BTNode));
nodeD->data = 'D';
nodeD->left = NULL;
nodeD->right = NULL;

BTNode* nodeE = (BTNode*)malloc(sizeof(BTNode));
nodeE->data = 'E';
nodeE->left = NULL;
nodeE->right = NULL;

// Construção da estrutura da árvore
nodeA->left = nodeB;
nodeA->right = nodeC;
nodeB->left = nodeD;
nodeB->right = nodeE;

// Agora 'nodeA' é a raiz da nossa árvore binária de exemplo.
   

3.2.3. Travessia em Pré-ordem (NLR - Nó, Esquerda, Direita)

A travessia em pré-ordem visita o nó raiz, depois percorre recursivamente a subárvore esquerda e, por fim, a subárvore direita.

#include <stdio.h> // Necessário para printf

void traversePreOrder(BTNode* root) {
   if (root == NULL) {
       printf("NULL "); // Indica fim de um ramo
       return;
   }
   printf("%c ", root->data); // Visita o nó
   traversePreOrder(root->left);  // Percorre a subárvore esquerda
   traversePreOrder(root->right); // Percorre a subárvore direita
}
   

3.2.4. Travessia em Em-ordem (LNR - Esquerda, Nó, Direita)

A travessia em em-ordem percorre recursivamente a subárvore esqeurda, visita o nó raiz e, em seguida, percorre a subárvore direita. Para árvores de busca binária, a travessia em em-ordem retorna os elementos em ordem crescente.

#include <stdio.h> // Necessário para printf

void traverseInOrder(BTNode* root) {
   if (root == NULL) {
       return;
   }
   traverseInOrder(root->left);  // Percorre a subárvore esquerda
   printf("%c ", root->data); // Visita o nó
   traverseInOrder(root->right); // Percorre a subárvore direita
}
   

3.2.5. Travessia em Pós-ordem (LRN - Esquerda, Direita, Nó)

A travessia em pós-ordem percorre recursivamente a subárvore esquerda, depois a subárvore direita e, por fim, visita o nó raiz. É útil para operações como a exclusão de nós, pois garante que os filhos sejam processados antes dos pais.

#include <stdio.h> // Necessário para printf

void traversePostOrder(BTNode* root) {
   if (root == NULL) {
       return;
   }
   traversePostOrder(root->left);  // Percorre a subárvore esquerda
   traversePostOrder(root->right); // Percorre a subárvore direita
   printf("%c ", root->data); // Visita o nó
}