【問題】
配列A[1],A[2],…,A[n]で、A[1]を根とし、A[i]の左側の子をA[2i]、右側の子をA[2i+1]とみなすことによって、2分木を表現する。このとき、配列を先頭から順に調べていくことは、2分木の探索のどれに当たるか。
ア．行きがけ順（先行順）深さ優先探索
イ．帰りがけ順（後行順）深さ優先探索
ウ．通りがけ順（中間順）深さ優先探索
エ．幅優先探索
【解答】
問題文の解釈が出来るかどうかが重要になる。
まず、どのような2分木を表現しているのかを考察すると、i=1の場合、A[1]の左側をA[2]、右側をA[3]とするから
A[1]
A[2] A[3]
のような2分木になる。さらに、i=2の場合、A[2]を節として、A[4]が左側に、A[5]が右側に来るので、
A[2]
A[4] A[5]
となる。同様に、i=3の場合も、A[3]を節として、A[6]が左側、A[7]が右側に配置されるので、
A[3]
A[6] A[7]
となる。
これを一つの2分木として表すと、
A[1]
A[2] A[3]
A[4] A[5] A[6] A[7]
となる。
さらに、配列を先頭から順に調べていくということは、以下の順に調べていくことを意味する。
A[1]①
A[2]② A[3]③
A[4]④ A[5]⑤ A[6]⑥ A[7]⑦
これは幅優先探索になるから、解答はエとなる。