Árvores binárias são estruturas de dados hierárquicas fundamentais em ciência da computação. Cada nó possui, no máximo, dois filhos, denominados filho esquerdo e filho direito. Elas são amplamente utilizadas para representar hierarquias, expressões matemáticas, e para implementar estruturas como árvores de busca, heaps e árvores AVL.

Nesta aula, vamos explorar a implementação de árvores binárias em C, desde a definição da estrutura até algoritmos de inserção e percurso, sempre utilizando recursão, que é a técnica natural para lidar com estruturas recursivas.

Estrutura

Em C, uma árvore binária é definida por um nó que contém um campo de dados e dois ponteiros para os nós filhos. A estrutura básica pode ser declarada como:

typedef struct No {
    int valor;
    struct No *esquerda;
    struct No *direita;
} No;

Normalmente, criamos uma árvore como um ponteiro para o nó raiz. Inicialmente, a árvore é vazia (NULL). A criação de um novo nó envolve alocação dinâmica de memória com malloc e inicialização dos campos. Veja um exemplo de função que aloca um nó:

No* criarNo(int valor) {
    No* novo = (No*) malloc(sizeof(No));
    if (novo != NULL) {
        novo->valor = valor;
        novo->esquerda = NULL;
        novo->direita = NULL;
    }
    return novo;
}

É importante sempre verificar se a alocação foi bem-sucedida. A árvore em si é apenas um ponteiro para o nó raiz, que pode ser NULL para indicar árvore vazia.

Inserção

Para inserir um valor em uma árvore binária, precisamos definir uma regra. Em uma árvore binária de busca (BST), valores menores vão para a esquerda, e maiores para a direita. Vamos implementar uma inserção recursiva que retorna o ponteiro para a raiz (que pode mudar). A função recebe a raiz e o valor a ser inserido:

No* inserir(No* raiz, int valor) {
    if (raiz == NULL) {
        return criarNo(valor);
    }
    if (valor < raiz->valor) {
        raiz->esquerda = inserir(raiz->esquerda, valor);
    } else if (valor > raiz->valor) {
        raiz->direita = inserir(raiz->direita, valor);
    }
    // Se valor já existe, não faz nada (ignoramos duplicados)
    return raiz;
}

Essa função cria um novo nó quando encontra um ponteiro NULL, e caso contrário, desce recursivamente pela árvore. Note que a raiz pode ser atualizada, por isso a função retorna o ponteiro. No main, chamaríamos assim:

No* arvore = NULL;
arvore = inserir(arvore, 10);
arvore = inserir(arvore, 5);
arvore = inserir(arvore, 15);

Após essas inserções, a árvore tem raiz 10, filho esquerdo 5 e filho direito 15.

Travessias (in/pre/pos-ordem)

Percurso (ou travessia) é a visita a todos os nós da árvore em uma ordem específica. Existem três percursos clássicos em árvores binárias, todos recursivos:

  • Pré-ordem: visita a raiz, depois percorre a subárvore esquerda, depois a direita.
  • Em ordem: percorre a subárvore esquerda, visita a raiz, depois a direita. Em uma BST, isso gera os valores em ordem crescente.
  • Pós-ordem: percorre a esquerda, depois a direita, e por fim visita a raiz.

Implementações:

void preOrdem(No* raiz) {
    if (raiz != NULL) {
        printf("%d ", raiz->valor);
        preOrdem(raiz->esquerda);
        preOrdem(raiz->direita);
    }
}

void emOrdem(No* raiz) {
    if (raiz != NULL) {
        emOrdem(raiz->esquerda);
        printf("%d ", raiz->valor);
        emOrdem(raiz->direita);
    }
}

void posOrdem(No* raiz) {
    if (raiz != NULL) {
        posOrdem(raiz->esquerda);
        posOrdem(raiz->direita);
        printf("%d ", raiz->valor);
    }
}

Para a árvore com valores 10, 5 e 15, teremos:
Pré-ordem: 10 5 15
Em ordem: 5 10 15
Pós-ordem: 5 15 10

Esses percursos são úteis para diferentes propósitos, como serializar a árvore, calcular expressões, etc.

Recursão

A recursão é a técnica de uma função chamar a si mesma. No contexto de árvores, é natural porque a definição de uma árvore é recursiva: uma árvore é composta por um nó e duas subárvores. Cada chamada recursiva resolve um subproblema menor, até atingir o caso base (NULL).

Por exemplo, para calcular a altura da árvore, usamos recursão:

int altura(No* raiz) {
    if (raiz == NULL) {
        return -1; // altura de árvore vazia é -1 (ou 0, dependendo da definição)
    }
    int alt_esq = altura(raiz->esquerda);
    int alt_dir = altura(raiz->direita);
    return (alt_esq > alt_dir ? alt_esq : alt_dir) + 1;
}

Outro exemplo clássico é a liberação da memória da árvore (pós-ordem para liberar os filhos antes do nó):

void liberar(No* raiz) {
    if (raiz != NULL) {
        liberar(raiz->esquerda);
        liberar(raiz->direita);
        free(raiz);
    }
}

É crucial entender o funcionamento da pilha de chamadas: cada chamada recursiva cria um novo contexto, e o retorno se dá na ordem inversa. Para árvores muito profundas, a recursão pode causar estouro de pilha, mas para a maioria dos casos é adequada.

Boas práticas e observações finais

Ao implementar árvores em C, sempre verifique a alocação de memória, use funções auxiliares para operações comuns e documente o comportamento. Considere a possibilidade de árvores desbalanceadas e, se necessário, implemente balanceamento (AVL ou Rubro-Negra). Além disso, para percursos iterativos, pode-se usar pilhas explícitas, mas a recursão é mais simples e legível.

Referências

Exercícios

  1. Escreva uma função em C que conta o número de nós em uma árvore binária. Dica: use recursão.

✓ Resposta: 
int contarNos(No* raiz) {
    if (raiz == NULL) return 0;
    return 1 + contarNos(raiz->esquerda) + contarNos(raiz->direita);
}
  • Implemente uma função que busca um valor em uma árvore binária de busca, retornando 1 se encontrado e 0 caso contrário.

    • ✓ Resposta: 
    int buscar(No* raiz, int valor) {
    if (raiz == NULL) return 0;
    if (valor == raiz->valor) return 1;
    if (valor < raiz->valor) return buscar(raiz->esquerda, valor);
    else return buscar(raiz->direita, valor);
}
  • Crie uma função que imprime os valores da árvore em ordem decrescente. (Dica: percorra primeiro a direita, depois a raiz, depois a esquerda).

    • ✓ Resposta: 
    void emOrdemDecrescente(No* raiz) {
    if (raiz != NULL) {
        emOrdemDecrescente(raiz->direita);
        printf("%d ", raiz->valor);
        emOrdemDecrescente(raiz->esquerda);
    }
}
  • Escreva uma função que verifica se uma árvore binária é uma árvore binária de busca válida. Assuma que não há valores duplicados.

    • ✓ Resposta: 
    int ehBST(No* raiz, int min, int max) {
    if (raiz == NULL) return 1;
    if (raiz->valor <= min || raiz->valor >= max) return 0;
    return ehBST(raiz->esquerda, min, raiz->valor) &&
           ehBST(raiz->direita, raiz->valor, max);
}

// Chamada inicial: ehBST(raiz, INT_MIN, INT_MAX);
  • Implemente uma função que retorna o menor valor em uma árvore binária de busca.

    • ✓ Resposta: 
    int menorValor(No* raiz) {
    if (raiz == NULL) {
        // Tratar erro ou retornar um valor sentinela
        return -1;
    }
    while (raiz->esquerda != NULL) {
        raiz = raiz->esquerda;
    }
    return raiz->valor;
}
// Versão recursiva:
// int menorValor(No* raiz) {
//     if (raiz->esquerda == NULL) return raiz->valor;
//     return menorValor(raiz->esquerda);
// }