Chapitre 1 · 6 h
Arbres binaires
Racine, nœud, feuille, hauteur ; représentations ; parcours préfixe, infixe, suffixe et en largeur ; arbre d'expression.
Comment un compilateur sait-il que 3 + 4 * 2 vaut 11 et non 14 ? Pas en appliquant des règles
de priorité au moment du calcul : en construisant un arbre où la multiplication est plus bas
que l'addition. Une fois l'arbre bâti, la priorité n'existe plus — elle est devenue de la
structure, et l'évaluation se fait par une récursion de trois lignes.
Les arbres sont partout dès qu'on modélise une hiérarchie : arborescence de fichiers du chapitre 7 du cours de systèmes, page web, arbre de décision de la borne inférieure des tris, arbre d'appels du chapitre 4. Ce chapitre les définit et donne les quatre façons de les parcourir ; le suivant montrera ce qu'ils font gagner.
Vocabulaire
Un arbre est un ensemble de nœuds reliés par des arêtes, tel qu'un nœud unique — la racine — n'a pas de parent, et que tout autre nœud a exactement un parent. Cette seconde condition est ce qui distingue un arbre d'un graphe quelconque, et elle interdit les cycles.
● racine, profondeur 0 ┌──┴──┐ ● ● profondeur 1 ┌──┴─┐ │ ● ● ● profondeur 2 └─┐ ● profondeur 3 → hauteur de l'arbre = 3| Terme | Définition |
|---|---|
| Feuille | nœud sans enfant |
| Nœud interne | nœud ayant au moins un enfant |
| Profondeur d'un nœud | nombre d'arêtes depuis la racine |
| Hauteur de l'arbre | profondeur maximale |
| Taille | nombre de nœuds |
| Sous-arbre | un nœud et toute sa descendance |
Un arbre binaire est un arbre où chaque nœud a au plus deux enfants, distingués comme gauche et droit — et l'ordre compte : un enfant unique à gauche ne donne pas le même arbre qu'à droite.
Ici encore, la définition est récursive : un arbre binaire est vide, ou bien une racine portant deux arbres binaires. Toutes les fonctions du chapitre s'écriront donc en trois lignes, selon le patron du bloc I — cas de base sur l'arbre vide, appel sur chaque sous-arbre.
Hauteur et taille : l'inégalité qui fonde tout
Un arbre binaire de hauteur contient au moins nœuds — le cas d'une chaîne, un enfant par niveau — et au plus — le cas de l'arbre parfait, tous les niveaux remplis.
En inversant, la hauteur d'un arbre de nœuds vérifie :
Tout le bloc IV tient dans cet encadrement. Un arbre équilibré a une hauteur en ; un arbre dégénéré a une hauteur en , et il n'est plus qu'une liste chaînée déguisée. Comme la plupart des opérations coûtent , l'écart entre les deux est exactement celui qui séparait le bon et le mauvais pivot du chapitre 3.
Deux représentations
Par chaînage. Un nœud est une cellule avec une valeur et deux pointeurs. C'est la cellule du chapitre 5, avec un lien de plus — et c'est bien ainsi qu'il faut voir la progression du semestre : un lien donne une liste, deux donnent un arbre, un nombre quelconque donnera un graphe.
Par tableau. Pour un arbre complet — tous les niveaux remplis sauf peut-être le dernier, comblé de gauche à droite — on peut se passer de pointeurs :
indice 0 1 2 3 4 5 6 ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐ │ A │ B │ C │ D │ E │ F │ G │ └─────┴─────┴─────┴─────┴─────┴─────┴─────┘ enfants de i : 2i+1 et 2i+2 parent de i : (i−1) / 2Aucun pointeur, une mémoire parfaitement contiguë — donc les bénéfices de cache du chapitre 5 — et la navigation par arithmétique. La contrepartie est stricte : cela ne fonctionne que si l'arbre reste complet, faute de quoi le tableau se troue. C'est exactement la représentation du tas au chapitre suivant, et c'est ce qui explique son efficacité.
Les quatre parcours
Un parcours visite tous les nœuds une fois. Il y en a quatre, et il faut les connaître par ce qu'ils produisent, pas seulement par leur nom.
Les trois premiers sont des parcours en profondeur, et leur code est identique à une ligne près :
préfixe(A) infixe(A) suffixe(A) si A vide, sortir si A vide, sortir si A vide, sortir VISITER(A) infixe(A.gauche) suffixe(A.gauche) préfixe(A.gauche) VISITER(A) suffixe(A.droit) préfixe(A.droit) infixe(A.droit) VISITER(A)C'est la position de la visite qui change, et rien d'autre. Sur cet arbre :
+ ┌──┴──┐ 3 × ┌──┴──┐ 4 2| Parcours | Résultat | Ce que c'est |
|---|---|---|
| Préfixe | + 3 × 4 2 | notation polonaise |
| Infixe | 3 + 4 × 2 | notation usuelle |
| Suffixe | 3 4 2 × + | notation postfixée du chapitre 6 |
Le quatrième est le parcours en largeur : on visite niveau par niveau, de gauche à droite,
soit + 3 × 4 2 ici. Il ne s'écrit pas récursivement — il emploie une file, exactement
celle du chapitre 6 : on enfile la racine, puis tant que la file n'est pas vide on défile un
nœud, on le visite, et on enfile ses deux enfants.
Et si l'on remplace cette file par une pile, on obtient le parcours en profondeur préfixe. Le code est le même à un mot près, et c'est la remarque annoncée au chapitre précédent : la structure choisie décide de l'ordre de visite.
Quiz · 1 question
Un parcours infixe d'un arbre binaire de recherche produit une suite triée. Pourquoi, et qu'obtient-on par un parcours suffixe du même arbre ?
- Parce que l'infixe visite les nœuds par valeur croissante ; le suffixe donne la même suite en ordre inverse — ordre croissant puis inverse
- Parce que l'infixe visite tout le sous-arbre gauche — dont les valeurs sont plus petites — puis le nœud, puis le sous-arbre droit ; le suffixe ne donne AUCUN ordre particulier sur les valeurs, il rend les enfants avant leurs parents — conséquence de l'invariant
- Parce que l'arbre a été construit dans l'ordre d'insertion, qui était trié — ordre d'insertion
Réponse : C'est une conséquence directe de l'invariant du chapitre suivant : tout le sous-arbre gauche est inférieur au nœud, tout le sous-arbre droit lui est supérieur. Visiter gauche, puis le nœud, puis droite énumère donc les valeurs dans l'ordre croissant — quel que soit l'ordre d'insertion, et sans aucun tri. Le suffixe, lui, visite les deux enfants AVANT leur parent : il ne produit aucun ordre sur les valeurs, mais il garantit qu'un nœud n'est traité qu'une fois sa descendance traitée. C'est exactement ce qu'il faut pour libérer un arbre en mémoire — on ne peut pas libérer un nœud avant ses enfants, sous peine de perdre les pointeurs qui y menaient — et pour évaluer un arbre d'expression, dont les opérandes doivent être calculés avant l'opération. Pour obtenir l'ordre décroissant, on inverse l'infixe : droite, nœud, gauche.
L'arbre d'expression
C'est l'application qui justifie le chapitre, et elle referme la boucle avec le chapitre 6.
Dans un arbre d'expression, les feuilles portent les opérandes et les nœuds internes les
opérateurs. Sa construction résout la question des priorités une fois pour toutes : dans
3 + 4 × 2, la multiplication devient un sous-arbre de l'addition, donc elle sera évaluée
avant, sans qu'aucune règle de priorité n'intervienne à l'évaluation.
L'évaluation elle-même est une récursion suffixe de quatre lignes :
fonction évaluer(A) si A est une feuille alors retourner sa valeur g ← évaluer(A.gauche) d ← évaluer(A.droit) retourner appliquer(A.opérateur, g, d)Les deux appels doivent précéder l'application : c'est un parcours suffixe, et c'est pourquoi la notation postfixée du chapitre 6 s'évaluait si simplement à la pile. Les deux mécanismes sont le même : la pile de l'évaluateur postfixé est la pile d'appels de cette récursion.
Un compilateur fait exactement ce chemin. Il lit le texte, construit l'arbre — c'est l'analyse
syntaxique — puis le parcourt pour produire les instructions machine du chapitre 6
d'architecture, en émettant les opérandes avant l'opération. La suite d'instructions
add $t0, $t1, $t2 que vous y écriviez à la main est la sortie d'un parcours suffixe.
Quiz · 1 question
On veut afficher les nœuds d'un arbre niveau par niveau, de gauche à droite. Quelle structure employer, et pourquoi le parcours récursif habituel ne convient-il pas ?
- Une pile : c'est ce qu'utilise déjà la récursion, il suffit de la rendre explicite — une pile
- Une FILE : on enfile la racine, puis on défile un nœud, on le visite et on enfile ses enfants. La récursion descend en profondeur avant de passer au frère, elle ne peut donc pas produire un ordre par niveaux — une file
- Un tableau trié par profondeur, calculé en deux passes — deux passes
Réponse : La récursion suit la pile d'appels : elle plonge dans le sous-arbre gauche jusqu'aux feuilles avant de toucher au sous-arbre droit. C'est exactement l'inverse d'un parcours par niveaux, qui demande de traiter tous les nœuds de profondeur k avant ceux de profondeur k+1. La FILE donne ce comportement gratuitement : quand on défile un nœud de profondeur k, ses enfants sont ajoutés DERRIÈRE tous les nœuds de profondeur k encore en attente, donc ils ne seront traités qu'après eux. Remplacer cette file par une pile dans le même code produit un parcours en profondeur préfixe — c'est le meilleur exemple du semestre de ce que le choix d'une structure décide à lui seul.
À vous
L'exercice construit un arbre d'expression, puis met en évidence que les trois parcours en profondeur ne diffèrent que d'une ligne : vous écrirez une seule fonction paramétrée par la position de la visite, et vous obtiendrez les trois notations.
Ensuite l'évaluation, puis le parcours en largeur à la file — et enfin la manipulation qui convainc : remplacer la file par une pile dans le même code, et constater que le parcours devient un parcours en profondeur.
Le squelette contient aussi le calcul de la hauteur et de la taille, deux récursions de deux lignes qui servent d'échauffement, et dont vous vérifierez qu'elles respectent l'encadrement posé plus haut.
Exercice de code
Écrivez les trois parcours en une fonction, évaluez l'arbre, puis échangez file et pile.
Point de départ
const noeud = (valeur, gauche = null, droit = null) => ({ valeur, gauche, droit });
// L'arbre de 3 + 4 * 2 : la multiplication est PLUS BAS que l'addition,
// donc elle sera évaluée avant. La priorité est devenue de la structure.
const EXPR = noeud("+", noeud(3), noeud("*", noeud(4), noeud(2)));
// ── Les trois parcours en profondeur, en une seule fonction ───────────────
// position vaut "prefixe", "infixe" ou "suffixe".
function profondeur(A, position, sortie = []) {
if (A === null) return sortie;
if (position === "prefixe") sortie.push(A.valeur);
profondeur(A.gauche, position, sortie);
// ← à écrire : la visite infixe se place ICI
profondeur(A.droit, position, sortie);
// ← et la visite suffixe LÀ
return sortie;
}
// ── Hauteur et taille ─────────────────────────────────────────────────────
function hauteur(A) {
if (A === null) return -1; // un arbre vide a une hauteur de −1
return 0; // ← à écrire : 1 + le max des hauteurs des deux sous-arbres
}
function taille(A) {
if (A === null) return 0;
return 1 + taille(A.gauche) + taille(A.droit);
}
// ── Évaluation ────────────────────────────────────────────────────────────
function evaluer(A) {
if (A.gauche === null && A.droit === null) return A.valeur;
const g = evaluer(A.gauche);
const d = evaluer(A.droit);
const ops = { "+": (a, b) => a + b, "-": (a, b) => a - b,
"*": (a, b) => a * b, "/": (a, b) => a / b };
return ops[A.valeur](g, d);
}
// ── Parcours en largeur, et son jumeau ────────────────────────────────────
// Une SEULE différence entre les deux : on retire par le début ou par la fin.
function parcours(A, parLeDebut) {
const attente = [A], sortie = [];
while (attente.length > 0) {
const n = parLeDebut ? attente.shift() : attente.pop();
sortie.push(n.valeur);
if (n.gauche) attente.push(n.gauche);
if (n.droit) attente.push(n.droit);
}
return sortie;
}
// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Complétez profondeur() et hauteur().
// 2. Vérifiez l'encadrement : log2(n+1) − 1 ≤ h ≤ n − 1.
// 3. Comparez parcours(A, true) et parcours(A, false). Lequel est en
// largeur ? Lequel retrouve un parcours en profondeur, et lequel ?
console.log("préfixe :", profondeur(EXPR, "prefixe").join(" "));
console.log("évaluation :", evaluer(EXPR), "(et non 14)");
Solution
const noeud = (valeur, gauche = null, droit = null) => ({ valeur, gauche, droit });
const EXPR = noeud("+", noeud(3), noeud("*", noeud(4), noeud(2)));
// (1 + 2) * (8 - 3) : les parenthèses de l'écriture usuelle disparaissent,
// elles sont dans la forme de l'arbre.
const EXPR2 = noeud("*", noeud("+", noeud(1), noeud(2)), noeud("-", noeud(8), noeud(3)));
function profondeur(A, position, sortie = []) {
if (A === null) return sortie;
if (position === "prefixe") sortie.push(A.valeur);
profondeur(A.gauche, position, sortie);
if (position === "infixe") sortie.push(A.valeur);
profondeur(A.droit, position, sortie);
if (position === "suffixe") sortie.push(A.valeur);
return sortie;
}
function hauteur(A) {
if (A === null) return -1;
return 1 + Math.max(hauteur(A.gauche), hauteur(A.droit));
}
function taille(A) {
if (A === null) return 0;
return 1 + taille(A.gauche) + taille(A.droit);
}
function evaluer(A) {
if (A.gauche === null && A.droit === null) return A.valeur;
// Les DEUX appels précèdent l'application : c'est un parcours suffixe, et
// c'est pourquoi la notation postfixée s'évalue si simplement à la pile.
const g = evaluer(A.gauche);
const d = evaluer(A.droit);
const ops = { "+": (a, b) => a + b, "-": (a, b) => a - b,
"*": (a, b) => a * b, "/": (a, b) => a / b };
return ops[A.valeur](g, d);
}
function parcours(A, parLeDebut) {
const attente = [A], sortie = [];
while (attente.length > 0) {
// shift() = défiler une FILE (le plus ancien) -> parcours en largeur.
// pop() = dépiler une PILE (le plus récent) -> parcours en profondeur.
const n = parLeDebut ? attente.shift() : attente.pop();
sortie.push(n.valeur);
if (n.gauche) attente.push(n.gauche);
if (n.droit) attente.push(n.droit);
}
return sortie;
}
for (const [nom, A] of [["3 + 4 * 2", EXPR], ["(1 + 2) * (8 - 3)", EXPR2]]) {
console.log("— " + nom + " —");
console.log(" préfixe (polonaise) : " + profondeur(A, "prefixe").join(" "));
console.log(" infixe (usuelle) : " + profondeur(A, "infixe").join(" "));
console.log(" suffixe (postfixée) : " + profondeur(A, "suffixe").join(" "));
console.log(" évaluation : " + evaluer(A));
const n = taille(A), h = hauteur(A);
const bas = Math.log2(n + 1) - 1;
console.log(" taille " + n + ", hauteur " + h +
" | encadrement " + bas.toFixed(2) + " <= " + h + " <= " + (n - 1) +
(bas <= h && h <= n - 1 ? " ok" : " X"));
console.log("");
}
console.log("— même code, deux structures d'attente —");
console.log(" avec une FILE (shift) : " + parcours(EXPR2, true).join(" ") + " -> en largeur, niveau par niveau");
console.log(" avec une PILE (pop) : " + parcours(EXPR2, false).join(" ") + " -> en profondeur");
// Une seule ligne change, et l'ordre de visite bascule complètement. C'est
// la leçon du bloc III : la structure de données ne sert pas seulement à
// ranger, elle décide de l'algorithme.
console.log("");
console.log("— arbre dégénéré : le pire cas —");
// Une chaîne : chaque nœud n'a qu'un enfant droit.
let chaine = noeud(5);
for (let i = 4; i >= 1; i--) chaine = noeud(i, null, chaine);
console.log(" taille " + taille(chaine) + ", hauteur " + hauteur(chaine) +
" -> h = n − 1, l'arbre EST une liste chaînée");
En travaux pratiques
Travaux pratiques 7 · 3 h
Quatre parcours, quatre usages
Implémenter un arbre binaire et ses parcours, puis constater que l'ORDRE de visite n'est pas un détail : chaque parcours résout un problème que les autres ne résolvent pas.
Avant de commencer
- Le TP 6 : pile et file
- Le TP 1 : récursivité et trace indentée
Énoncé
- Construire à la main — Définissez le nœud et construisez un arbre de sept nœuds explicitement, sans fonction d'insertion. Dessinez-le sur papier à côté.
- Les trois parcours en profondeur — Écrivez préfixe, infixe et suffixe. Exécutez les trois sur votre arbre et notez les trois suites de valeurs. Reliez chaque suite à votre dessin.
- Le parcours en largeur — Écrivez le parcours par niveaux avec la file du TP 6. Vérifiez qu'il donne bien l'ordre de lecture de votre dessin, ligne par ligne.
- Hauteur et taille — Écrivez le calcul de la hauteur, du nombre de nœuds et du nombre de feuilles. Chacune tient en trois lignes récursives.
- Choisir le bon parcours — Pour chacune de ces tâches, dites lequel des quatre parcours convient, et pourquoi : libérer l'arbre, l'afficher indenté, le recopier, afficher une expression arithmétique dans l'ordre naturel. Indice : Pour libérer, réfléchissez à ce qu'on ne peut pas faire avant d'avoir traité les enfants.
- Un arbre d'expression — Construisez l'arbre de l'expression correspondant à trois plus quatre, le tout multiplié par deux. Exécutez les trois parcours et reliez chacun à une notation connue.
- L'évaluer — Écrivez l'évaluation récursive de l'arbre d'expression. Comparez avec l'évaluateur postfixé du TP 6.
- Sans récursion — Réécrivez le parcours infixe avec une pile explicite. Comparez la longueur du code et la profondeur maximale supportée.
C'est réussi quand
- Vos trois suites correspondent exactement à votre dessin
- Vous justifiez le parcours suffixe pour la libération, sans hésiter
- Le parcours infixe de votre arbre d'expression redonne la notation habituelle
Correction
void prefixe(Noeud *n) { if(!n) return; visiter(n); prefixe(n->g); prefixe(n->d); }
void infixe(Noeud *n) { if(!n) return; infixe(n->g); visiter(n); infixe(n->d); }
void suffixe(Noeud *n) { if(!n) return; suffixe(n->g); suffixe(n->d); visiter(n); }
void largeur(Noeud *racine) {
File f; file_init(&f); enfiler(&f, racine);
while (!file_vide(&f)) {
Noeud *n = defiler(&f);
visiter(n);
if (n->g) enfiler(&f, n->g);
if (n->d) enfiler(&f, n->d);
}
}Les trois premiers ne diffèrent que par la POSITION de l'appel à visiter : avant, entre, après. Une seule ligne déplacée, trois algorithmes. Le quatrième n'est pas récursif du tout — il utilise la file du TP 6, et c'est exactement le même code que le parcours en largeur du labyrinthe.
préfixe : racine d'abord → recopier un arbre, l'afficher indenté, le sérialiser infixe : gauche, racine, droite → sur un ABR, donne les valeurs TRIÉES (TP 8) → sur un arbre d'expression, donne la notation infixe suffixe : enfants d'abord → LIBÉRER (on ne peut pas free un nœud avant ses enfants : on perdrait les pointeurs) → calculer une valeur qui dépend des sous-arbres (hauteur, taille) largeur : par niveaux → plus court chemin, affichage par étage, sérialisation compacte
Le cas de la libération est le plus parlant : libérer la racine d'abord détruit les seuls pointeurs menant aux enfants, et tout le sous-arbre fuit. Le parcours suffixe n'est donc pas une préférence de style, c'est le seul correct — et ce raisonnement « les enfants d'abord » vaut pour tout calcul remontant.
(*)
/ \
(+) 2
/ \
3 4
préfixe : * + 3 4 2 notation POLONAISE (préfixée)
infixe : 3 + 4 * 2 notation habituelle — mais SANS parenthèses !
suffixe : 3 4 + 2 * notation POLONAISE INVERSE (postfixée)Les trois notations arithmétiques sont les trois parcours du même arbre. Et le parcours infixe perd de l'information : « 3 + 4 * 2 » relu naïvement donne 11, pas 14. L'arbre porte la structure, la notation infixe ne la porte qu'avec des parenthèses — c'est pourquoi les compilateurs travaillent sur l'arbre et non sur le texte.
int hauteur(Noeud *n) {
if (!n) return -1; /* -1 : arbre vide */
int hg = hauteur(n->g), hd = hauteur(n->d);
return 1 + (hg > hd ? hg : hd);
}
int taille(Noeud *n) { return n ? 1 + taille(n->g) + taille(n->d) : 0; }
int feuilles(Noeud *n) {
if (!n) return 0;
if (!n->g && !n->d) return 1;
return feuilles(n->g) + feuilles(n->d);
}Trois lignes chacune, et toutes trois sont des parcours SUFFIXES : la valeur du nœud dépend de celles de ses enfants, donc on descend d'abord. La convention hauteur d'un arbre vide égale −1 fait que la hauteur d'une feuille vaut 0 ; l'autre convention est valable aussi, à condition de s'y tenir partout.
void infixe_iteratif(Noeud *racine) {
Pile p; pile_init(&p);
Noeud *n = racine;
while (n || !pile_vide(&p)) {
while (n) { empiler(&p, n); n = n->g; } /* descendre à gauche */
n = depiler(&p);
visiter(n);
n = n->d; /* puis à droite */
}
}Neuf lignes contre une, pour le même résultat. La pile explicite remplace exactement la pile d'appels du TP 1 — c'est la dérécursivation du TP 2 appliquée à un arbre. On ne l'écrit que si la profondeur peut être grande, autrement dit sur un arbre potentiellement dégénéré, ce que le TP 8 va justement produire.
Ce que la suite en fait
Le chapitre 8 impose un invariant sur les valeurs — un ordre pour l'arbre binaire de recherche, une priorité pour le tas — et c'est cet invariant qui transforme une structure de rangement en structure de recherche. On y verra que l'accès en est conditionnel : il suppose que la hauteur reste logarithmique, ce que l'encadrement de ce chapitre ne garantit pas du tout.
La représentation par tableau y trouvera son emploi : le tas est précisément l'arbre complet pour lequel elle a été inventée, et c'est ce qui permet un tri en sur place, la combinaison que ni le tri fusion ni le tri rapide n'offraient.
À retenir
Flashcards · 5 cartes
- Quel encadrement relie hauteur et taille d'un arbre binaire, et pourquoi est-il central ?
- Un arbre de hauteur h a au moins h+1 nœuds (une chaîne) et au plus 2^(h+1) − 1 (arbre parfait). Donc pour n nœuds : log₂(n+1) − 1 ≤ h ≤ n − 1. Central parce que la plupart des opérations coûtent O(h) : un arbre ÉQUILIBRÉ donne O(log n), un arbre DÉGÉNÉRÉ est une liste chaînée déguisée en O(n). C'est le même écart qu'entre bon et mauvais pivot au chapitre 3.
- Comment représenter un arbre binaire par tableau, et à quelle condition ?
- Les enfants du nœud d'indice i sont en 2i+1 et 2i+2, son parent en (i−1)/2. Aucun pointeur, mémoire contiguë (donc bénéfices de cache) et navigation par arithmétique. Condition stricte : l'arbre doit rester COMPLET — tous les niveaux remplis sauf le dernier, comblé de gauche à droite — sans quoi le tableau se troue. C'est la représentation du tas.
- Quelle est la seule différence entre les parcours préfixe, infixe et suffixe ?
- La POSITION DE LA VISITE dans le corps de la fonction, les deux appels récursifs restant identiques. Préfixe : visiter, gauche, droite — donne la notation polonaise. Infixe : gauche, visiter, droite — donne la notation usuelle, et l'ordre croissant sur un ABR. Suffixe : gauche, droite, visiter — donne la notation postfixée, et garantit qu'un nœud est traité après sa descendance (indispensable pour libérer un arbre ou évaluer une expression).
- Comment fait-on un parcours en largeur, et que se passe-t-il si l'on change la structure ?
- Avec une FILE : on enfile la racine, puis tant qu'elle n'est pas vide on défile un nœud, on le visite et on enfile ses enfants. Les enfants d'un nœud de profondeur k passent derrière tous les nœuds de profondeur k encore en attente, d'où l'ordre par niveaux. Remplacer la file par une PILE dans le même code donne un parcours en profondeur préfixe : c'est la structure, pas l'algorithme, qui décide de l'ordre de visite.
- Qu'est-ce qu'un arbre d'expression, et que résout-il ?
- Les feuilles portent les opérandes, les nœuds internes les opérateurs. Il résout les PRIORITÉS une fois pour toutes : dans 3 + 4 × 2, la multiplication devient un sous-arbre de l'addition, donc elle est évaluée avant sans qu'aucune règle n'intervienne. L'évaluation est une récursion suffixe — évaluer les deux enfants, puis appliquer l'opérateur — et c'est pourquoi la notation postfixée s'évalue si simplement à la pile : les deux mécanismes sont le même.