応用情報技術者試験 応用情報技術者試験 令和3年度春期 午前 問6: 配列 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 分木の探索のどれに当たるか。

選択肢

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

正解

エ. 幅優先探索

解説

この配列表現では、A[1]が根（深さ1）、A[2]・A[3]が深さ2、A[4]〜A[7]が深さ3…と、添字の順に同じ深さのノードが左から並ぶ。したがって配列を先頭から順に調べると、根から1階層ずつ同じ深さのノードを左から右へたどることになり、これは木を浅い階層から順に横方向にたどる幅優先探索に相当する。よって正解はエである。

選択肢ごとの解説

• ア.行きがけ順（先行順）は「ノード→左部分木→右部分木」の順に深く潜りながらたどる深さ優先探索であり、配列を先頭から順に読む順序とは一致しないため誤り。
• イ.帰りがけ順（後行順）は「左部分木→右部分木→ノード」の順にたどる深さ優先探索であり、配列の添字順とは一致しないため誤り。
• ウ.通りがけ順（中間順）は「左部分木→ノード→右部分木」の順にたどる深さ優先探索であり、配列の添字順とは一致しないため誤り。
• エ.配列の添字順は根から深さの浅い順に、各階層を左から右へたどる並びであり、これは幅優先探索の訪問順そのものなので正しい。