Le miroir

(* Renvoie l'arbre symetrique de a. Complexite : Theta(n) en temps. *)
let rec miroir = function
  | Vide -> Vide
  | Noeud (g, e, d) -> Noeud (miroir d, e, miroir g)     (* d et g ECHANGES *)

Le parcours infixe est renversé : $\text{infixe}(\text{miroir}(a))=\text{renverse}(\text{infixe}(a))$.

Vérification : sur l'arbre de l'exercice 10.1, $\text{infixe}(a)=1,3,4,6,8,7,9$ et $\text{infixe}(\text{miroir}(a))=9,7,8,6,4,3,1$. Les deux listes sont bien l'inverse l'une de l'autre, et $\text{miroir}(\text{miroir}(a))=a$ : vérifié.

Et les deux autres parcours ? Le préfixe du miroir n'est pas l'inverse du préfixe : c'est l'inverse du postfixe. En effet, préfixe visite racine-gauche-droite ; en renversant l'arbre puis la liste, on obtient gauche-droite-racine, qui est le postfixe. Symétriquement, $\text{postfixe}(\text{miroir}(a))=\text{renverse}(\text{prefixe}(a))$. Seul l'infixe est stable par cette double symétrie, parce qu'il est le seul des trois à être symétrique dans sa définition.

À quoi cela sert. À obtenir gratuitement la variante décroissante de tout algorithme fondé sur l'infixe : parcourir un arbre binaire de recherche par ordre décroissant, c'est parcourir son miroir par ordre croissant — ou, plus économiquement, échanger les deux appels récursifs, ce qui coûte $\Theta (1)$ au lieu de $\Theta (n)$.