アルゴリズム(全101問中73問目)
No.73解説へ
図の2分木を深さ優先の先行順で探索を行ったときの探索順はどれか。ここで，図中の数字はノードの番号を表す。
出典：平成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分探索木を巡回します。
設問の2分探索木を先行順(節→左部分木→右部分木)で巡回すると、
- ルートノード1を探索
- ノード1の左部分木の節点2を探索
- 節点2の左部分木のノード4を探索
- 節点4の右部分木のノード5を探索
- ノード1の右部分木の節点3を探索
- ノード3に左部分木はないので右部分木のノード6を探索
広告