Parcours infixe

Exercice · OCaml (option informatique), chapitre 3 — Types sommes et arbres

Énoncé

Écrire infixe : 'a arbre -> 'a list qui liste les étiquettes en ordre gauche – racine – droite. Que vaut ce parcours sur un ABR ? Discuter le coût.

Corrigé

let rec infixe a =
  match a with
  | Vide -> []
  | Noeud (g, x, d) -> infixe g @ [x] @ infixe d

Sur un ABR, le parcours infixe renvoie les étiquettes triées par ordre croissant — c'est une propriété caractéristique. Côté coût, les @ répétés rendent ce parcours quadratique dans le pire cas ; une variante à accumulateur (aux g (x :: aux d acc)) le ramène en $Θ (n)$ — même idée que le renverse du chapitre 2.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.