平成26年 秋期 応用情報技術者 午前 問4

配列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 という探索順になります。
図では探索の線が節の下を通るときその節を探索します。


キーワード
・探索順

キーワードの解説
  • 探索順
    問題で書かれた2分木を図にすると、下のようになる。
    A
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

    2分木の探索としては、配列の順に探索する方法と、2分木の図の親子の関係に沿って探索する方法があります。

もっと、「探索順」について調べてみよう。

戻る 一覧へ 次へ