Nodi e struttura degli alberi
Modelli un nodo con i puntatori.
Nodi e struttura degli alberi è una lezione C Academy gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento C Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso C Academy include 4 lezioni in totale.
Che cos'è un albero binario
Un albero binario è una struttura gerarchica in cui ogni nodo contiene un valore e collegamenti verso al massimo due figli: un figlio sinistro e un figlio destro.
Il nodo più in alto è la radice. I nodi senza figli sono le foglie. Questa struttura rende gli alberi binari adatti alla ricerca e all'ordinamento rapidi, nonché all'elaborazione ricorsiva.
La struct del nodo
In C modelliamo un nodo con una struct che contiene i dati e due puntatori autoreferenziali.
Ogni puntatore punta a un altro Node oppure a NULL quando non esiste un figlio su quel lato.
struct Node {
int value;
struct Node *left;
struct Node *right;
};Perché usare puntatori autoreferenziali
Un nodo non può contenere al proprio interno un altro nodo completo per valore, perché ciò richiederebbe una quantità infinita di memoria. Contiene invece puntatori ai propri figli.
I puntatori hanno dimensione fissa, quindi la struct mantiene una dimensione nota pur potendo collegarsi ad altri nodi nell'heap.
struct Node {
int value;
struct Node *left; /* 8 bytes on 64-bit */
struct Node *right; /* 8 bytes on 64-bit */
};Un typedef per comodità
Scrivere struct Node ovunque è scomodo. Un typedef consente di scrivere semplicemente Node.
Il tag è comunque necessario all'interno della struct, perché in quel punto il tipo non è ancora completamente definito.
typedef struct Node {
int value;
struct Node *left;
struct Node *right;
} Node;Allocazione di un Node
I nodi risiedono nell'heap e vengono creati con malloc. Impostiamo il valore e inizializziamo entrambi i puntatori ai figli su NULL.
Controlli sempre che malloc non abbia restituito NULL prima di utilizzare la memoria.
Node *create_node(int value) {
Node *n = malloc(sizeof(Node));
if (n == NULL) return NULL;
n->value = value;
n->left = NULL;
n->right = NULL;
return n;
}Creare manualmente un piccolo albero
Per comprendere i collegamenti, colleghiamo manualmente tre nodi: una radice con due figli.
Questo programma crea l'albero e stampa i valori; normalmente, poi, lo libereremmo (come illustrato più avanti).
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node *left;
struct Node *right;
} Node;
Node *create_node(int v) {
Node *n = malloc(sizeof(Node));
n->value = v; n->left = NULL; n->right = NULL;
return n;
}
int main(void) {
Node *root = create_node(10);
root->left = create_node(5);
root->right = create_node(15);
printf("%d %d %d\n", root->left->value, root->value, root->right->value);
return 0;
}Raggiungere i nipoti
Si attraversa l'albero concatenando l'operatore freccia. root->left->right scende al figlio sinistro e poi al suo figlio destro.
Prima di seguire un puntatore, si assicuri che non sia NULL, altrimenti il programma terminerà con un crash.
/* root
* \
* right (15)
* \
* right->right (20)
*/
if (root->right != NULL && root->right->right != NULL)
printf("%d\n", root->right->right->value);Conteggio ricorsivo dei nodi
La ricorsione si adatta naturalmente agli alberi. Per contare i nodi, un sottoalbero vuoto contiene zero nodi; altrimenti si conta il nodo corrente più entrambi i sottoalberi.
Il controllo su NULL è il caso base che arresta la ricorsione.
int count_nodes(Node *root) {
if (root == NULL) return 0;
return 1 + count_nodes(root->left)
+ count_nodes(root->right);
}Misurare l'altezza
L'altezza di un albero è il percorso più lungo dalla radice a una foglia, misurato in archi.
Prendiamo l'altezza maggiore tra i due sottoalberi e aggiungiamo uno. A un albero vuoto assegniamo altezza -1, così un albero con un solo nodo ha altezza 0.
int height(Node *root) {
if (root == NULL) return -1;
int l = height(root->left);
int r = height(root->right);
return 1 + (l > r ? l : r);
}Individuare le foglie
Una foglia è un nodo senza figli: sia left sia right sono NULL.
Questo piccolo helper è utile in molte routine di attraversamento e conteggio.
int is_leaf(Node *n) {
return n != NULL && n->left == NULL && n->right == NULL;
}Mettere la struttura al lavoro
Qui viene creato un piccolo albero e ne vengono riportati il numero di nodi e l'altezza utilizzando gli helper ricorsivi.
Noti che gli helper non presuppongono una forma fissa: funzionano con qualsiasi albero perché la ricorsione segue i puntatori effettivi.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *nn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
int count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }
int height(Node *r){ if(!r) return -1; int l=height(r->left),x=height(r->right); return 1+(l>x?l:x); }
int main(void){
Node *root = nn(10);
root->left = nn(5); root->right = nn(15);
root->left->left = nn(2);
printf("nodes=%d height=%d\n", count(root), height(root));
return 0;
}Controllo rapido
Verifichi la propria comprensione della struttura dei nodi.
Riepilogo
Un nodo di un albero binario contiene un valore e due puntatori autoreferenziali (left, right), impostati su NULL quando non sono presenti.
Allochiamo i nodi con malloc, li colleghiamo manualmente e li elaboriamo ricorsivamente. Il controllo su NULL è sempre il caso base per il conteggio, il calcolo dell'altezza e il controllo delle foglie.
Domande Frequenti
La lezione «Nodi e struttura degli alberi» è gratuita?
Sì — il testo completo di «Nodi e struttura degli alberi» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso C Academy, passa a CoddyKit PRO. Il corso C Academy include 4 lezioni in totale.
Cosa imparerò in «Nodi e struttura degli alberi»?
Modelli un nodo con i puntatori. Eserciti C Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare C Academy?
Non è richiesta alcuna esperienza precedente. C Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Nodi e struttura degli alberi»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione C Academy?
Sì. Ogni lezione C Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Nodi e struttura degli alberi
- Inserire in un BST
- Attraversamenti
- Cercare e liberare