2分木を入力するためのテキスト表現を，次のように規定した。
図のように節に番号をつけたとき，テキスト表現として適切なものはどれか。
〔テキスト表現〕
(1) （左部分木の節番号又はテキスト表現，節番号，右部分木の節番号又はテキスト表現）と表す。
(2) 部分木が空のときはxを書く。
正答3
解説
正解は3です。
2分木を、決められた規則のテキストで表す問題です。
規則は「（左部分木，節番号，右部分木）」の3要素で、部分木が空のときはxを書きます。
図では、根が節3、その左の子が節2、右の子が節5です。
節2は左の子に節1をもち、右の子はありません。
節5は左の子に節4、右の子に節6をもちます。
【選択肢別解説】
1：× 節2の部分木を(1, 2)と2要素で書いています。
右部分木が空なのでxを書く必要があり、正しくは(1, 2, x)です。
2：× 根の位置にxを書き、節3を左部分木の中に入れています。
根は節3なので、真ん中に3を書かなければなりません。
3：○ 節2の部分木は(1, 2, x)、節5の部分木は(4, 5, 6)です。
根の節3をはさんで((1, 2, x), 3, (4, 5, 6))となり、規則どおりです。
4：× 右部分木を(6, 5, 4)と書いています。
図では節4が左、節6が右なので、正しくは(4, 5, 6)です。
【ポイント】
この表現は、左部分木、節、右部分木の順に並べる中間順の考え方と同じです。
空の部分木もxで明示し、常に3要素にそろえる点に注意しましょう。