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