🚀 Nuova versione beta disponibile! Feedback o problemi? Contattaci

Alberi in C

Codegrind Team•Aug 23 2024

Gli alberi sono una struttura dati fondamentale in C, utilizzata per rappresentare gerarchie e organizzare dati complessi. Gli alberi sono composti da nodi collegati in modo tale da formare una struttura a ramificazione, con un nodo radice e vari nodi figli. In questa guida, esploreremo come implementare alberi in C, concentrandoci in particolare sugli alberi binari, una delle forme più comuni di alberi.

Cos’è un Albero?

Un albero è una struttura dati non lineare composta da nodi. Ogni nodo in un albero contiene un dato e riferimenti (puntatori) ai nodi figli. Il nodo più in alto della gerarchia è chiamato radice, e i nodi senza figli sono chiamati foglie.

Tipi di Alberi

  • Albero Binario: Ogni nodo ha al massimo due figli, detti figlio sinistro e figlio destro.
  • Albero Bilanciato: Un albero in cui la differenza di profondità tra i sottoalberi è minima.
  • Albero di Ricerca Binario (BST): Un albero binario in cui per ogni nodo, i valori nel sottoalbero sinistro sono inferiori al nodo stesso, e i valori nel sottoalbero destro sono superiori.

Implementazione di un Albero Binario

Definizione della Struttura Nodo

Iniziamo creando una struttura per rappresentare un nodo in un albero binario.

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

// Definizione della struttura del nodo
struct Nodo {
    int dato;
    struct Nodo* sinistro;
    struct Nodo* destro;
};

Ogni nodo contiene un intero dato e due puntatori, sinistro e destro, che puntano ai nodi figli.

Creazione di un Nuovo Nodo

Per creare un nuovo nodo, possiamo definire una funzione che alloca memoria per un nodo e inizializza i suoi campi.

struct Nodo* nuovo_nodo(int dato) {
    struct Nodo* nodo = (struct Nodo*)malloc(sizeof(struct Nodo));
    nodo->dato = dato;
    nodo->sinistro = NULL;
    nodo->destro = NULL;
    return nodo;
}

Inserimento in un Albero Binario di Ricerca

L’inserimento in un albero binario di ricerca (BST) segue una logica specifica: i valori minori vengono inseriti nel sottoalbero sinistro e i valori maggiori nel sottoalbero destro.

struct Nodo* inserisci(struct Nodo* nodo, int dato) {
    if (nodo == NULL) return nuovo_nodo(dato);

    if (dato < nodo->dato)
        nodo->sinistro = inserisci(nodo->sinistro, dato);
    else if (dato > nodo->dato)
        nodo->destro = inserisci(nodo->destro, dato);

    return nodo;
}

Esempio Completo di Inserimento

int main() {
    struct Nodo* radice = NULL;
    radice = inserisci(radice, 50);
    inserisci(radice, 30);
    inserisci(radice, 20);
    inserisci(radice, 40);
    inserisci(radice, 70);
    inserisci(radice, 60);
    inserisci(radice, 80);

    return 0;
}

Traversamento di un Albero

Il traversamento di un albero è il processo di visitare tutti i nodi di un albero in un ordine specifico. I metodi di traversamento comuni sono:

1. Inorder (Simmetrico): Visita il sottoalbero sinistro, poi il nodo corrente, e infine il sottoalbero destro.

void inorder(struct Nodo* nodo) {
    if (nodo != NULL) {
        inorder(nodo->sinistro);
        printf("%d ", nodo->dato);
        inorder(nodo->destro);
    }
}

2. Preorder (Anticipato): Visita il nodo corrente prima dei suoi figli.

void preorder(struct Nodo* nodo) {
    if (nodo != NULL) {
        printf("%d ", nodo->dato);
        preorder(nodo->sinistro);
        preorder(nodo->destro);
    }
}

3. Postorder (Posticipato): Visita il nodo corrente dopo aver visitato i suoi figli.

void postorder(struct Nodo* nodo) {
    if (nodo != NULL) {
        postorder(nodo->sinistro);
        postorder(nodo->destro);
        printf("%d ", nodo->dato);
    }
}

Esempio Completo di Traversamento

int main() {
    struct Nodo* radice = NULL;
    radice = inserisci(radice, 50);
    inserisci(radice, 30);
    inserisci(radice, 20);
    inserisci(radice, 40);
    inserisci(radice, 70);
    inserisci(radice, 60);
    inserisci(radice, 80);

    printf("Traversamento Inorder: ");
    inorder(radice);
    printf("\n");

    printf("Traversamento Preorder: ");
    preorder(radice);
    printf("\n");

    printf("Traversamento Postorder: ");
    postorder(radice);
    printf("\n");

    return 0;
}

Uscita:

Traversamento Inorder: 20 30 40 50 60 70 80
Traversamento Preorder: 50 30 20 40 70 60 80
Traversamento Postorder: 20 40 30 60 80 70 50

Ricerca in un Albero Binario di Ricerca

La ricerca in un albero binario di ricerca è efficiente grazie alla sua struttura. Si procede ricorsivamente confrontando il valore cercato con il nodo corrente e muovendosi verso il sottoalbero sinistro o destro a seconda del confronto.

struct Nodo* cerca(struct Nodo* radice, int dato) {
    if (radice == NULL || radice->dato == dato)
        return radice;

    if (dato < radice->dato)
        return cerca(radice->sinistro, dato);

    return cerca(radice->destro, dato);
}

Cancellazione in un Albero Binario di Ricerca

La cancellazione di un nodo in un albero binario di ricerca è più complessa perché richiede il mantenimento della proprietà dell’albero binario di ricerca. Esistono tre casi principali da considerare:

  1. Nodo senza figli (foglia): Rimuovere semplicemente il nodo.
  2. Nodo con un figlio: Sostituire il nodo con il suo unico figlio.
  3. Nodo con due figli: Trovare il successore in-order (il nodo con il valore più piccolo nel sottoalbero destro) e sostituire il nodo da eliminare con il successore.

Esempio di Funzione di Cancellazione

struct Nodo* min_valore_nodo(struct Nodo* nodo) {
    struct Nodo* corrente = nodo;
    while (corrente && corrente->sinistro != NULL)
        corrente = corrente->sinistro;

    return corrente;
}

struct Nodo* cancella_nodo(struct Nodo* radice, int dato) {
    if (radice == NULL) return radice;

    if (dato < radice->dato)
        radice->sinistro = cancella_nodo(radice->sinistro, dato);
    else if (dato > radice->dato)
        radice->destro = cancella_nodo(radice->destro, dato);
    else {
        if (radice->sinistro == NULL) {
            struct Nodo* temp = radice->destro;
            free(radice);
            return temp;
        } else if (radice->destro == NULL) {
            struct Nodo* temp = radice->sinistro;
            free(radice);
            return temp;
        }

        struct Nodo* temp = min_valore_nodo(radice->destro);
        radice->dato = temp->dato;
        radice->destro = cancella_nodo(radice->destro, temp->dato);
    }

    return radice;
}

Vantaggi e Svantaggi degli Alberi

Vantaggi:

  • Organizzazione Gerarchica: Ideale per rappresentare gerarchie come directory di file o strutture organizzative.
  • Ricerca Efficiente: Gli alberi binari di ricerca permettono ricerche, inserimenti e cancellazioni efficienti (O(log n) nel caso medio).

Svantaggi:

  • Complessità: Implementare alberi richiede una buona comprensione della gestione dei puntatori e della ricorsione.
  • Degradazione in Lista: Un albero binario di ricerca sbilanciato può degenerare in una lista, riducendo l’efficienza a O(n).

Conclusioni

Gli alberi

, e in particolare gli alberi binari di ricerca, sono una struttura dati versatile e potente che trova applicazione in numerosi problemi di programmazione. Capire come implementare, attraversare e manipolare alberi in C è fondamentale per affrontare problemi complessi che richiedono una gestione efficiente dei dati. Con un’implementazione corretta, gli alberi offrono vantaggi significativi in termini di organizzazione e accesso ai dati.

PrecedenteStack e QueueSuccessivoGrafi