Arbres binaires

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");

Avant de commencer

• Le TP 6 : pile et file
• Le TP 1 : récursivité et trace indentée

Énoncé

1. 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é.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. L'évaluer — Écrivez l'évaluation récursive de l'arbre d'expression. Comparez avec l'évaluateur postfixé du TP 6.
8. 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);
  }
}

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

        (*)
     /   \
   (+)    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)

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);
}

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 */
  }
}