Parcours
Infixe, préfixe et postfixe.
Parcours est une leçon C Academy gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage C Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours C Academy comprend 4 leçons au total.
Qu’est-ce qu’un parcours ?
Un parcours est une manière systématique de visiter chaque nœud d’un arbre exactement une fois.
Les trois ordres classiques du parcours en profondeur sont l’ordre infixe, l’ordre préfixe et l’ordre postfixe. Ils ne diffèrent que par le moment où le nœud courant est traité par rapport à ses sous-arbres.
Parcours infixe
Le parcours infixe visite le sous-arbre gauche, puis le nœud, puis le sous-arbre droit.
Pour un BST, il affiche les valeurs par ordre croissant, ce qui en fait le parcours le plus utile pour les arbres de recherche.
void in_order(Node *root) {
if (root == NULL) return;
in_order(root->left);
printf("%d ", root->value);
in_order(root->right);
}Parcours préfixe
Le parcours préfixe visite d’abord le nœud, puis le sous-arbre gauche et enfin le sous-arbre droit.
Il est pratique pour copier un arbre ou produire une expression préfixée, car la racine est produite avant ses enfants.
void pre_order(Node *root) {
if (root == NULL) return;
printf("%d ", root->value);
pre_order(root->left);
pre_order(root->right);
}Parcours postfixe
Le parcours postfixe visite d’abord les deux sous-arbres, puis le nœud en dernier.
Comme les enfants sont traités avant leur parent, cet ordre est exactement celui qu’il faut utiliser pour libérer un arbre : aucun nœud n’est utilisé après la suppression de ses enfants.
void post_order(Node *root) {
if (root == NULL) return;
post_order(root->left);
post_order(root->right);
printf("%d ", root->value);
}Le schéma commun
Les trois parcours en profondeur partagent la même structure : un cas de base NULL, un appel récursif sur l’enfant gauche, un appel récursif sur l’enfant droit et une étape de visite.
Seule la position de l’étape de visite détermine le nom de l’ordre.
/* visit position decides the order:
* pre : VISIT, left, right
* in : left, VISIT, right
* post : left, right, VISIT
*/L’infixe affiche les valeurs triées
Ce programme construit un petit BST et exécute un parcours infixe, illustrant la propriété qui garantit une sortie triée.
Les valeurs sont affichées de la plus petite à la plus grande, quel que soit l’ordre d’insertion.
#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;
}Comparaison des trois ordres
Pour l’arbre dont la racine vaut 10, avec 5 à gauche et 15 à droite, les sorties diffèrent :
Le parcours préfixe donne 10 5 15. L’infixe donne 5 10 15. Le postfixe donne 5 15 10. Les valeurs des nœuds sont identiques ; seul le moment de la visite change.
/* 10
* / \
* 5 15
* pre : 10 5 15
* in : 5 10 15
* post: 5 15 10
*/Parcours par niveaux
Le parcours en largeur, ou par niveaux, visite les nœuds niveau par niveau, du haut vers le bas. Il n’est pas naturellement récursif : il utilise une file.
Nous ajoutons la racine à la file, puis retirons à répétition un nœud, l’affichons et ajoutons ses enfants à la file.
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;
}
}Le parcours permet des opérations concrètes
Les parcours sont des modèles pour toute opération qui doit toucher chaque nœud, et pas seulement pour l’affichage.
Remplacez l’étape de visite par une somme des valeurs, la recherche d’un maximum ou la copie des nœuds : la même structure fera le travail.
int sum_tree(Node *root) {
if (root == NULL) return 0;
return root->value
+ sum_tree(root->left)
+ sum_tree(root->right);
}Coût d’un parcours
Chaque parcours visite chaque nœud une fois ; son temps d’exécution est donc proportionnel à n, le nombre de nœuds.
La récursion utilise une mémoire de pile proportionnelle à la hauteur de l’arbre : elle vaut log(n) lorsque l’arbre est équilibré et n dans le pire des cas.
Les trois parcours en même temps
Ce programme affiche les parcours préfixe, infixe et postfixe du même arbre afin que vous puissiez les comparer côte à côte.
Observez que seule la position de l’appel d’affichage change la séquence obtenue.
#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;
}Vérification rapide
Choisissez le parcours adapté à la tâche.
Récapitulatif
Les parcours en profondeur partagent une même structure récursive ; la position de l’étape de visite détermine l’ordre préfixe, infixe ou postfixe. Le parcours infixe d’un BST produit une sortie triée, et le parcours postfixe est l’ordre sûr pour libérer l’arbre.
Le parcours par niveaux se fait en largeur et utilise une file. Tous visitent chaque nœud une fois, en temps O(n).
Questions Fréquemment Posées
La leçon « Parcours » est-elle gratuite ?
Oui — le texte complet de « Parcours » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours C Academy, passe à CoddyKit PRO. Le cours C Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Parcours » ?
Infixe, préfixe et postfixe. Tu pratiques C Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer C Academy ?
Aucune expérience préalable n'est requise. C Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Parcours » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon C Academy ?
Oui. Chaque leçon C Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.