HOME»ソフトウェア開発技術者平成19年秋期»午前問13
ソフトウェア開発技術者平成19年秋期 午前問13
問13
図の2分木を深さ優先の先行順で探索を行ったときの探索順はどれか。ここで，図中の数字はノードの番号を表す。
- 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分探索木を巡回します。
設問の2分探索木を先行順(節→左部分木→右部分木)で巡回すると、
- ルートノード1を探索
- ノード1の左部分木の節点2を探索
- 節点2の左部分木のノード4を探索
- 節点4の右部分木のノード5を探索
- ノード1の右部分木の節点3を探索
- ノード3に左部分木はないので右部分木のノード6を探索