Come Creare un Albero Binario in C

Gli alberi binari in C sono un'ottima struttura per organizzare dinamicamente i dati per una ricerca efficiente, anche se richiedono un certo impegno per la manutenzione.

Creazione dell'Albero Binario

Passo 1: Definire la Struttura

Ogni albero binario necessita di una struttura, anche se contiene una sola variabile. Scegli un nome e usa typedef per crearla:

typedef struct student_data STUDENT_DATA;

Passo 2: Definire i Campi della Struttura

Includi due puntatori alla stessa struttura per i nodi sinistro e destro:

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

Passo 3: Inizializzare il Puntatore alla Radice

Alloca un puntatore a questa struttura dati, inizializzandolo a NULL, che fungerà da testa dell'albero:

STUDENT_DATA *students = NULL;

Aggiunta di Elementi all'Albero Binario

Passo 1: Allocare Puntatori Temporanei

STUDENT_DATA *new_student, *cur_student;

Passo 2: Creare un Nuovo Nodo con malloc()

if ((new_student = malloc(sizeof(STUDENT_DATA))) == NULL) {
    abort(); // Gestione errore allocazione
}

Passo 3: Popolare i Campi del Nuovo Nodo

new_student->student_ID = newID;
new_student->student_grade = newGrade; // Corretto: era student_size
new_student->left = NULL;
new_student->right = NULL;

Passo 4: Gestire il Primo Elemento

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

Passo 5: Traversare l'Albero

cur_student = students;
while (cur_student) {

Passo 6: Gestire Duplicati

if (newID == cur_student->student_ID) {
    abort(); // Valore duplicato non ammesso
}

Passo 7: Inserire a Sinistra

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: Inserire a Destra

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

Ricerca nell'Albero Binario

Passo 1: Creare Puntatore Temporaneo

STUDENT_DATA *cur_student;

Passo 2: Impostare sulla Radice

cur_student = students; // Corretto: era students_head

Passo 3: Ciclo di Ricerca

while (cur_student) {
    if (cur_student->student_ID == targetID) {
        return cur_student->student_grade; // Trovato
    }

Passo 4: Navigare nell'Albero

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

Passo 5: Elemento Non Trovato

return 0; // Non trovato

Pulizia della Memoria

Dealloca l'albero binario alla fine del programma, poiché non tutti i sistemi operativi lo fanno automaticamente. Il metodo migliore è una funzione ricorsiva:

Passo 1: Funzione di Deallocazione

void deallocate_binary_tree(STUDENT_DATA *tree) {

Passo 2: Caso Base

if (!tree) return;

Passo 3: Deallocazione Ricorsiva dei Sottoalberi

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

Passo 4: Liberare il Nodo Corrente

free(tree);
}

Suggerimento

La ricerca e l'inserimento negli alberi binari possono essere implementati anche ricorsivamente. Questo rende il codice più semplice da scrivere e manutenere, anche se inizialmente può essere meno intuitivo. È comune creare un albero binario che contenga solo puntatori a una seconda struttura dati C, spesso un array o una lista collegata, dove risiedono i dati effettivi. Ogni albero binario funge da indice per ricercare rapidamente un singolo campo dei dati della lista.

Avvertenza

L'eliminazione da un albero binario è un algoritmo molto complesso in C, ma in molti casi d'uso degli alberi binari, gli elementi non vengono mai eliminati.