令和3年度 春期 午前 問6

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

解説

根から浅い順に読むので幅優先探索に当たります。

設問は、配列と 2 分木の対応づけを与えたうえで、配列を先頭から順に調べる行為がどの探索に当たるかを問うています。ですから見分けの軸は、その読み方が同じ深さのものを先にすべて読むのか、それとも一つの枝を深いところまで先に降りるのか、という一点だけです。与えられた対応では、番号 i の要素の子が番号 2i と 2i+1 に置かれます。番号 1 が根、番号 2 と 3 が深さ 1 の二つ、番号 4 から 7 までが深さ 2 の四つというように、同じ深さのものが番号の上で連続してかたまります。ですから先頭から番号順に調べると、根を読み、次に深さ 1 をすべて読み、続いて深さ 2 をすべて読むという順序になります。これは階層ごとに横へなぞる読み方です。

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

• ア行きがけ順（先行順）深さ優先探索：節を訪れてから左の部分木、右の部分木へと降りていく読み方です。根の次に読むのは根の左の子ですが、その後は同じ深さの右の子へ移らず、さらに下の子孫へ先に降りるため、番号順の並びとずれます。
• イ帰りがけ順（後行順）深さ優先探索：左右の部分木を読み終えてから節そのものを読む読み方です。最初に読まれるのは根ではなく最も左下にある葉になりますから、配列の先頭にある根から始まる順序とは出だしから食い違います。
• ウ通りがけ順（中間順）深さ優先探索：左の部分木を読み、節を読み、右の部分木を読む読み方です。根が読まれるのは全体のちょうど途中になりますから、先頭の要素を最初に調べる順序にはなりません。