技術士試験ナビ

技術士試験対策・テキスト・過去問題解説を発信します。

技術士第一次試験専門科目 平成29年度 Ⅲ-1

 次に示す2分木のノードを,行きがけ順(あるいは前順,preorder),通りがけ順(あるいは中順,inorder),帰りがけ順(あるいは後順,postorder)の3通りの方法で列挙した。

f:id:honmurapeo:20180430102826p:plain

 次の(ア)〜(ウ)は,これら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が最後なので、帰りがけ順になります。