1. O que é uma Árvore Binária

Uma árvore binária é uma estrutura de dados hierárquica onde cada nó possui no máximo dois filhos, referenciados como filho esquerdo e filho direito. É uma estrutura fundamental na computação, usada em diversas aplicações como bancos de dados, sistemas de arquivos e algoritmos de busca.

Existem variações importantes das árvores binárias:

• Árvore Binária Cheia (Full Binary Tree): todos os nós, exceto os folha, possuem dois filhos.
• Árvore Binária Completa (Complete Binary Tree): todos os níveis, exceto possivelmente o último, estão completamente preenchidos, e todos os nós do último nível estão o mais à esquerda possível.

2. Implementando a Estrutura Básica

A estrutura de um nó em uma árvore binária típica em C pode ser definida da seguinte forma:

typedef char TreeValue;

typedef struct TreeNode {
    TreeValue info;
    struct TreeNode *leftChild;
    struct TreeNode *rightChild;
} TreeNode;

2.1 Construção via Travessia Pré-Ordem

Uma forma comum de construir uma árvore binária é usando uma lista de valores em pré-ordem, onde um caractere especial (como '#') indica um nó nulo. A função recursiva a seguir demonstra este processo:

TreeNode* buildTree(char *sequence, int *currentIndex) {
    if (sequence[*currentIndex] == '#') {
        (*currentIndex)++;
        return NULL;
    }

    TreeNode *newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->info = sequence[(*currentIndex)++];
    newNode->leftChild = buildTree(sequence, currentIndex);
    newNode->rightChild = buildTree(sequence, currentIndex);
    return newNode;
}

A construção segue a ordem: nó atual, subárvore esquerda, subárvore direita. Este método é intrinsecamente ligado ao conceito de travessia pré-ordem.

3. Métodos de Travessia

Existem diferentes maneiras de percorrer uma árvore binária para visitar todos os seus nós. As três travessias recursivas principais são:

3.1 Travessia Pré-Ordem (Raiz-Esquerda-Direita)

Visita o nó atual, depois recursivamente a subárvore esquerda, e finalmente a subárvore direita.

void preOrderTraversal(TreeNode *node) {
    if (node == NULL) return;
    printf("%c ", node->info);
    preOrderTraversal(node->leftChild);
    preOrderTraversal(node->rightChild);
}

3.2 Travessia Em-Ordem (Esquerda-Raiz-Direita)

Recursivamente percorre a subárvore esquerda, visita o nó atual, e depois percorre a subárvore direita. Em uma árvore de busca binária, esta travessia produz os valores em ordem crescente.

void inOrderTraversal(TreeNode *node) {
    if (node == NULL) return;
    inOrderTraversal(node->leftChild);
    printf("%c ", node->info);
    inOrderTraversal(node->rightChild);
}

3.3 Travessia Pós-Ordem (Esquerda-Direita-Raiz)

Percorre recursivamente as subárvores esquerda e direita antes de visitar o nó atual.

void postOrderTraversal(TreeNode *node) {
    if (node == NULL) return;
    postOrderTraversal(node->leftChild);
    postOrderTraversal(node->rightChild);
    printf("%c ", node->info);
}

3.4 Travessia em Nível (Largura)

Diferente das travessias em profundidade anteriores, a travessia em nível visita os nós nível por nível, da esquerda para a direita. Utiliza uma fila para gerenciar a ordem de visita.

void levelOrderTraversal(TreeNode *root) {
    if (root == NULL) return;
    
    // Fila implementada com array (exemplo simplificado)
    TreeNode *queue[100];
    int front = 0, rear = 0;
    
    queue[rear++] = root;
    
    while (front < rear) {
        TreeNode *current = queue[front++];
        printf("%c ", current->info);
        
        if (current->leftChild != NULL) {
            queue[rear++] = current->leftChild;
        }
        if (current->rightChild != NULL) {
            queue[rear++] = current->rightChild;
        }
    }
}

4. Operações Fundamentais e Consultas

4.1 Contagem de Nós

Para contar o número total de nós na árvore, podemos percorrer toda a estrutura recursivamente.

int countNodes(TreeNode *node) {
    if (node == NULL) return 0;
    return 1 + countNodes(node->leftChild) + countNodes(node->rightChild);
}

4.2 Contagem de Nós Folha

Nós folha são aqueles sem filhos (esquerdo e direito são nulos).

int countLeaves(TreeNode *node) {
    if (node == NULL) return 0;
    if (node->leftChild == NULL && node->rightChild == NULL) return 1;
    return countLeaves(node->leftChild) + countLeaves(node->rightChild);
}

4.3 Contagem de Nós em um Nível Específico

Podemos determinar quantos nós existem em um determinado nível k (considerando a raiz como nível 1).

int countNodesAtLevel(TreeNode *node, int targetLevel) {
    if (node == NULL) return 0;
    if (targetLevel == 1) return 1;
    return countNodesAtLevel(node->leftChild, targetLevel - 1) +
           countNodesAtLevel(node->rightChild, targetLevel - 1);
}

4.4 Busca por Valor

Para encontrar um nó com um valor específico, percorremos a árvore até encontrarmos o valor ou esgotarmos as possibilidades.

TreeNode* searchValue(TreeNode *node, char target) {
    if (node == NULL) return NULL;
    if (node->info == target) return node;
    
    TreeNode *foundInLeft = searchValue(node->leftChild, target);
    if (foundInLeft != NULL) return foundInLeft;
    
    return searchValue(node->rightChild, target);
}

4.5 Veriifcação de Árvore Binária Completa

Uma abordagem baseada em BFS pode ser usada para verificar se uma árvore é completa. A ideia é que, durante uma travessia em nível, após encontrarmos um nó nulo, não devemos encontrar mais nenhum nó não nulo.

bool isCompleteBinaryTree(TreeNode *root) {
    if (root == NULL) return true;
    
    TreeNode *queue[100];
    int front = 0, rear = 0;
    bool reachedEnd = false;
    
    queue[rear++] = root;
    
    while (front < rear) {
        TreeNode *current = queue[front++];
        
        if (current == NULL) {
            reachedEnd = true;
        } else {
            if (reachedEnd) return false;
            queue[rear++] = current->leftChild;
            queue[rear++] = current->rightChild;
        }
    }
    return true;
}