修了試験 2023-01-22実施分 基本情報技術者試験 問7

解説

正解は3です。 テキスト表現は「（左部分木、節番号、右部分木）」の三つ組で書き、空の部分木はxで表します。 子をもたない葉の節は番号だけで書けます。 【図の読み取り】 根は節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：× (1，2)は要素が二つしかなく、三つ組の規定に合いません。 右部分木が空であることをxで書く必要があります。 2：× (1，2，3)は節2の右の子が節3であることを表してしまいます。 節3は根であり、根の位置にxを置くのも誤りです。 3：○ 節2の部分木を(1，2，x)、節5の部分木を(4，5，6)とし、根3の左右に置いた正しい表現です。 4：× (6，5，4)は節5の左の子が6、右の子が4であることを表します。 図では左が4、右が6なので左右が逆です。 【ポイント】 2分木の表現では、空の部分木を省略せずに明示することが重要です。 中間順（左、節、右）でたどると、節番号が1から6の順に並ぶことも確認できます。