📚 Capítulo do curso: 19 — Estruturas de Dados Dinâmicas (Listas, Pilhas, Filas e BST) da Especialização em Sistemas com C. Leia o capítulo antes de começar.

🌳 Miniprojeto C 19 — Fila de Prioridades com Árvore Binária de Busca

Estrutura de dados dinâmica hierárquica com percursos e liberação de memória.

🎯 Objetivos

• Modelar um nó auto-referenciado no heap (struct Tarefa contendo ponteiros para outras struct Tarefa).
• Implementar inserção recursiva em uma Árvore Binária de Busca (BST), mantendo sua propriedade de ordenação.
• Implementar o percurso in-order, que visita os nós em ordem crescente de chave.
• Implementar busca em O(log n) médio, descartando metade da árvore a cada comparação.
• Liberar recursivamente toda a árvore ao final, sem vazar memória.

📋 O problema

Diferente de um array, uma árvore binária de busca não precisa de um tamanho pré-definido nem de realocação: cada tarefa nova vira um nó novo alocado dinamicamente, ligado à árvore pelo ponteiro certo. Você vai construir uma fila de prioridades de tarefas de um sistema de tickets, onde a prioridade de cada tarefa funciona como a chave de ordenação da árvore.

Seu programa (main.c) deve:

1. Definir struct Tarefa { int prioridade; char descricao[50]; struct Tarefa *esquerda, *direita; };.
2. Implementar struct Tarefa *inserir(struct Tarefa *raiz, int prioridade, const char *descricao), que aloca um novo nó com malloc e o insere na posição correta, mantendo a propriedade de BST (prioridade menor à esquerda, maior à direita).
3. Inserir pelo menos 6 tarefas fixas, todas com prioridades diferentes.
4. Implementar void percorrer_em_ordem(const struct Tarefa *raiz), que imprime as tarefas em ordem crescente de prioridade (percurso in-order: esquerda → raiz → direita).
5. Implementar const struct Tarefa *buscar(const struct Tarefa *raiz, int prioridade), que retorna o nó com a prioridade buscada ou NULL se não existir. Testar com uma prioridade existente e uma inexistente.
6. Implementar void liberar_arvore(struct Tarefa *raiz), que libera todos os nós recursivamente antes do programa terminar.

graph TD
    A["inserir(raiz, prioridade, descricao)"] --> B{"raiz == NULL?"}
    B -- "sim" --> C["malloc novo no'"]
    B -- "nao, prioridade < raiz" --> D["inserir(raiz->esquerda, ...)"]
    B -- "nao, prioridade > raiz" --> E["inserir(raiz->direita, ...)"]
    F["percorrer_em_ordem"] --> G["esquerda -> raiz -> direita\n(ordem crescente)"]
    H["liberar_arvore"] --> I["libera esquerda -> direita -> raiz\n(pos-ordem, sem leak)"]

    style C fill:#0284c7,stroke:#38bdf8,color:#ffffff
    style G fill:#0d9488,stroke:#2dd4bf,color:#ffffff
    style I fill:#059669,stroke:#34d399,color:#ffffff

🧰 Ambiente

O mesmo do Miniprojeto 01: gcc 8 ou mais novo. No Windows, rode chcp 65001 se os emojis aparecerem quebrados.

Passo 1 — Compilar o esqueleto

🎯 Objetivo: partir de um código que compila e roda, antes de escrever qualquer linha.

⌨️ Faça: crie a pasta c_mini_19, salve o código abaixo como main.c e rode:

gcc -Wall -Wextra -Wpedantic -std=c17 main.c -o app
./app          # Linux/macOS
.\app.exe      # Windows (PowerShell)

📄 src/esqueleto.c

/*
 * Miniprojeto 19: Fila de Prioridades com Arvore Binaria de Busca (BST)
 * Especializacao em Engenharia de Sistemas em C
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Tarefa {
    int prioridade;
    char descricao[50];
    struct Tarefa *esquerda;
    struct Tarefa *direita;
};

struct Tarefa *criar_tarefa(int prioridade, const char *descricao) {
    (void)prioridade; (void)descricao; // stub: apague esta linha ao implementar
    // TODO 1: aloque um "struct Tarefa" com malloc, valide contra NULL
    // (imprima erro e chame exit(EXIT_FAILURE) se falhar), preencha
    // prioridade, copie descricao com strncpy (garantindo terminador
    // '\0'), e inicialize esquerda/direita com NULL. Retorne o ponteiro.
    return NULL;
}

struct Tarefa *inserir(struct Tarefa *raiz, int prioridade, const char *descricao) {
    (void)prioridade; (void)descricao; // stub: apague esta linha ao implementar
    // TODO 2: se raiz == NULL, retorne criar_tarefa(prioridade, descricao).
    // Se prioridade < raiz->prioridade, insira recursivamente na esquerda.
    // Se prioridade > raiz->prioridade, insira recursivamente na direita.
    // Se for igual, imprima um aviso de duplicata (nao insira de novo).
    // Nao esqueca de retornar "raiz" no final.
    return raiz;
}

void percorrer_em_ordem(const struct Tarefa *raiz) {
    (void)raiz; // stub: apague esta linha ao implementar
    // TODO 3: caso base (raiz == NULL, retorne). Senao: percorra a
    // esquerda, imprima a raiz, percorra a direita (nessa ordem).
}

const struct Tarefa *buscar(const struct Tarefa *raiz, int prioridade) {
    (void)raiz; (void)prioridade; // stub: apague esta linha ao implementar
    // TODO 4: caso base (raiz == NULL, retorne NULL). Se achou, retorne
    // raiz. Senao va' para esquerda ou direita conforme a comparacao.
    return NULL;
}

void liberar_arvore(struct Tarefa *raiz) {
    (void)raiz; // stub: apague esta linha ao implementar
    // TODO 5: caso base (raiz == NULL, retorne). Libere recursivamente
    // esquerda e direita ANTES de dar free(raiz) (pos-ordem).
}

int main(void) {
    printf("====================================================\n");
    printf(" ⚡ Miniprojeto 19: Fila de Prioridades com BST\n");
    printf("====================================================\n");

    struct Tarefa *raiz = NULL;
    // As 6 tarefas do problema. Enquanto inserir() for um stub, raiz continua NULL.
    raiz = inserir(raiz, 50, "Revisar pull request");
    raiz = inserir(raiz, 20, "Corrigir bug critico em producao");
    raiz = inserir(raiz, 80, "Atualizar documentacao");
    raiz = inserir(raiz, 10, "Responder incidente de seguranca");
    raiz = inserir(raiz, 35, "Preparar reuniao de sprint");
    raiz = inserir(raiz, 65, "Otimizar consulta lenta no banco");

    printf("\n--- Tarefas em ordem crescente de prioridade (in-order) ---\n");
    // TODO 7: chame percorrer_em_ordem(raiz).

    printf("\n--- Buscando tarefas por prioridade ---\n");
    // TODO 8: busque uma prioridade que EXISTE e imprima o resultado.
    // Busque tambem uma prioridade que NAO EXISTE e imprima "nao encontrada".

    printf("\n--- Liberando toda a arvore (sem memory leak) ---\n");
    // TODO 9: chame liberar_arvore(raiz) e atribua raiz = NULL.

    printf("====================================================\n");
    printf(" ✅ Status: Operacional e Validado!\n");
    printf("====================================================\n");

    return EXIT_SUCCESS;
}

✅ Checkpoint: zero avisos do gcc, e a saída é:

🖥️ Saída esperada:

====================================================
 ⚡ Miniprojeto 19: Fila de Prioridades com BST
====================================================

--- Tarefas em ordem crescente de prioridade (in-order) ---

--- Buscando tarefas por prioridade ---

--- Liberando toda a arvore (sem memory leak) ---
====================================================
 ✅ Status: Operacional e Validado!
====================================================

As 6 inserções já estão no main, mas inserir ainda é um stub e devolve NULL. Por isso nenhuma tarefa aparece.

💡 As linhas (void)...; silenciam o aviso de parâmetro não usado enquanto a função é um stub. Apague cada uma ao implementar a função.

Passo 2 — Criar e inserir nós (TODO 1 e 2)

🎯 Objetivo: montar a árvore com nós alocados um a um no heap.

⌨️ Faça:

1. criar_tarefa: malloc(sizeof(struct Tarefa)); se NULL, imprima um erro e exit(EXIT_FAILURE). Preencha prioridade, copie a descrição com strncpy + terminador '\0' e zere esquerda e direita.
2. inserir (recursiva): se raiz == NULL, devolva criar_tarefa(...). Se a prioridade for menor, raiz->esquerda = inserir(raiz->esquerda, ...); se for maior, o mesmo à direita; se for igual, avise que é duplicata. Sempre devolva raiz.

✅ Checkpoint: ainda não há percurso para imprimir, mas o programa roda até o fim sem travar. Num depurador, ou com um printf temporário, raiz->prioridade é 50, raiz->esquerda->prioridade é 20 e raiz->direita->prioridade é 80.

🧯 Se der errado: a árvore fica só com o último nó, ou vazia: faltou reatribuir o retorno (raiz->esquerda = inserir(...)). Sem isso, o nó novo é criado e se perde.

Passo 3 — Percurso in-order (TODO 3 e 7)

🎯 Objetivo: visitar esquerda → raiz → direita e obter a ordem crescente de graça.

⌨️ Faça: caso base if (raiz == NULL) return;. Depois percorrer_em_ordem(raiz->esquerda);, imprima ` [prioridade %d] %s e percorrer_em_ordem(raiz->direita);. Chame a função no main`.

✅ Checkpoint: 6 linhas, de [prioridade 10] até [prioridade 80], em ordem crescente, embora tenham sido inseridas na ordem 50, 20, 80, 10, 35, 65.

Passo 4 — Busca (TODO 4 e 8)

🎯 Objetivo: descartar metade da árvore a cada comparação.

⌨️ Faça: caso base NULL → NULL. Se a prioridade bate, devolva raiz; se é menor, busque só na esquerda; senão, só na direita. No main, busque 20 e 99 e imprima o resultado de cada uma.

✅ Checkpoint: Prioridade 20 encontrada: "Corrigir bug critico em producao" e Prioridade 99 nao encontrada.. A busca por 20 visita só 2 nós (50 → 20).

Passo 5 — Liberar a árvore (TODO 5 e 9)

🎯 Objetivo: devolver toda a memória, filhos antes do pai.

⌨️ Faça: caso base NULL. Depois liberar_arvore(raiz->esquerda); liberar_arvore(raiz->direita); free(raiz);. No main, chame e faça raiz = NULL.

✅ Checkpoint: Memoria liberada com sucesso. No Linux ou WSL, valgrind --leak-check=full ./app mostra All heap blocks were freed.

🧯 Se der errado: se você fizer free(raiz) antes de liberar os filhos, ler raiz->esquerda depois disso é uso de memória já liberada (use-after-free), e o Valgrind acusa Invalid read.

Passo final — Conferir com o gabarito

🎯 Objetivo: validar a saída completa e o código de retorno.

✅ Checkpoint: a saída é esta, e o código de retorno é 0 (echo $? no Linux/macOS ou echo $LASTEXITCODE no PowerShell):

🖥️ Saída esperada:

====================================================
 ⚡ Miniprojeto 19: Fila de Prioridades com BST
====================================================

--- Tarefas em ordem crescente de prioridade (in-order) ---
  [prioridade 10] Responder incidente de seguranca
  [prioridade 20] Corrigir bug critico em producao
  [prioridade 35] Preparar reuniao de sprint
  [prioridade 50] Revisar pull request
  [prioridade 65] Otimizar consulta lenta no banco
  [prioridade 80] Atualizar documentacao

--- Buscando tarefas por prioridade ---
Prioridade 20 encontrada: "Corrigir bug critico em producao"
Prioridade 99 nao encontrada.

--- Liberando toda a arvore (sem memory leak) ---
Memoria liberada com sucesso.
====================================================
 ✅ Status: Operacional e Validado!
====================================================

Só abra o gabarito depois de chegar até aqui:

/*
 * Miniprojeto 19: Fila de Prioridades com Arvore Binaria de Busca (BST)
 * Especializacao em Engenharia de Sistemas em C
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Tarefa {
    int prioridade;
    char descricao[50];
    struct Tarefa *esquerda;
    struct Tarefa *direita;
};

struct Tarefa *criar_tarefa(int prioridade, const char *descricao) {
    struct Tarefa *nova = malloc(sizeof(struct Tarefa));
    if (nova == NULL) {
        fprintf(stderr, "ERRO: falha ao alocar memoria para nova tarefa.\n");
        exit(EXIT_FAILURE);
    }
    nova->prioridade = prioridade;
    strncpy(nova->descricao, descricao, sizeof(nova->descricao) - 1);
    nova->descricao[sizeof(nova->descricao) - 1] = '\0';
    nova->esquerda = NULL;
    nova->direita = NULL;
    return nova;
}

/* Insere recursivamente mantendo a propriedade da BST:
 * prioridade menor vai para a esquerda, maior para a direita. */
struct Tarefa *inserir(struct Tarefa *raiz, int prioridade, const char *descricao) {
    if (raiz == NULL) {
        return criar_tarefa(prioridade, descricao);
    }
    if (prioridade < raiz->prioridade) {
        raiz->esquerda = inserir(raiz->esquerda, prioridade, descricao);
    } else if (prioridade > raiz->prioridade) {
        raiz->direita = inserir(raiz->direita, prioridade, descricao);
    } else {
        printf("  [AVISO] Prioridade %d ja existe, tarefa ignorada.\n", prioridade);
    }
    return raiz;
}

/* Percurso in-order: esquerda -> raiz -> direita = ordem crescente. */
void percorrer_em_ordem(const struct Tarefa *raiz) {
    if (raiz == NULL) {
        return;
    }
    percorrer_em_ordem(raiz->esquerda);
    printf("  [prioridade %d] %s\n", raiz->prioridade, raiz->descricao);
    percorrer_em_ordem(raiz->direita);
}

/* Busca O(log n) medio: a cada passo descarta metade da arvore
 * restante, seguindo para esquerda ou direita conforme a comparacao. */
const struct Tarefa *buscar(const struct Tarefa *raiz, int prioridade) {
    if (raiz == NULL) {
        return NULL;
    }
    if (prioridade == raiz->prioridade) {
        return raiz;
    }
    if (prioridade < raiz->prioridade) {
        return buscar(raiz->esquerda, prioridade);
    }
    return buscar(raiz->direita, prioridade);
}

/* Libera toda a arvore recursivamente (pos-ordem: filhos antes do pai,
 * senao perderiamos o ponteiro para os filhos antes de libera-los). */
void liberar_arvore(struct Tarefa *raiz) {
    if (raiz == NULL) {
        return;
    }
    liberar_arvore(raiz->esquerda);
    liberar_arvore(raiz->direita);
    free(raiz);
}

int main(void) {
    printf("====================================================\n");
    printf(" ⚡ Miniprojeto 19: Fila de Prioridades com BST\n");
    printf("====================================================\n");

    struct Tarefa *raiz = NULL;
    raiz = inserir(raiz, 50, "Revisar pull request");
    raiz = inserir(raiz, 20, "Corrigir bug critico em producao");
    raiz = inserir(raiz, 80, "Atualizar documentacao");
    raiz = inserir(raiz, 10, "Responder incidente de seguranca");
    raiz = inserir(raiz, 35, "Preparar reuniao de sprint");
    raiz = inserir(raiz, 65, "Otimizar consulta lenta no banco");

    printf("\n--- Tarefas em ordem crescente de prioridade (in-order) ---\n");
    percorrer_em_ordem(raiz);

    printf("\n--- Buscando tarefas por prioridade ---\n");
    int alvo_existente = 20;
    const struct Tarefa *encontrada = buscar(raiz, alvo_existente);
    if (encontrada != NULL) {
        printf("Prioridade %d encontrada: \"%s\"\n", alvo_existente, encontrada->descricao);
    } else {
        printf("Prioridade %d nao encontrada.\n", alvo_existente);
    }

    int alvo_inexistente = 99;
    encontrada = buscar(raiz, alvo_inexistente);
    if (encontrada != NULL) {
        printf("Prioridade %d encontrada: \"%s\"\n", alvo_inexistente, encontrada->descricao);
    } else {
        printf("Prioridade %d nao encontrada.\n", alvo_inexistente);
    }

    printf("\n--- Liberando toda a arvore (sem memory leak) ---\n");
    liberar_arvore(raiz);
    raiz = NULL;
    printf("Memoria liberada com sucesso.\n");

    printf("====================================================\n");
    printf(" ✅ Status: Operacional e Validado!\n");
    printf("====================================================\n");

    return EXIT_SUCCESS;
}

Por que isso importa: essa é a mesma estrutura por trás de índices de bancos de dados (B-Trees são uma generalização da BST), de std::map/std::set em C++ e de TreeMap em Java — todos mantêm dados ordenados com inserção e busca em tempo logarítmico médio.

🏆 Desafio

Implemente int altura(const struct Tarefa *raiz), que calcula recursivamente a altura da árvore (1 + max(altura(esquerda), altura(direita)), com caso base 0 para raiz == NULL), e int contar_nos(const struct Tarefa *raiz), que conta quantos nós existem. Insira as 6 tarefas em ordens diferentes (ex: já em ordem crescente de prioridade) e observe como a altura da árvore muda — essa é a motivação para árvores balanceadas (AVL, Red-Black), fora do escopo deste miniprojeto.

✅ Checkpoint: com a ordem de inserção do projeto, altura é 3 e contar_nos é 6. Inserindo as mesmas 6 tarefas já em ordem crescente (10, 20, 35, 50, 65, 80), a altura vira 6: a árvore degenera numa lista ligada, e a busca volta a ser O(n).

🧭 Navegação

📋 Projetos do curso de C | 📚 Teoria do Capítulo 19 | 🗂️ Hub de projetos