人工衛星

説明

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

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

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

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

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

  a
 / \
i   x
   / \
  f   r

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