応用情報技術者試験 応用情報技術者試験 平成29年度秋期 午前 問5: 配列 A[1]，A[2]，…，A[n] で，A[1] を根とし，A[i] の左側の子を A[2i]，右側の子を A[2i+1] とみなすことによって，2 分木を

問題本文

配列 A[1]，A[2]，…，A[n] で，A[1] を根とし，A[i] の左側の子を A[2i]，右側の子を A[2i+1] とみなすことによって，2 分木を表現する。このとき，配列を先頭から順に調べていくことは，2 分木の探索のどれに当たるか。

選択肢

• ア.行きがけ順（先行順）深さ優先探索
• イ.帰りがけ順（後行順）深さ優先探索
• ウ.通りがけ順（中間順）深さ優先探索
• エ.幅優先探索

正解

エ. 幅優先探索

解説

この配列表現では，添字1が根，添字2・3がその子，添字4〜7がさらに次の階層…というように，添字の小さい順が木の上の階層から下の階層へ並ぶ。配列を先頭(添字1)から順に調べると，同じ階層を左から右へ走査し終えてから次の階層へ進むことになり，これは木の階層を上から横方向に探索する幅優先探索に一致する。よってエが正しい。

選択肢ごとの解説

• ア.誤り。先行順(行きがけ順)は『節点→左部分木→右部分木』の順に深く潜る深さ優先探索で，階層順の配列走査とは訪問順序が異なる。
• イ.誤り。後行順(帰りがけ順)は『左部分木→右部分木→節点』の順で，最後に親を訪れる深さ優先探索であり配列の先頭からの順序とは合わない。
• ウ.誤り。中間順(通りがけ順)は『左部分木→節点→右部分木』の順の深さ優先探索で，これも階層順の走査にはならない。
• エ.正しい。添字順=階層順であり，同じ深さの節点を左から順にすべて訪れてから次の深さへ進むので幅優先探索に当たる。