応用情報技術者 2014年 秋期 午前2 問04
問題文
配列で、を根とし、の左側の子を、右側の子をとみなすことによって、2分木を表現する。このとき、配列を先頭から順に調べていくことは、2分木の探索のどれに当たるか。
選択肢
ア：行きがけ順 (先行順) 深さ優先探索
イ：帰りがけ順 (後行順) 深さ優先探索
ウ：通りがけ順 (中間順) 深さ優先探索
エ：幅優先探索（正解）
配列による2分木表現と探索順序【午前2 解説】
要点まとめ
- 結論：配列を先頭から順に調べる操作は幅優先探索に該当します。
- 根拠：配列の添字規則から、親ノードの次にその子ノードが続くため、レベルごとにノードを順に訪問する形になるからです。
- 差がつくポイント：深さ優先探索は再帰的に子ノードを辿るため、配列の単純な順番走査とは異なる点を理解しましょう。
正解の理由
配列でを根とし、を左の子、を右の子とする表現は完全2分木のレベル順格納を意味します。配列を先頭から順に調べると、根から始まり、同じレベルのノードを左から右へ順に訪問することになるため、これは幅優先探索（レベル順探索）に該当します。深さ優先探索（行きがけ順・帰りがけ順・通りがけ順）はノードの深さ方向に進むため、配列の単純な順序とは異なります。
よくある誤解
配列の順番で調べることを「行きがけ順」などの深さ優先探索と混同しやすいですが、深さ優先探索は再帰的に子ノードを辿るため、配列の単純な順序とは異なります。
解法ステップ
- 配列の添字規則を確認し、が根であることを理解する。
- とがそれぞれ左・右の子であることから、配列はレベル順にノードを格納していると認識する。
- 配列を先頭から順に調べる操作は、根から始まりレベルごとに左から右へノードを訪問することと同義であると判断する。
- これが幅優先探索（レベル順探索）であると結論づける。
選択肢別の誤答解説
- ア（行きがけ順）：深さ優先探索の一種で、根→左→右の順に訪問するため、配列の単純な順序とは異なる。
- イ（帰りがけ順）：深さ優先探索の一種で、左→右→根の順に訪問するため、配列の順序とは合わない。
- ウ（通りがけ順）：深さ優先探索の一種で、左→根→右の順に訪問するため、配列の順序とは異なる。
- エ（幅優先探索）：レベルごとに左から右へ訪問するため、配列の先頭から順に調べる操作に一致する。
補足コラム
配列による2分木表現は完全2分木やヒープ構造でよく用いられます。幅優先探索はキューを用いてレベル順にノードを訪問するアルゴリズムであり、配列の添字規則と自然に対応しています。一方、深さ優先探索はスタックや再帰を用いてノードの深さ方向に探索を進めます。
FAQ
Q: なぜ配列の添字がやになるのですか？
A: 完全2分木を配列で表現する際、親ノードの添字に対し左の子が、右の子がとなる規則が一般的です。
A: 完全2分木を配列で表現する際、親ノードの添字に対し左の子が、右の子がとなる規則が一般的です。
Q: 幅優先探索はどのような場面で使われますか？
A: 最短経路探索やレベルごとの処理が必要な場合に使われ、ツリーの各レベルを順に処理したいときに有効です。
A: 最短経路探索やレベルごとの処理が必要な場合に使われ、ツリーの各レベルを順に処理したいときに有効です。
関連キーワード: 2分木、幅優先探索、深さ優先探索、配列表現、ヒープ
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！