Como Criar uma Árvore Binária em C

Árvores binárias em C são uma excelente forma de organizar dados dinamicamente para buscas eficientes. No entanto, exigem bastante trabalho para manutenção.

Criar a Árvore Binária

Passo 1: Estruturar a Árvore

Toda árvore binária precisa de uma estrutura, mesmo que tenha apenas uma variável. Escolha um nome e use typedef para criá-la:

typedef struct student_data STUDENT_DATA;

Passo 2: Definir a Estrutura

Inclua dois ponteiros para a mesma estrutura:

struct student_data {
    int student_ID;
    int student_grade;
    STUDENT_DATA *left, *right;
};

Passo 3: Alocar Ponteiro Cabeça

Aloque um ponteiro para esta estrutura de dados, inicializando-o como NULL, para ser a cabeça da árvore:

STUDENT_DATA *students = NULL;

Adicionar à Árvore Binária

Passo 1: Alocar Ponteiros Temporários

STUDENT_DATA *new_student, *cur_student;

Passo 2: Criar Novo Elemento com malloc()

if ((new_student = malloc(sizeof(STUDENT_DATA))) == NULL) {
    abort();
}

Passo 3: Preencher Campos do Novo Elemento

new_student->student_ID = newID;
new_student->student_grade = newgrade;
new_student->left = NULL;
new_student->right = NULL;

Passo 4: Verificar se é o Primeiro Elemento

if (!students) {
    students = new_student;
    return;
}

Passo 5: Iniciar no Topo da Árvore

cur_student = students;
while (cur_student) {

Passo 6: Tratar Entradas Duplicadas

if (newID == cur_student->student_ID) {
    abort();
}

Passo 7: Inserir à Esquerda (Valor Menor)

if (newID < cur_student->student_ID) {
    if (cur_student->left == NULL) {
        cur_student->left = new_student;
        return 1;
    }
    cur_student = cur_student->left;
}

Passo 8: Inserir à Direita (Valor Maior)

} else {
    if (cur_student->right == NULL) {
        cur_student->right = new_student;
        return 1;
    }
    cur_student = cur_student->right;
}

Buscar na Árvore Binária

Passo 1: Criar Variável Temporária

STUDENT_DATA *cur_student;

Passo 2: Apontar para a Cabeça

cur_student = students_head;

Passo 3: Percorrer a Árvore

while (cur_student) {
    if (cur_student->student_ID == 15) {
        return cur_student->student_grade;
    }

Passo 4: Navegar Esquerda ou Direita

if (cur_student->student_ID < 15) {
    cur_student = cur_student->right;
} else {
    cur_student = cur_student->left;
}

Passo 5: Verificar se Não Encontrou

}
return 0;

Limpeza

Passo 1: Função Recursiva de Desalocação

Desaloque a árvore binária quando o programa terminar, pois nem todos os sistemas operacionais fazem isso automaticamente. Use uma função recursiva:

void deallocate_binary_tree(STUDENT_DATA *tree) {

Passo 2: Caso Base

if (!tree) return;

Passo 3: Desalocar Subárvores Recursivamente

deallocate_binary_tree(tree->left);
deallocate_binary_tree(tree->right);

Passo 4: Liberar Elemento Atual

free(tree);
}

Dica

Busca e inserção em árvores binárias também podem ser feitas usando recursão. Isso torna o código mais fácil de escrever e manter, embora um pouco mais difícil de entender até você se acostumar. É comum criar uma árvore binária que contenha apenas ponteiros para uma segunda estrutura de dados em C, geralmente um array ou lista encadeada, onde os dados reais residem. Cada árvore binária atua como um índice para buscar rapidamente um único campo dos dados da lista.

Aviso

Excluir um nó de uma árvore binária é um algoritmo muito complexo em C, mas em muitos usos de árvores binárias, os elementos nunca são excluídos.

• Como Sublinhar Texto em HTML
• Como Cancelar Seu Lance no eBay