2分木の探索方法のメモ
応用情報技術者の問題集の探索順の解説がいまいちわからなかったので調べてみた。
数字は配列の添字とする。
まず、行きがけの場合
a．何らかの処理(表示やkeyとの比較など)
b．左のノードへ移動
c．右のノードへ移動
を根(①)から再帰的に行う。
ノード①でのaの処理を1-aと表記すると、
1-a 処理
1-b 左のノードへ移動
2-a 処理
2-b 左のノードへ移動
4-a 処理
4-b なし
4-c なし
2-c 右のノードへ移動
5-a 処理
5-b なし
5-c なし
1-c 右のノードへ移動
3-a 処理
3-b 左のノードへ移動
6-a 処理
6-b なし
6-c なし
3-c 右のノードへ移動
7-a 処理
7-b なし
7-c なし
となり、処理された順番は、①→②→④→⑤→③→⑥→⑦となる。
次に、通りがけの場合
a．左のノードへ移動
b．何らかの処理(表示やkeyとの比較など)
c．右のノードへ移動
を根(①)から再帰的に行う。
1-a 左のノードへ移動
2-a 左のノードへ移動
4-a なし
4-b 処理
4-c なし
2-b 処理
2-c 右のノードへ移動
5-a なし
5-b 処理
5-c なし
1-b 処理
1-c 右のノードへ移動
3-a 左のノードへ移動
6-a なし
6-b 処理
6-c なし
3-b 処理
3-c 右のノードへ移動
7-a なし
7-b 処理
7-c なし
となり、処理された順番は、④→②→⑤→①→⑥→③→⑦となる。
最後に、帰りがけの場合
a．左のノードへ移動
b．右のノードへ移動
c．何らかの処理(表示やkeyとの比較など)
を根(①)から再帰的に行う。
1-a 左のノードへ移動
2-a 左のノードへ移動
4-a なし
4-b なし
4-c 処理
2-b 右のノードへ移動
5-a なし
5-b なし
5-c 処理
2-c 処理
1-b 右のノードへ移動
3-a 左のノードへ移動
6-a なし
6-b なし
6-c 処理
3-b 右のノードへ移動
7-a なし
7-b なし
7-c 処理
3-c 処理
1-c 処理
となり、処理された順番は、④→⑤→②→⑥→⑦→③→①となる。
どの探索方法でも、根から再帰的に調べているが、
問題等で、探索される順を問われる場合には、処理される順のことになる。
応用情報技術者の問題集の探索順の解説がいまいちわからなかったので調べてみた。
まず、行きがけの場合
a．何らかの処理(表示やkeyとの比較など)
b．左のノードへ移動
c．右のノードへ移動
を根(①)から再帰的に行う。
ノード①でのaの処理を1-aと表記すると、
1-a 処理
1-b 左のノードへ移動
2-a 処理
2-b 左のノードへ移動
4-a 処理
4-b なし
4-c なし
2-c 右のノードへ移動
5-a 処理
5-b なし
5-c なし
1-c 右のノードへ移動
3-a 処理
3-b 左のノードへ移動
6-a 処理
6-b なし
6-c なし
3-c 右のノードへ移動
7-a 処理
7-b なし
7-c なし
となり、処理された順番は、①→②→④→⑤→③→⑥→⑦となる。
次に、通りがけの場合
a．左のノードへ移動
b．何らかの処理(表示やkeyとの比較など)
c．右のノードへ移動
を根(①)から再帰的に行う。
1-a 左のノードへ移動
2-a 左のノードへ移動
4-a なし
4-b 処理
4-c なし
2-b 処理
2-c 右のノードへ移動
5-a なし
5-b 処理
5-c なし
1-b 処理
1-c 右のノードへ移動
3-a 左のノードへ移動
6-a なし
6-b 処理
6-c なし
3-b 処理
3-c 右のノードへ移動
7-a なし
7-b 処理
7-c なし
となり、処理された順番は、④→②→⑤→①→⑥→③→⑦となる。
最後に、帰りがけの場合
a．左のノードへ移動
b．右のノードへ移動
c．何らかの処理(表示やkeyとの比較など)
を根(①)から再帰的に行う。
1-a 左のノードへ移動
2-a 左のノードへ移動
4-a なし
4-b なし
4-c 処理
2-b 右のノードへ移動
5-a なし
5-b なし
5-c 処理
2-c 処理
1-b 右のノードへ移動
3-a 左のノードへ移動
6-a なし
6-b なし
6-c 処理
3-b 右のノードへ移動
7-a なし
7-b なし
7-c 処理
3-c 処理
1-c 処理
となり、処理された順番は、④→⑤→②→⑥→⑦→③→①となる。
どの探索方法でも、根から再帰的に調べているが、
問題等で、探索される順を問われる場合には、処理される順のことになる。