出典：公益社団法人 日本技術士会「技術士第一次試験 過去問題」
2分木のノードを前順(preorder)、間順(inorder)、後順(postorder)で列挙した3つの並びのそれぞれが、どの走査順に対応するかを選ぶ問題。
2分木の3つの走査順(前順・間順・後順)の列挙結果を判別する問題。
① 根の位置で見分ける: 前順=根が先頭、後順=根が最後、間順=根が真ん中(左部分木の後)
② 根A: (ア)ABDECFGは先頭→前順、(ウ)DEBFGCAは最後→後順、(イ)DBEAFCGは真ん中→間順
③ ①
根A、Aの左の子B(子はD、E)、右の子C(子はF、G)の2分木を考える。前順は「根→左部分木→右部分木」の順で、A、B、D、E、C、F、G(ABDECFG)となる。間順は「左部分木→根→右部分木」の順で、D、B、E、A、F、C、G(DBEAFCG)となる。後順は「左部分木→右部分木→根」の順で、D、E、B、F、G、C、A(DEBFGCA)となる。したがって(ア)=前順、(イ)=間順、(ウ)=後順の①が正しい。
2分木の走査は、前順=根→左→右、間順=左→根→右、後順=左→右→根。根が先頭なら前順、最後なら後順、中央付近なら間順である。
キーワード: 2分木、木の走査、前順、間順、後順、データ構造、情報工学部門
同じ問題が計3回出題されています(平成29年度、令和2年度、令和7年度)。