人工衛星

説明

アルファ・ケンタウリへ向かう衛星に二分木を送信する必要があり、しかも通信帯域が限られていると想像してみてください。 この木には重複する要素がないので、行きがけ順と通りがけ順の走査によって一意に表すことができます。

その走査結果から木を復元するソフトウェアを、衛星のために書きましょう。

行きがけ順の走査では、左部分木を行きがけ順で読む前に、現在のノードの値を読みます（だから「行きがけ」なのです）。 その後、右部分木を行きがけ順で読みます。

通りがけ順の走査では、左部分木を通りがけ順で読み、次に現在のノード、最後に右部分木を通りがけ順で読みます。 つまり、左から右へと順に読み進めることになります。

たとえば、この木の行きがけ順の走査は[a, i, x, f, r]です。 通りがけ順の走査は[i, a, f, x, r]です。

  a
 / \
i   x
   / \
  f   r

補足：行きがけ順の走査で最初に現れる要素は、常に根です。

例外メッセージ

ときには例外を発生させる必要があります。そのときは、エラーの原因が何であるかを示す意味のあるエラーメッセージを必ず含めるようにしましょう。そうすることでコードが読みやすくなり、デバッグもずっと楽になります。エラーの原因が特定の種類になるとわかっている場合は、組み込みのエラータイプのいずれかを発生させることもできますが、その場合でも意味のあるメッセージを含めるようにしましょう。

この演習では、preorderとinorderの引数が長さで一致しない場合、要素で一致しない場合、または要素が重複している場合に、raise文を使ってValueErrorを「スロー」する必要があります。テストに合格するには、raiseでexceptionを投げ、それにメッセージを付ける、その両方ができていなければなりません。

メッセージ付きでValueErrorを発生させるには、メッセージを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")