Satellite

Instructions

Imagine que tu doives transmettre un arbre binaire à un satellite qui s'approche d'Alpha Centauri, avec une bande passante limitée. Comme l'arbre ne contient aucun élément en double, il peut être représenté de façon unique par ses parcours préfixe et infixe.

Écris le logiciel qui permettra au satellite de reconstruire l'arbre à partir de ces parcours.

Un parcours préfixe lit la valeur du nœud courant avant (d'où le « pré ») de parcourir le sous-arbre gauche en préfixe. Ensuite, le sous-arbre droit est parcouru en préfixe.

Un parcours infixe parcourt le sous-arbre gauche en infixe, puis le nœud courant, et enfin le sous-arbre droit en infixe. Donc, de gauche à droite.

Par exemple, le parcours préfixe de cet arbre est [a, i, x, f, r]. Le parcours infixe de cet arbre est [i, a, f, x, r]

  a
 / \
i   x
   / \
  f   r

Remarque : le premier élément du parcours préfixe est toujours la racine.