配列A[1]，A[2]，…，A[n]で，A[1]を根とし，A[i]の左側の子をA[2i]，右側の子をA[2i+1]とみなすことによって，2分木を表現する。
このとき，配列を先頭から順に調べていくことは，2分木の探索のどれに当たるか。
正答4
解説
正解は4です。
この配列表現では、A[1]が根、A[2]とA[3]が深さ1、A[4]からA[7]が深さ2のノードになります。
つまり、配列の添字の順は、浅い階層から順に、同じ階層では左から右へと並んでいます。
【選択肢別解説】
1：× 行きがけ順（先行順）は、根、左部分木、右部分木の順に訪れる探索です。
A[1]の次に左の子A[2]、さらにその左の子A[4]へと深く進むので、A[3]より先にA[4]を訪れます。
配列の順（A[1]、A[2]、A[3]…）とは一致しません。
2：× 帰りがけ順（後行順）は、左部分木、右部分木、根の順に訪れる探索です。
根A[1]が最後になるので、配列の先頭から調べる順とは一致しません。
3：× 通りがけ順（中間順）は、左部分木、根、右部分木の順に訪れる探索です。
最初に訪れるのは最も左下の葉であり、A[1]から始まる配列の順とは一致しません。
4：○ 幅優先探索は、根から近い階層の順に、同じ階層を左から右へたどる探索です。
添字の順に調べると、深さ0、深さ1、深さ2…と各階層を左から順に訪れるので、幅優先探索に当たります。
【ポイント】
この配列表現はヒープの実装にも使われます。
ノードA[i]の親はA[i÷2]（小数点以下切捨て）となる点もあわせて覚えておきましょう。