次に示す2分木のノードを，行きがけ順（あるいは前順，preorder），通りがけ順（あるいは中順，inorder），帰りがけ順（あるいは後順，postorder）の3通りの方法で列挙した。
次の（ア）〜（ウ）は，これら3通りの方法によるノードの列挙を，順不同で並べたものである。最も適切な組合せはどれか。
（ア）D B E A F C G
（イ）A B D E C F G
（ウ）D E B F G C A
| ア | イ | ウ | |
| ① | 行きがけ順 | 帰りがけ順 | 通りがけ順 |
| ② | 行きがけ順 | 通りがけ順 | 帰りがけ順 |
| ③ | 帰りがけ順 | 行きがけ順 | 通りがけ順 |
| ④ | 通りがけ順 | 行きがけ順 | 帰りがけ順 |
| ⑤ | 通りがけ順 | 帰りがけ順 | 行きがけ順 |
答え
④
解説
木のすべての節点を組織だった方法で（原則上から下、左から右）たどることを、「木の巡回（traverse）」または、「木のなぞり」と言います。それぞれの方法の意味は次の通りです。
- 行きがけ順（あるいは前順，preorder）
最初にたどりついた際に出力 - 通りがけ順（あるいは中順，inorder）
左の部分木のなぞりが終わった後に出力 - 帰りがけ順（あるいは後順，postorder）
最後にたどりついた際に出力
設問の2分木における木の巡回順序は、“A B D B E B A C F C G C A” となりますが、どのタイミングで節点を出力するかが、上記方法によって異なります。
（ア）D B E A F C G
最も左のDが最初かつAが最後ではないので、通りがけ順になります。
（イ）A B D E C F G
Aが最初なので、行きがけ順になります。
（ウ）D E B F G C A
Aが最後なので、帰りがけ順になります。