━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ データ構造・アルゴリズム論 確認問題10 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
●問 (2分木の走査) 次の2分木を (1)先行順 (2)中間順 (3)後行順 の各順序で走査するとき， それぞれの処理順を頂点の列として（例えば 1, 3, 6, 5 のように）示せ． １ ／ ＼ ２ ３ ／＼ ／ ４ ５ ６ ────────────────────────────────────── ●答 (2分木の走査) (1) 先行順： １, ２, ４, ５, ３, ６ (2) 中間順： ４, ２, ５, １, ６, ３ (3) 後行順： ４, ５, ２, ６, ３, １ [解説] 先行・中間・後行 の名前は，根をいつ訪れるかを表す． 先行順なら 根→左部分木→右部分木 の順， 中間順なら 左部分木→根→右部分木 の順， 後行順なら 左部分木→右部分木→根 の順に， 根の訪問と部分木の再帰的な走査をする． 2分木の枝に沿って深さ優先順に渡り歩きながら，節を訪れると捉えるなら， 先行順は行きがけ（節の左を通る時）に節を訪問し， 中間順は通りがけ（節の下を通る時）に節を訪問し， 後行順は帰りがけ（節の右を通る時）に節を訪問する． ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 授業のホームページ 山田 俊行 https://www.cs.info.mie-u.ac.jp/~toshi/