4-19. 2分木の探索順を求める

　本記事では、2分木の探索順を求める問題演習をします。

問題　次の木をそれぞれの探索法で巡回したとき、たどる値の順番はどうなりますか。例に習って答えてください。

図1. 本問題における2分探索木

（例）幅優先順探索のとき・・A → B → C → D → E

設問1　先行順探索のとき
設問2　中間順探索のとき
設問3　後行順探索のとき

解答

設問1　先行順探索のとき
　A → B → C → D → E
設問2　中間順探索のとき
　B → A → D → C → E
設問3　後行順探索のとき
　B → D → E → C → A

解説

(1) 幅優先順探索
　木の根から順に深さの小さい順に探索し、同じ深さのデータでは、左から右に順番に探索します。

(2) 深さ優先順探索
①　先行順探索（前順探索）
　親にあたる節の探索を部分木の探索の前に行う方法です。
　「親→左の子→右の子」という順番に探索していきます。
　この木では、A → B →（C → D → E）の順番になります。
②中間順探索（間順探索）
　左部分木の探索をしてから、親にあたる節を探索し、そのあとで右部分木の探索を行う方法です。
　「左の子→ 親 → 右の子」という順番に探索していきます。
　この木では、（Aの左の子）→ A → (Aの右の子) = B → A → (D → C → E) の順番になります。
③後行順探索（後順探索）
　左部分木の探索をしてから、右部分木の探索を行い、最後に親の節を探索する方法です。「左の子→ 右の子 → 親」という順番に探索していきます。
　この木では、（A の左の子）→ (A の右の子) → A = B →（D → E → C）→ A の順番になります。

以上です。