Istruzioni
Immagina di dover trasmettere un albero binario a un satellite che si avvicina ad Alpha Centauri, con una larghezza di banda limitata.
Dato che l'albero non ha elementi ripetuti, può essere rappresentato in modo univoco dai suoi attraversamenti in pre-ordine e in ordine.
Scrivi il software che permetterà al satellite di ricostruire l'albero a partire dagli attraversamenti.
Un attraversamento in pre-ordine legge il valore del nodo corrente prima (da cui il «pre») di leggere il sottoalbero sinistro in pre-ordine.
Subito dopo, il sottoalbero destro viene letto in pre-ordine.
Un attraversamento in ordine legge il sottoalbero sinistro in ordine, poi il nodo corrente e infine il sottoalbero destro in ordine.
Quindi in ordine da sinistra a destra.
Ad esempio, l'attraversamento in pre-ordine di questo albero è [a, i, x, f, r].
L'attraversamento in ordine di questo albero è [i, a, f, x, r]
a
/ \
i x
/ \
f r
Nota: il primo elemento dell'attraversamento in pre-ordine è sempre la radice.
Messaggi delle eccezioni
A volte è necessario sollevare un'eccezione. Quando lo fai, dovresti sempre includere un messaggio di errore significativo che indichi qual è l'origine dell'errore. Questo rende il codice più leggibile e aiuta molto nel debug. Nei casi in cui sai che l'origine dell'errore sarà di un certo tipo, puoi scegliere di sollevare uno dei tipi di errore predefiniti, ma dovresti comunque includere un messaggio significativo.
Questo esercizio in particolare richiede che tu usi l'istruzione raise per «lanciare» un ValueError se gli argomenti preorder e inorder non corrispondono per lunghezza, per elementi, oppure se gli elementi non sono unici. I test passeranno solo se usi raise e includi anche un messaggio insieme all'exception.
Per sollevare un ValueError con un messaggio, scrivi il messaggio come argomento del tipo 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")
