アルゴリズム(全97問中69問目)

図の2分木を深さ優先の先行順で探索を行ったときの探索順はどれか。ここで,図中の数字はノードの番号を表す。
13.gif

出典:平成19年秋期 問13

  • 1,2,3,4,5,6
  • 1,2,4,5,3,6
  • 4,2,5,1,3,6
  • 4,5,2,6,3,1
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
解説
2分探索木の深さ優先探索には先行順、中間順、後行順があり、それぞれ次の決まりで2分探索木を巡回します。
13_1.gif
設問の2分探索木を先行順(節→左部分木→右部分木)で巡回すると、
  1. ルートノード1を探索
  2. ノード1の左部分木の節点2を探索
  3. 節点2の左部分木のノード4を探索
  4. 節点4の右部分木のノード5を探索
  5. ノード1の右部分木の節点3を探索
  6. ノード3に左部分木はないので右部分木のノード6を探索
したがって先行順での探索順は「1,2,4,5,3,6」になります。
13_2.gif

Pagetop