データ構造(全40問中6問目)
No.6解説へ
配列A[1]，A[2]，…，A[n]で，A[1]を根とし，A[i]の左側の子をA[2i]，右側の子をA[2i＋1]とみなすことによって，2分木を表現する。このとき，配列を先頭から順に調べていくことは，2分木の探索のどれに当たるか。
出典：令和3年春期 問 6
- 行きがけ順(先行順)深さ優先探索
- 帰りがけ順(後行順)深さ優先探索
- 通りがけ順(中間順)深さ優先探索
- 幅優先探索
広告
解説
仮に配列[1, 2, 3, 4, 5, 6, 7]があったとき、設問のルールにより表される2分木は次の構造になります。
この木構造において配列を先頭から順に1，2，…と調べていくと、以下の順序で要素を調べていくことなります。
根から近い順に階層ごとに探索することになるため「幅優先探索」が適切となります。よって「エ」が正解です。
なお、深さ優先探索は、根から開始して左の（右の）部分木優先で最も深い葉まで到達してから、一つ前の節まで戻り他方の部分木の探索を行うことを繰り返す方法です。先行順、後行順、中間順は参照するタイミングが違うだけです。
なお、深さ優先探索は、根から開始して左の（右の）部分木優先で最も深い葉まで到達してから、一つ前の節まで戻り他方の部分木の探索を行うことを繰り返す方法です。先行順、後行順、中間順は参照するタイミングが違うだけです。
- 行きがけ順(先行順) … 訪問したタイミングで調べる
- 帰りがけ順(後行順) … 移動する子がなくなったタイミングで調べる
- 通りがけ順(中間順) … 左の子に移動できなくなったタイミングで調べる
広告