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]
efilho[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
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 0filho[1]
é o caminho para o bit 1fimDeChave
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)
:- Se a raiz é NULL, aloca um nó novo e inicializa tudo para NULL/0.
- Para cada bit da chave (de 31 a 0):
a. Calculabit = (chave >> i) & 1
.
b. Se(*atual)->filho[bit]
for NULL, aloca um novo nó e inicializa.
c. Move o ponteiroatual
para(*atual)->filho[bit]
. - 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.