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.

Messages d'exception

Il est parfois nécessaire de lever une exception. Dans ce cas, il faut toujours inclure un message d'erreur explicite pour indiquer l'origine de l'erreur. Cela rend le code plus lisible et facilite grandement le débogage. Quand tu sais que l'erreur sera d'un type précis, tu peux lever l'un des types d'erreur intégrés, mais il faut tout de même y joindre un message explicite.

Cet exercice demande plus précisément d'utiliser l'instruction raise pour « lever » une ValueError si les arguments preorder et inorder n'ont pas la même longueur, ne contiennent pas les mêmes éléments, ou si les éléments ne sont pas uniques. Les tests ne passeront que si tu lèves l'exception avec raise et que tu l'accompagnes d'un message.

Pour lever une ValueError accompagnée d'un message, écris ce message comme argument du type d'exception :

# if preorder and inorder are not the same length
raise ValueError("traversals must have the same length")

# if preorder and inorder do not share the same elements
raise ValueError("traversals must have the same elements")
    
# if element repeat (are not unique)    
raise ValueError("traversals must contain unique items")