Deux parcours suffisent-ils à retrouver l'arbre ?

1. Non, et le contre-exemple tient en deux nœuds. Soient

$$\begin{array}{rl}{a}_1& =\text{Nœud}(\text{Nœud}(\text{Vide},7,\text{Vide}),9,\text{Vide}),\\ a_2& =\text{Nœud}(\text{Vide},9,\text{Nœud}(\text{Vide},7,\text{Vide})).\end{array}$$

Le $7$ est fils gauche dans l'un, fils droit dans l'autre. Mesures :

Mêmes préfixe et postfixe, arbres différents. La cause est structurelle : ces deux parcours ne disent jamais de quel côté se trouve un fils unique. Le préfixe pose la racine avant ses fils, le postfixe après — ni l'un ni l'autre ne les sépare. Seul l'infixe, qui pose la racine entre les deux sous-arbres, porte cette information.

2. Oui, et la reconstruction est constructive. La racine est le premier élément du préfixe ; on la cherche dans l'infixe, ce qui coupe celui-ci en deux : à gauche les $k$ étiquettes du sous-arbre gauche, à droite celles du sous-arbre droit. On coupe alors la queue du préfixe aux mêmes tailles, et l'on recommence.

(* Reconstruit l'arbre a partir de ses parcours prefixe et infixe.
   Precondition : les deux listes sont les parcours d'un MEME arbre dont
   toutes les etiquettes sont DISTINCTES. *)
let rec reconstruit pre inf = match pre, inf with
  | [], [] -> Vide
  | r :: pre', _ ->
      let (gi, di) = coupe_en r inf in          (* infixe gauche, infixe droit *)
      let k = List.length gi in
      let gp = prefixe_des k pre'               (* les k premiers *)
      and dp = apres_les k pre' in              (* les suivants *)
      Noeud (reconstruit gp gi, r, reconstruit dp di)
  | _ -> failwith "listes incompatibles"

Terminaison. Variant : la longueur de pre. Chaque appel récursif reçoit une liste strictement plus courte, la racine ayant été retirée.

Correction, par récurrence forte sur la taille. L'arbre vide donne deux listes vides. Sinon, la racine est bien le premier du préfixe — par définition du parcours ; et l'infixe est exactement (infixe du gauche)(racine)(infixe du droit), donc la coupe sur la racine sépare correctement, à condition que les étiquettes soient distinctes : sinon on ne saurait pas laquelle des occurrences est la racine. C'est la précondition, et elle n'est pas décorative.

Vérification : la reconstruction rend l'arbre de départ sur $3000$ arbres tirés au hasard jusqu'à $40$ nœuds, à étiquettes distinctes.

Complexité. La recherche de la racine dans l'infixe coûte $O(n)$ ; sur un peigne, on obtient $\Theta (n^2)$. Une table associative des positions (chapitre chap:hachage) ramène chaque recherche à $O(1)$ et le total à $\Theta (n)$.

La conclusion, et elle est plus générale que l'exercice. Un parcours seul perd de l'information : il aplatit un objet à deux dimensions en une liste. Deux parcours bien choisis la restituent, deux autres non. Pour qu'un seul parcours suffise, il faut lui faire porter les arbres vides — c'est exactement ce que construit le problème 10.1.