基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

３分探索木で深さ優先探索の通りがけ順(中間順)と帰りがけ順(後行順)についての質問です。

      通りがけ順
帰りがけ順
              2
3
           /  |  \
/  |  \
          1  3  4
1  2  4

上にある探索順で大丈夫でしょうか。
間違っていたら回答してもらえるとありがたいです。
あまり３分探索の解説サイトが見当たらないので、質問させていただきました。

図が見づらいので

通りがけ順
  2
/ | \
134

帰りがけ順
  3
/ | \
124

多分木では、
通りがけ（中間順、inorder）の走査はさらに別の規則が与えられないと決まらないです。

ある節から見て、子が3つあるとき、
(子1, 子2) 節 (子3)、の状態を「節が中間位置にある」というのか、
それとも、
(子1) 節 (子2, 子3)、の状態を「節が中間位置にある」というのか、
が決まらないので。

帰りがけ（後行順、postorder）の正解はこちら。

 ↓④↑
 ／｜＼
① ② ③

回答ありがとうございます。
通りがけ順だと、中間位置がどこにあるかというのがあらかじめ問題文に書かれているということですね。
帰りがけ順では、"子をすべて通ってから節"という解釈で大丈夫でしょうか。

> 帰りがけ順では、"子をすべて通ってから節"という解釈で大丈夫でしょうか。

はい、それで正しいです。

> 通りがけ順だと、中間位置がどこにあるかというのが
> あらかじめ問題文に書かれているということですね。

多分木における通りがけ順が出題されたという例を私は知りません。

理解できました。
ご回答ありがとうございました。