モジュール詳細：二分木

通常の木とは真逆に、二分木は下にどんどん伸びていくから、探索順序も違って混乱するんだよね……。

二分木に関する用語と順序の解説については、付録BTを参照する。

• モジュールには、画面と深さ3の二分木があり、二分木には7個の押せるボタンでできた節がある。 各節は異なる色をしており、それぞれに黒または銀の文字が記載されている。 このモジュールには英字の'O'は出現しないが、数字のゼロは出現する可能性がある。
• モジュールは3ステージで構成されている。各ステージで、参照節を使用してどの節を押すべきか特定する。 最初のステージでは、木の根を参照節として使用する。 その後のステージでは、直前のステージで押した正しい節を参照節として使用する。
• どの節を押すべきか探すには、まず参照節に記されている文字を数字に変換する。 それが数字の文字であればその数字を使用し、そうでない場合はアルファベット上の位置+2を使用する。
• 結果の数字が7を超える場合、1–7の範囲になるまで、繰り返し7を引く。数字が0の場合、7を使用する。 この数字をNと呼ぶ。
• 次ページの表を使用して、現在のステージ数と参照節の色から、節の順番を特定する。
• 順番に数えて最初からN番目の節を押す。 ただし参照節の文字が銀色の場合は例外とする。その場合は、代わりに最後から数えてN番目の節を押す。
• 画面は直前に押した正しい節を表示し、モジュールの解除には必要ではない。
• 間違った節を押すとミスが記録されるが、モジュールは現在のステージのままである。 更に、モジュールはしばらく十字の形をしたミスの記号を表示し、この間はすべての入力が無視される。

節の順番表

ステージ数		ステージ1	ステージ2	ステージ3
参照節の色	赤	先行順	右から左への 中間順	右から左への 幅優先
	緑	中間順	右から左への 後行順	中間順
	青	後行順	右から左への 先行順	右から左への 中間順
	オレンジ	幅優先	幅優先	先行順
	シアン	右から左への 先行順	先行順	幅優先
	マゼンタ	右から左への 中間順	中間順	右から左への 後行順
	黄	右から左への 後行順	右から左への 幅優先	後行順
	灰	右から左への 幅優先	後行順	右から左への 先行順

付録BT：二分木の用語&探索順序

用語

• 完全二分木とは、各節に子と呼ばれる節が最下段の節を除いてその真下に二つずつ付いている構造になっている。
• 木の根(ルート)は、木の最上段にある節のことである。
• 節の左部分木は、節の左の子と子の子である節をすべて含んだ木のことである。 節の右部分木は、節の右の子と子の子である節をすべて含んだ木のことである。
• 木の順序は、木の各節をある順序で一回だけ訪れる。

順序

• 先行順：根から開始し、まず根を訪れその左にある部分木のすべての節を訪れ、その右の部分木のすべての節を訪れ、最初に訪れた順に数える。
• 中間順:根から開始し、まず根を訪れその左にある部分木のすべての節を訪れ、その右の部分木のすべての節を訪れ、節の真下を訪れた順に数える。
• 後行順:根から開始し、まず根を訪れその左にある部分木のすべての節を訪れ、その右の部分木のすべての節を訪れ、訪れ終わった順に数える。
• 幅優先:読み順と似ている。最上段から開始し、それぞれの段を左から右に読む。
• 上で右から左の順序形式では、上記の対応する説明において「右」と「左」を入れ替えて読む。