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