次に示す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が最後なので、帰りがけ順になります。