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

正解

エ. 幅優先探索

正答率 66.9%（598人中 400人が正解）

問題の解説

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

選択肢ごとの解説

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