| ソフトウェア開発技術者試験 |
2007年度 ＝ 平成19年度・春期 |
午前 |
問10 |
配列A[1]，A[2]，…，A[n ]で，A[1]を根とし、A[i ]の左側の子をA[2i ]，右側の子をA[2i ＋1]とみなすことによって、２分木を表現する。このとき、配列を先頭から順に調べていくことは、２分木の探索のどれに当たるか。
ア 行きがけ順（先行順）深さ優先探索
イ 帰りがけ順（後行順）深さ優先探索
ウ 通りがけ順（中間順）深さ優先探索
エ 幅優先探索
エ
横型探索とも呼ばれる幅優先探索（breadth-first search）は、レベルの低い点から始めて、左側から右側へ、それが終わると次のレベルへとたどっていく方法です。
n が7であれば、探索は、以下のようになります。
→ １ →
／ ＼
→ ２ → ３ →
／ ＼ ／ ＼
→ ４ → ５→６ → ７ →
