応用情報技術者 2017年 秋期 午前2 問05

配列による二分木表現と探索方法【午前2 解説】

要点まとめ

• 結論：配列を先頭から順に調べる操作は幅優先探索に該当します。
• 根拠：配列の添字規則により、親ノードから順に左子・右子が続くため、レベルごとにノードを訪問する幅優先探索と一致します。
• 差がつくポイント：深さ優先探索は再帰的に子ノードを辿るため配列順とは異なり、配列順＝幅優先探索と理解することが重要です。

正解の理由

よくある誤解

解法ステップ

1. 配列の添字規則を確認し、$A[1]$が根であることを理解する。
2. $A[2i]$が左の子、$A[2i+1]$が右の子であることから、ノードはレベル順に格納されていると判断する。
3. 配列を先頭から順に調べる操作は、根からレベルごとにノードを訪問する幅優先探索に該当することを認識する。
4. 深さ優先探索の3種類（行きがけ順・帰りがけ順・通りがけ順）と比較し、訪問順が異なることを確認する。
5. よって正解はエの幅優先探索と結論づける。

選択肢別の誤答解説

• ア: 行きがけ順（先行順）深さ優先探索は、根→左→右の順に再帰的に訪問するため配列順とは異なります。
• イ: 帰りがけ順（後行順）深さ優先探索は、左→右→根の順で訪問し、配列順と一致しません。
• ウ: 通りがけ順（中間順）深さ優先探索は、左→根→右の順で訪問し、配列順とは異なります。
• エ: 幅優先探索はレベルごとに左から右へ訪問するため、配列の添字順と完全に一致します。

補足コラム

FAQ