修了試験 2015-07-26実施分 基本情報技術者試験 問5

解説

正解は3です。 2分木を、問題で決めたテキスト表現の規則に従って書き表す問題です。 図では、根が節3です。 節3の左の子が節2、右の子が節5です。 節2の左の子は節1で、右の子はありません。 節5の左の子が節4、右の子が節6です。 【計算】 節2の部分木は、左が節1、右が空なので（1, 2, x）と表します。 節5の部分木は、左が節4、右が節6なので（4, 5, 6）と表します。 根の節3は、左部分木（1, 2, x）、右部分木（4, 5, 6）を使って表します。 全体は（(1, 2, x), 3, (4, 5, 6)）となります。 【選択肢別解説】 1：× 節2の部分木が（1, 2）となっており、3要素の形になっていません。 規則(2)により、空の右部分木はxと書く必要があります。 2：× 根の位置にxが書かれており、根の節番号3が中央にありません。 （1, 2, 3）も節3を節2の右の子として扱っており、図と合いません。 3：○ 節2の部分木（1, 2, x）、根の3、節5の部分木（4, 5, 6）が規則どおりの順に並んでいます。 図の木の形と完全に一致します。 4：× 右部分木が（6, 5, 4）となっており、左右が逆です。 図では節4が左の子、節6が右の子なので、（4, 5, 6）が正しい表現です。 【ポイント】 この表現は「左部分木、節、右部分木」の順で、中間順（通りがけ順）と同じ並びです。 子がない側を省略せずxで書くことが、規則を読み取るうえでの要点です。