平成29年度 秋期 午前 問5

✓ これが正解エ幅優先探索

解説

添字の順は、上の段から左へ右への並びになります。

設問は、配列を先頭から順に調べることが、どの探索に当たるかを問うています。まず添字の振られ方を確かめます。根が先頭に置かれ、ある要素の子が添字の二倍と二倍足す一に置かれるので、番号は段の浅いほうから順に、同じ段の中では左から右へ振られます。根が一番、その子が二番と三番、さらにその子が四番から七番、という具合です。したがって配列を先頭から読むことは、木を段ごとに上から下へ、各段では左から右へたどることと同じになります。これが幅優先探索です。深さ優先探索は、根を離れたらまず左側の部分木を最後まで片づけるので、根の子を二つ続けて読むことができません。三つ目の要素で分かれると覚えておくと速く決まります。

ほかの選択肢はなぜ違うのか

• ア行きがけ順（先行順）深さ優先探索：行きがけ順は、節を出してから左側へ潜っていく読み方です。根の次に来るのは左の子で、そちらの部分木を読み切るまで右の子には移らないため、番号の順とはずれます。
• イ帰りがけ順（後行順）深さ優先探索：帰りがけ順では、両側の部分木を読み終えてから節を出します。最初に出るのは最も深い左端の要素で、根は最後に回るので、先頭が根になる番号の順とは並びが違います。
• ウ通りがけ順（中間順）深さ優先探索：通りがけ順は、左側、節、右側という並びで出す読み方です。根が出てくるのは全体のほぼ中ほどになるため、先頭から順に読んだ並びとは一致しません。