図の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分木の探索
- 2分木の探索
2分木構成のデータの探索法には、行きがけ順探索、通りがけ順探索、帰りがけ順探索、深さ優先探索、幅優先探索などがある。- 行きがけ順、通りがけ順、帰りがけ順探索
2分木の構造は根とその子を根とする部分木という再帰的なつくりになっているので、探索するときも再帰的なアルゴリズムで行うことができ、根から調べるのを行きがけ順、左の子を根とする部分木を調べて、根を調べ、右の子を根とする部分木を調べるのを通りがけ順、部分木から調べて最後に根を調べるのを帰りがけ順という。 - 深さ優先探索
根から最も遠いノードから調べる方法である。 - 幅優先探索
根に近いノードから調べる方法である。
- 行きがけ順、通りがけ順、帰りがけ順探索
もっと、「2分木の探索」について調べてみよう。
戻る
一覧へ
次へ