図の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分木の根であるノード1を調べる。 |
A | ノード1の左の子であるノード2を根とする部分木の処理を行い、部分木の根であるノード2を調べる。 |
B | ノード2の左の子であるノード4を根とする部分木の処理を行い、部分木の根であるノード4を調べる。 ノード4に子がないので、次はノード2の右の子を調べる。 |
C | ノード2の右の子であるノード5を根とする部分木の処理を行い、部分木の根であるノード5を調べる。 ノード5に子がなく、ノード2の子の処理が終わったので、次はノード1の右の子を調べる。 |
D | ノード1の右の子であるノード3を根とする部分木の処理を行い、部分木の根であるノード3を調べる。 ノード3に左の子がないので、次は右の子を処理する。 |
E | ノード3の右の子であるノード6を根とする部分木の処理を行い、部分木の根であるノード6を調べる。 すべてのノードを調べ終わったので終了。 |
【キーワード】
・2分木の探索