Implementar, em linguagem C, o algoritmo de busca em uma árvore digital binária.

Passo 1

Beleza! O enunciado pede para a gente “Implementar, em linguagem C, o algoritmo de busca em uma árvore digital binária.” Isso cai na matéria de estruturas de dados (mais especificamente em tries binárias ou árvores digitais), e a gente vai usar:
  • Conceito de árvore (ponteiros para filhos esquerdo e direito)
  • Operações bit a bit em C para separar cada bit da chave
  • Laços para percorrer do bit mais significativo (MSB) até o menos significativo (LSB)

Passo 2

Vamos começar definindo a estrutura do nó. Aqui cada nó tem dois ponteiros (filho 0 e filho 1) e uma flag que indica se ali terminou uma chave inserida.
#define BITS_KEY 32  // assumindo chave de 32 bits

typedef struct TrieNode {
    int isEnd;                // 1 se esse nó marca fim de uma chave válida
    struct TrieNode* child[2]; // child[0] = ramo para bit 0, child[1] = ramo para bit 1
} TrieNode;

Passo 3

Agora a função de busca. A ideia é: dado um ponteiro root e uma chave key, a gente percorre bit a bit, do MSB (bit 31) até o LSB (bit 0). Em cada nível, escolhe child[bit]. Se em algum momento não existir nó, concluímos que a chave não está na árvore.
TrieNode* search(TrieNode* root, unsigned int key) {
    TrieNode* curr = root;
    // percorre do bit 31 até o bit 0
    for (int i = BITS_KEY-1; i >= 0; i--) {
        if (!curr) return NULL;  // ramo não existe → não achou
        int bit = (key >> i) & 1; // extrai o i-ésimo bit: (key >> i) & 1
        curr = curr->child[bit];
    }
    // se terminou os bits e curr não é NULL, checa se é fim de chave
    if (curr && curr->isEnd)
        return curr;  // achou a chave
    return NULL;      // percorreu tudo mas não era fim de chave
}

Passo 4

Teoria em jogo:
  • Em uma árvore digital binária (ou trie binária), cada nível corresponde a um bit da chave.
  • Você decide ramificar para a esquerda (bit 0) ou direita (bit 1).
  • A operação (key >> i) & 1 desloca os bits de key para a direita em i posições, depois faz AND com 1 para isolar só aquele bit.
  • A busca leva tempo O(W), com W sendo número de bits da chave (aqui 32).

Passo 5

Se quiser usar na prática, basta chamar search(root, minhaChave). Se o retorno for NULL, não existe; senão, você recebe o ponteiro do nó onde isEnd == 1.

Resposta

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

#define BITS_KEY 32

typedef struct TrieNode {
    int isEnd;
    struct TrieNode* child[2];
} TrieNode;

// cria nó novo
TrieNode* newNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->isEnd = 0;
    node->child[0] = node->child[1] = NULL;
    return node;
}

// busca na trie binária
TrieNode* search(TrieNode* root, unsigned int key) {
    TrieNode* curr = root;
    for (int i = BITS_KEY - 1; i >= 0; i--) {
        if (!curr) return NULL;
        int bit = (key >> i) & 1;
        curr = curr->child[bit];
    }
    if (curr && curr->isEnd)
        return curr;
    return NULL;
}

// exemplo de inserção só pra testar busca
void insert(TrieNode* root, unsigned int key) {
    TrieNode* curr = root;
    for (int i = BITS_KEY - 1; i >= 0; i--) {
        int bit = (key >> i) & 1;
        if (!curr->child[bit])
            curr->child[bit] = newNode();
        curr = curr->child[bit];
    }
    curr->isEnd = 1;
}

int main() {
    TrieNode* root = newNode();
    insert(root, 42);
    insert(root, 100);

    unsigned int x = 42;
    if (search(root, x))
        printf("Chave %u encontrada!\n", x);
    else
        printf("Chave %u nao existe.\n", x);

    return 0;
}

Exercícios relacionados