Alberi e grafi in C

Gli alberi e i grafi sono strutture dati non lineari usate per rappresentare dati gerarchici e dati organizzati in rete.

In questa lezione imparerà:

• Come sono strutturati gli alberi e i grafi.
• Come implementare un albero binario in C.
• Come rappresentare i grafi usando liste e matrici di adiacenza.

Che cos'è un albero?

Un albero è una struttura dati gerarchica composta da nodi.

Termini chiave:

• Radice - Il nodo più in alto.
• Padre e figlio - Nodi collegati direttamente.
• Foglia - Un nodo senza figli.

Esempio: nodo di un albero binario

In C, un nodo di un albero binario viene definito utilizzando una struct con puntatori al figlio sinistro e al figlio destro.

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

struct Node {
    int data;
    struct Node *left, *right;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

int main() {
    struct Node *root = createNode(10);
    return 0;
}

Attraversamento di un albero binario

Metodi di attraversamento:

• Inorder (LNR) - Sinistro, nodo, destro.
• Preorder (NLR) - Nodo, sinistro, destro.
• Postorder (LRN) - Sinistro, destro, nodo.

Esempio: attraversamento inorder

Questo programma esegue un attraversamento inorder di un albero binario.

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

struct Node {
    int data;
    struct Node *left, *right;
};

void inorder(struct Node *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    struct Node *root = malloc(sizeof(struct Node));
    root->data = 10;
    root->left = NULL;
    root->right = NULL;
    inorder(root);
    return 0;
}

Che cos'è un grafo?

Un grafo è un insieme di nodi (vertici) collegati da archi.

I grafi possono essere:

• Orientati - Gli archi hanno una direzione.
• Non orientati - Gli archi non hanno una direzione.

Rappresentazione dei grafi

I grafi possono essere rappresentati utilizzando:

• Matrice di adiacenza - Un array bidimensionale che rappresenta le connessioni.
• Lista di adiacenza - Un elenco in cui ogni nodo punta ai propri vicini.

Attraversamento dei grafi

Metodi di attraversamento comuni:

• Ricerca in ampiezza (BFS) - Visita tutti i vicini prima di procedere più in profondità.
• Ricerca in profondità (DFS) - Esplora il percorso più profondo possibile prima di tornare indietro.

Riepilogo

In questa lezione ha imparato:

• Come sono strutturati alberi e grafi.
• Come eseguire gli attraversamenti degli alberi.
• Come vengono rappresentati e attraversati i grafi.

Questa è la conclusione della sezione Strutture dati in C!