A representação de uma árvore binária utilizando uma estrutura encadeada envolve a criação de nós, cada um contendo um campo de dados e ponteiros para os filhos esquerdo e direito. A implementação é dividida em três arquivos: um cabeçalho (arvore.h), uma implementação (arvore.c) e um teste (teste.c).

arvore.h

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int TipoDado;

typedef struct NoArvBin {
    TipoDado info;
    struct NoArvBin* esq;
    struct NoArvBin* dir;
} NoArv;

// Travessias
void TravessiaPreOrdem(NoArv* raiz);
void TravessiaEmOrdem(NoArv* raiz);
void TravessiaPosOrdem(NoArv* raiz);

// Contagens
int QuantidadeNos(NoArv* raiz);
int QuantidadeFolhas(NoArv* raiz);
int QuantidadeNosNivelK(NoArv* raiz, int nivel);

// Propriedades
int AlturaArvore(NoArv* raiz);
NoArv* BuscarValor(NoArv* raiz, TipoDado valor);

// Operações
void DestruirArvore(NoArv** raiz);
void TravessiaPorNivel(NoArv* raiz);
bool ArvoreCompleta(NoArv* raiz);

arvore.c

Travessia pré-ordem: visita a raiz, depois a subárvore esquerda e por fim a subárvore direita.

#include "arvore.h"

void TravessiaPreOrdem(NoArv* raiz) {
    if (!raiz) return;
    printf("%d ", raiz->info);
    TravessiaPreOrdem(raiz->esq);
    TravessiaPreOrdem(raiz->dir);
}

Travessia em-ordem: visita a subárvore esquerda, depois a raiz e por fim a subárvore direita.

void TravessiaEmOrdem(NoArv* raiz) {
    if (!raiz) return;
    TravessiaEmOrdem(raiz->esq);
    printf("%d ", raiz->info);
    TravessiaEmOrdem(raiz->dir);
}

Travessia pós-ordem: visita a subárvore esquerda, depois a subárvore direita e por fim a raiz.

void TravessiaPosOrdem(NoArv* raiz) {
    if (!raiz) return;
    TravessiaPosOrdem(raiz->esq);
    TravessiaPosOrdem(raiz->dir);
    printf("%d ", raiz->info);
}

Quantidade de nós: retorna 0 se a raiz for nula, caso contrário, retorna 1 mais a soma das contagens das subárvores.

int QuantidadeNos(NoArv* raiz) {
    if (!raiz) return 0;
    return 1 + QuantidadeNos(raiz->esq) + QuantidadeNos(raiz->dir);
}

Quantidade de folhas: conta nós sem filhos recursivamente.

int QuantidadeFolhas(NoArv* raiz) {
    if (!raiz) return 0;
    if (!raiz->esq && !raiz->dir) return 1;
    return QuantidadeFolhas(raiz->esq) + QuantidadeFolhas(raiz->dir);
}

Quantidade de nós no nível k: decrementa o nível a cada chamada recursiva até chegar a 1.

int QuantidadeNosNivelK(NoArv* raiz, int nivel) {
    if (!raiz) return 0;
    if (nivel == 1) return 1;
    return QuantidadeNosNivelK(raiz->esq, nivel - 1) + QuantidadeNosNivelK(raiz->dir, nivel - 1);
}

Altura da árvore: calcula a maior profundidade entre as subárvores e adiciona 1.

int AlturaArvore(NoArv* raiz) {
    if (!raiz) return 0;
    int altEsq = AlturaArvore(raiz->esq);
    int altDir = AlturaArvore(raiz->dir);
    return (altEsq > altDir) ? altEsq + 1 : altDir + 1;
}

Buscar valor: procura recursivamente nas subárvores e retorna o nó correspondente.

NoArv* BuscarValor(NoArv* raiz, TipoDado valor) {
    if (!raiz) return NULL;
    if (raiz->info == valor) return raiz;
    NoArv* achouEsq = BuscarValor(raiz->esq, valor);
    if (achouEsq) return achouEsq;
    return BuscarValor(raiz->dir, valor);
}

Destruir árvore: libera a memória de forma pós-ordem, evitando acessos inválidos.

void DestruirArvore(NoArv** raiz) {
    if (*raiz == NULL) return;
    DestruirArvore(&((*raiz)->esq));
    DestruirArvore(&((*raiz)->dir));
    free(*raiz);
    *raiz = NULL;
}

Travessia por nível: utiliza uma fila para processar os nós largura-primeiro.

#include "fila.h"

void TravessiaPorNivel(NoArv* raiz) {
    Fila fila;
    InicializarFila(&fila);
    Enfileirar(&fila, raiz);
    while (!FilaVazia(&fila)) {
        NoArv* atual = FrenteFila(&fila);
        Desenfileirar(&fila);
        printf("%d ", atual->info);
        if (atual->esq) Enfileirar(&fila, atual->esq);
        if (atual->dir) Enfileirar(&fila, atual->dir);
    }
    DestruirFila(&fila);
}

Verificar se a árvore é completa: usa uma fila para detectar lacunas nos níveis inferiores.

bool ArvoreCompleta(NoArv* raiz) {
    Fila fila;
    InicializarFila(&fila);
    Enfileirar(&fila, raiz);
    while (!FilaVazia(&fila)) {
        NoArv* atual = FrenteFila(&fila);
        Desenfileirar(&fila);
        if (!atual) break;
        Enfileirar(&fila, atual->esq);
        Enfileirar(&fila, atual->dir);
    }
    while (!FilaVazia(&fila)) {
        NoArv* atual = FrenteFila(&fila);
        Desenfileirar(&fila);
        if (atual) {
            DestruirFila(&fila);
            return false;
        }
    }
    DestruirFila(&fila);
    return true;
}

teste.c

Construção manual de uma árvore para demosntração.

#include "arvore.h"

NoArv* CriarNo(TipoDado valor) {
    NoArv* novo = (NoArv*)malloc(sizeof(NoArv));
    if (!novo) {
        perror("Falha na alocação");
        exit(EXIT_FAILURE);
    }
    novo->info = valor;
    novo->esq = novo->dir = NULL;
    return novo;
}

void ExecutarTeste() {
    NoArv* n1 = CriarNo(10);
    NoArv* n2 = CriarNo(20);
    NoArv* n3 = CriarNo(30);
    NoArv* n4 = CriarNo(40);
    n1->esq = n2;
    n1->dir = n3;
    n2->esq = n4;

    TravessiaPreOrdem(n1);
    printf("\n");
    TravessiaEmOrdem(n1);
    printf("\n");
    TravessiaPosOrdem(n1);
    printf("\n");

    printf("Total de nós: %d\n", QuantidadeNos(n1));
    printf("Folhas: %d\n", QuantidadeFolhas(n1));
    printf("Nós no nível 3: %d\n", QuantidadeNosNivelK(n1, 3));
    printf("Altura: %d\n", AlturaArvore(n1));
    printf("Valor 40 encontrado no nó: %d\n", BuscarValor(n1, 40)->info);

    TravessiaPorNivel(n1);
    printf("\n");
    printf("%s\n", ArvoreCompleta(n1) ? "É uma árvore completa" : "Não é uma árvore completa");

    DestruirArvore(&n1);
}

int main() {
    ExecutarTeste();
    return 0;
}