応用情報技術者 2021年 春期 午前2 問06
問題文
配列で、を根とし、の左側の子を、右側の子をとみなすことによって、2分木を表現する。このとき、配列を先頭から順に調べていくことは、2分木の探索のどれに当たるか。
選択肢
ア：行きがけ順 (先行順) 深さ優先探索
イ：帰りがけ順 (後行順) 深さ優先探索
ウ：通りがけ順 (中間順) 深さ優先探索
エ：幅優先探索（正解）
配列による2分木表現と探索順序【午前2 解説】
要点まとめ
- 結論：配列を先頭から順に調べる操作は幅優先探索に該当します。
- 根拠：配列のインデックス順は根から各レベルのノードを左から右へ順に並べているため、レベル単位で探索する幅優先探索と一致します。
- 差がつくポイント：深さ優先探索はノードの枝を深く辿る順序であり、配列の単純な先頭から順の走査とは異なる点を理解しましょう。
正解の理由
配列のインデックスは根から始まり、左子、右子と決まっています。この構造は完全2分木のレベル順（幅優先）にノードを格納しているため、配列を先頭から順に調べることはレベルごとに左から右へ探索する幅優先探索と同じです。深さ優先探索の行きがけ順・帰りがけ順・通りがけ順はノードの訪問順が異なり、配列の単純な順序とは一致しません。
よくある誤解
配列の順序を見て「先行順（行きがけ順）などの深さ優先探索だ」と誤解しやすいですが、配列の並びはレベル単位の幅優先探索の結果を表しています。
解法ステップ
- 配列の添字とノードの関係を確認する（が根、が左子、が右子）。
- この添字の並びがどの探索順序に対応するかを考える。
- 深さ優先探索はノードを深く辿るため、添字順とは異なる訪問順になることを理解する。
- 配列の添字順がレベル単位の左から右への訪問であることから幅優先探索と判断する。
選択肢別の誤答解説
- ア: 行きがけ順（先行順）深さ優先探索
→ 根→左→右の順に訪問するため、配列の単純な添字順とは異なります。 - イ: 帰りがけ順（後行順）深さ優先探索
→ 左→右→根の順で訪問し、配列の順序とは合いません。 - ウ: 通りがけ順（中間順）深さ優先探索
→ 左→根→右の順で訪問し、配列の順序とは異なります。 - エ: 幅優先探索
→ レベルごとに左から右へ訪問するため、配列の添字順と一致します。
補足コラム
配列による2分木表現は完全2分木やヒープ構造でよく使われます。幅優先探索はキューを用いてレベル単位でノードを訪問するため、配列の添字順と自然に対応します。一方、深さ優先探索はスタックや再帰で枝を深く辿るため、訪問順が異なります。
FAQ
Q: なぜ配列の添字順が幅優先探索になるのですか？
A: 配列は根から始まり、各レベルのノードを左から右へ順に格納しているため、添字順がレベル単位の訪問順（幅優先）と一致します。
A: 配列は根から始まり、各レベルのノードを左から右へ順に格納しているため、添字順がレベル単位の訪問順（幅優先）と一致します。
Q: 深さ優先探索は配列で表現できないのですか？
A: 深さ優先探索の訪問順は配列の単純な添字順とは異なるため、同じ配列順で表現することはできません。
A: 深さ優先探索の訪問順は配列の単純な添字順とは異なるため、同じ配列順で表現することはできません。
関連キーワード: 2分木、幅優先探索、深さ優先探索、配列表現、木構造、探索順序
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！