OCaml (option informatique) · Chapitre 3 · Exercice de TD
Parcours infixe
Types sommes et arbres · niveau 3 (difficile)
É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 dSur 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 — même idée que le renverse du chapitre 2.
Exercices semblables
- Compter les feuilles corrigé
- Miroir d'un arbre corrigé
- Évaluer une expression arithmétique corrigé
- Appartenance dans un arbre binaire de recherche corrigé
- Insertion dans un ABR corrigé