アルゴリズム (全82問中54問目)

No.54

図の2分木を深さ優先の先行順で探索を行ったときの探索順はどれか。ここで,図中の数字はノードの番号を表す。
13.gif/image-size:187×108
  • 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/image-size:503×200
設問の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/image-size:187×110
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop