Attraversamenti
In-order, pre-order, post-order.
Attraversamenti è una lezione C Academy gratuita su CoddyKit. Questa è la lezione 3 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'è una visita?
Una visita è un modo sistematico per visitare ogni nodo di un albero esattamente una volta.
I tre ordini classici della visita in profondità sono in-order, pre-order e post-order. Differiscono soltanto da quando viene elaborato il nodo corrente rispetto ai suoi sottoalberi.
Visita in-order
La visita in-order elabora prima il sottoalbero sinistro, poi il nodo e infine il sottoalbero destro.
In un BST stampa i valori in ordine crescente, perciò è la visita più utile per gli alberi di ricerca.
void in_order(Node *root) {
if (root == NULL) return;
in_order(root->left);
printf("%d ", root->value);
in_order(root->right);
}Visita pre-order
La visita pre-order elabora prima il nodo, poi il sottoalbero sinistro e infine il sottoalbero destro.
È utile per copiare un albero o produrre un'espressione prefissa, perché la radice viene emessa prima dei suoi figli.
void pre_order(Node *root) {
if (root == NULL) return;
printf("%d ", root->value);
pre_order(root->left);
pre_order(root->right);
}Visita post-order
La visita post-order elabora prima entrambi i sottoalberi e il nodo per ultimo.
Poiché i figli vengono gestiti prima del padre, questo è esattamente l'ordine necessario per liberare un albero: un nodo non viene mai utilizzato dopo che i suoi figli sono stati eliminati.
void post_order(Node *root) {
if (root == NULL) return;
post_order(root->left);
post_order(root->right);
printf("%d ", root->value);
}Lo schema comune
Tutte e tre le visite in profondità condividono la stessa struttura: un caso base NULL, una chiamata ricorsiva sul figlio sinistro, una chiamata ricorsiva sul figlio destro e un'operazione di visita.
È soltanto la posizione dell'operazione di visita a determinare il nome dell'ordine.
/* visit position decides the order:
* pre : VISIT, left, right
* in : left, VISIT, right
* post : left, right, VISIT
*/In-order stampa in ordine
Questo programma costruisce un piccolo BST ed esegue una visita in-order, mostrando la proprietà dell'output ordinato.
I valori vengono restituiti dal più piccolo al più grande, indipendentemente dall'ordine di inserimento.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
if(!r) return cn(v);
if(v<r->value) r->left=insert(r->left,v);
else if(v>r->value) r->right=insert(r->right,v);
return r;
}
void in_order(Node *r){ if(!r) return; in_order(r->left); printf("%d ", r->value); in_order(r->right); }
int main(void){
Node *root=NULL;
int d[]={10,5,15,3,7,12};
for(int i=0;i<6;i++) root=insert(root,d[i]);
in_order(root);
printf("\n");
return 0;
}Confronto tra i tre ordini
Per l'albero con radice 10, figlio sinistro 5 e figlio destro 15, gli output differiscono:
Il pre-order produce 10 5 15. L'in-order produce 5 10 15. Il post-order produce 5 15 10. I valori dei nodi sono gli stessi; cambia soltanto il momento della visita.
/* 10
* / \
* 5 15
* pre : 10 5 15
* in : 5 10 15
* post: 5 15 10
*/Visita level-order
La visita breadth-first, o level-order, elabora i nodi livello per livello, dall'alto verso il basso. Non è naturalmente ricorsiva: utilizza una coda.
Si inserisce la radice nella coda, quindi si estrae ripetutamente un nodo, lo si stampa e si inseriscono nella coda i suoi figli.
void level_order(Node *root) {
if (!root) return;
Node *queue[100];
int head = 0, tail = 0;
queue[tail++] = root;
while (head < tail) {
Node *n = queue[head++];
printf("%d ", n->value);
if (n->left) queue[tail++] = n->left;
if (n->right) queue[tail++] = n->right;
}
}La visita svolge il lavoro reale
Le visite sono modelli per qualsiasi operazione che debba raggiungere ogni nodo, non solo per la stampa.
Sostituendo l'operazione di visita con la somma dei valori, la ricerca del massimo o la copia dei nodi, la stessa struttura svolge il compito.
int sum_tree(Node *root) {
if (root == NULL) return 0;
return root->value
+ sum_tree(root->left)
+ sum_tree(root->right);
}Costo di una visita
Ogni visita raggiunge ciascun nodo una volta, quindi viene eseguita in un tempo proporzionale a n, il numero di nodi.
La ricorsione utilizza uno spazio nello stack proporzionale all'altezza dell'albero, che è log(n) quando l'albero è bilanciato e n nel caso peggiore.
Tutti e tre insieme
Questo programma stampa il pre-order, l'in-order e il post-order dello stesso albero, così potete confrontarli affiancati.
Osservate come soltanto la posizione della chiamata di stampa modifichi la sequenza risultante.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
void pre(Node *r){ if(!r) return; printf("%d ", r->value); pre(r->left); pre(r->right); }
void ino(Node *r){ if(!r) return; ino(r->left); printf("%d ", r->value); ino(r->right); }
void post(Node *r){ if(!r) return; post(r->left); post(r->right); printf("%d ", r->value); }
int main(void){
Node *root = cn(10);
root->left = cn(5); root->right = cn(15);
pre(root); printf("\n");
ino(root); printf("\n");
post(root); printf("\n");
return 0;
}Verifica rapida
Scegliete la visita più adatta allo scopo.
Riepilogo
Le visite in profondità condividono la stessa struttura ricorsiva; la posizione dell'operazione di visita determina l'ordine pre-, in- o post-order. La visita in-order di un BST produce un output ordinato, mentre il post-order è l'ordine sicuro per liberare la memoria.
La visita level-order è breadth-first e utilizza una coda. Tutte visitano ogni nodo una volta, in tempo O(n).
Domande Frequenti
La lezione «Attraversamenti» è gratuita?
Sì — il testo completo di «Attraversamenti» è 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 «Attraversamenti»?
In-order, pre-order, post-order. 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 3 di 4.
Quanto tempo richiede la lezione «Attraversamenti»?
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.