配列A[1]、A[2]、…、A[n ]でA[1]を根とし、A[i ]の左側の子をA[2i ]、右側の子をA[2i +1]とみなすことによって、2分木を表現する。 このとき、配列を先頭から順に調べて行くことは、2分木の探索のどれに当たるか。
ア | 行きがけ順(先行順)深さ優先探索 |
イ | 帰りがけ順(後行順)深さ優先探索 |
ウ | 通りがけ順(中間順)深さ優先探索 |
エ | 幅優先探索 |
答え エ
【解説】
2分木の探索で、配列の順に探索する方法(2分木図では、根→2段目の節全部→3段目の節全部→4段目の節全部(1→2→3→4→5→6→7→8→9→10→11→12→13→14→15)と探索していく方法)は幅優先探索(エ)といいます。
2分木の深さ優先探索を図で表すと下のようになります。
ア | 行きがけ順(先行順)深さ優先探索では、1→2→4→8→9→5→10→11→3→6→12→12→7→14→15 という探索順になります。 図では探索の線が節の左を通るときその節を探索します。 |
イ | 帰りがけ順(後行順)深さ優先探索では、8→9→4→10→11→5→2→12→13→6→14→15→7→3→1 という探索順になります。 図では探索の線が節の右を通るときその節を探索します。 |
ウ | 通りがけ順(中間順)深さ優先探索では、8→4→9→2→10→5→11→1→12→6→13→3→14→7→15 という探索順になります。 図では探索の線が節の下を通るときその節を探索します。 |
【キーワード】
・探索順
A |
|