平成29年度 III-1

解説

この問題で問われていること

2分木の走査順序(前順・中順・後順)の定義を、具体的な木に適用する問題。

解き方

① 見分け方: 根Aが先頭=行きがけ順、根Aが末尾=帰りがけ順、根Aが真ん中(左部分木の後)=通りがけ順
② ア DBEAFCG はAが真ん中 → 通りがけ、イ ABDECFG は先頭がA → 行きがけ、ウ DEBFGCA は末尾がA → 帰りがけ
③ ④

正解が正しい理由

木は、根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。これは(ウ)。したがって、ア=通りがけ順、イ=行きがけ順、ウ=帰りがけ順の④が正しい。

各選択肢について

• ① アが行きがけ順、イが帰りがけ順、ウが通りがけ順となっており、すべて誤り。
• ② アが行きがけ順(ABDECFG)ではなく、DBEAFCGなので、アが誤り。
• ③ アが帰りがけ順となっており、誤り。
• ④ ア=通りがけ順(DBEAFCG)、イ=行きがけ順(ABDECFG)、ウ=帰りがけ順(DEBFGCA)で、正しい。これが正答。
• ⑤ イが帰りがけ順、ウが行きがけ順となっており、誤り。

覚えるべきポイント

行きがけ順(前順)=根が最初、帰りがけ順(後順)=根が最後、通りがけ順(中順)=根が左右の部分木の間。列の先頭が根なら前順、末尾が根なら後順。