配列A[1]，A[2]，…，A[n]で，A[1]を根とし，A[i]の左側の子をA[2i]，右側の子をA[2i+1]とみなすことによって，2分木を表現する。
このとき，配列を先頭から順に調べていくことは，2分木の探索のどれに当たるか。
正答4
解説
正解は4です。
配列で2分木を表す方法では、A[1]が根、A[2]とA[3]がその子、A[4]〜A[7]が孫というように、浅い階層から順に並びます。
同じ階層の中では左から右の順に並んでいます。
【選択肢別解説】
1：× 行きがけ順（先行順）は、根、左部分木、右部分木の順に深くたどります。
A[1]の次にA[2]、その次はA[3]ではなくA[4]を訪問するため、配列の順とは異なります。
2：× 帰りがけ順（後行順）は、左部分木、右部分木、根の順です。
最初に最も深い左端の節点を訪問するので、根から始まる配列の順とは異なります。
3：× 通りがけ順（中間順）は、左部分木、根、右部分木の順です。
こちらも左下の節点から始まるため、配列の順とは異なります。
4：○ 幅優先探索は、根から近い階層ごとに左から右へ節点を訪問します。
これは配列を先頭から順に調べる順序と一致します。
【ポイント】
この配列表現はヒープでも使われます。
「配列の添字順＝階層順＝幅優先探索」と結び付けて覚えておきましょう。