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