Implementar, em linguagem C, o algoritmo de inclusão em uma árvore digital.

Passo 1

Beleza, então o exercício pede para escrever em C o algoritmo de inserção numa árvore digital (ou trie). O assunto aqui é estruturas de dados, mais especificamente trie binária (cada nó tem dois ponteiros, 0 ou 1). Para resolver, vamos precisar entender como representar um nó em C, como percorrer os bits da chave que queremos inserir e como criar novos nós conforme vamos descendo na árvore.

Passo 2

Antes de codar, vamos relembrar a teoria:
  • Uma árvore digital guarda chaves (normalmente cadeias de caracteres ou números) distribuindo-as a partir dos bits ou caracteres.
  • Cada nó tem, no nosso caso, dois filhos: filho[0] e filho[1].
  • Para inserir, começamos no bit mais significativo da chave e, a cada bit, escolhemos o caminho 0 ou 1.
  • Se o caminho não existe, criamos um novo nó. No fim, marcamos o nó como término de chave.

Passo 3

Agora vamos ver como pegar o bit certo de uma chave inteira em C. Se a chave é um unsigned int chave, e queremos do bit mais significativo (bit 31) ao menos (bit 0), fazemos:
int bit = (chave >> i) & 1;
Em LaTeX, isso seria:

Ou seja: deslocamos a chave i posições para a direita e isolamos o último bit com & 1.

Passo 4

Definindo a struct do nó em C, de forma bem direta:
typedef struct No {
    struct No *filho[2];  // ponteiros para 0 e 1
    int fimDeChave;       // marca se aqui termina uma chave
} No;
  • filho[0] é o caminho para o bit 0
  • filho[1] é o caminho para o bit 1
  • fimDeChave serve para marcarmos que aquela sequência de bits forma uma chave válida.

Passo 5

Vamos ao passo a passo da função inserir(No **raiz, unsigned int chave):
  1. Se a raiz é NULL, aloca um nó novo e inicializa tudo para NULL/0.
  2. Para cada bit da chave (de 31 a 0):
    a. Calcula bit = (chave >> i) & 1.
    b. Se (*atual)->filho[bit] for NULL, aloca um novo nó e inicializa.
    c. Move o ponteiro atual para (*atual)->filho[bit].
  3. No final do laço, faz atual->fimDeChave = 1.

Passo 6

Implementação completa em C:
#include <stdio.h>
#include <stdlib.h>

typedef struct No {
    struct No *filho[2];
    int fimDeChave;
} No;

// Cria um nó e inicializa
No* criaNo() {
    No *novo = (No*) malloc(sizeof(No));
    if (!novo) return NULL;
    novo->filho[0] = novo->filho[1] = NULL;
    novo->fimDeChave = 0;
    return novo;
}

// Insere uma chave na trie
void inserir(No **raiz, unsigned int chave) {
    if (*raiz == NULL) {
        *raiz = criaNo();
        if (*raiz == NULL) return; // falha na alocação
    }
    No *atual = *raiz;
    for (int i = 31; i >= 0; i--) {
        int bit = (chave >> i) & 1; // extrai o bit i
        if (atual->filho[bit] == NULL) {
            atual->filho[bit] = criaNo();
            if (atual->filho[bit] == NULL) return; // falha
        }
        atual = atual->filho[bit];
    }
    atual->fimDeChave = 1; // marca o fim da chave
}

Resposta

Veja acima a definição da struct No, a função criaNo() e a implementação da inserir() que faz exatamente o algoritmo de inclusão em uma árvore digital (trie) em C.

Exercícios relacionados