令和3年度 春期 応用情報技術者試験 午前 問6
テクノロジ／アルゴリズム配列 A[1]，A[2]，…，A[n] で，A[1] を根とし，A[i] の左側の子を A[2i]，右側の子を A[2i＋1] とみなすことによって，2分木を表現する。このとき，配列を先頭から順に調べていくことは，2分木の探索のどれに当たるか。
出典：令和3年度 春期 応用情報技術者試験 午前 問6
- ア行きがけ順（先行順）深さ優先探索
- イ帰りがけ順（後行順）深さ優先探索
- ウ通りがけ順（中間順）深さ優先探索
- エ幅優先探索
正解：エ
解説
A[1] を根とし A[i] の子を A[2i]，A[2i＋1] とする配列表現では，配列の添字順（A[1]，A[2]，A[3]，…）は木の浅い階層から順に，同じ階層では左から右への並びになっています。したがって配列を先頭から順に調べることは，幅優先探索（レベル順探索）に相当します。
選択肢ごとの解説
- ア誤り。行きがけ順（先行順）は根→左部分木→右部分木の順にたどる深さ優先探索であり，配列の添字順とは一致しません。
- イ誤り。帰りがけ順（後行順）は左部分木→右部分木→根の順にたどる深さ優先探索であり，配列の添字順とは一致しません。
- ウ誤り。通りがけ順（中間順）は左部分木→根→右部分木の順にたどる深さ優先探索であり，配列の添字順とは一致しません。
- エ正しい。配列の添字順は階層ごとに左から右へ調べる順序であり，幅優先探索に当たります。