サンプル問題[科目B]問9 木構造を走査するプログラム

サンプル問題 [科目B]問9

問9

　次の記述中の　に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は1から始まる。

　手続 order は，図の2分木の，引数で指定した節を根とする部分木をたどりながら，全ての節番号を出力する。大域の配列 tree が図の2分木を表している。配列 tree の要素は，対応する節の子の節番号を，左の子，右の子の順に格納した配列である。例えば，配列 tree の要素番号1の要素は，節番号1の子の節番号から成る配列であり，左の子の節番号2，右の子の節番号3を配列｛2，3｝として格納する。手続 order を order(1) として呼び出すと，　の順に出力される。

〔プログラム〕

1，2，3，4，5，6，7，8，9，10，11，12，13，14
1，2，4，8，9，5，10，11，3，6，12，13，7，14
8，4，9，2，10，5，11，1，12，6，13，3，14，7
8，9，4，10，11，5，2，12，13，6，14，7，3，1

分類

アルゴリズムとプログラミング » データ構造及びアルゴリズム

正解

ウ

解説

プログラム order を見ると、処理対象となっている節が有する子の数（tree[n]の要素数）によって、3つの処理に分岐させています。

その節が2つの子を持つ（tree[n]の要素数が2）: 要素の1番目の節番号（左の子）を探索する、自身の節番号を出力する、要素の2番目の節番号（右の子）を探索する（tree[n]の要素数が1）
その節が1つの子を持つ: 要素の1番目の節番号（左の子）を探索する、自身の節番号を出力する
その節が子を持たない（tree[n]の要素数が0）: 自身の節番号を出力する

節番号1を根として探索をすると、以下のように処理されています。

order(1)を呼び出す
配列 tree[1] は2つの要素{2, 3}を持つので、そのうち1番目の要素（tree[1][1]）である節番号2を対象として order(2) を呼び出す
配列 tree[2] は2つの要素{4, 5}を持つので、そのうち1番目の要素（tree[2][1]）である節番号4を対象として order(4) を呼び出す
配列 tree[4] は2つの要素{8, 9}を持つので、そのうち1番目の要素（tree[4][1]）である節番号8を対象として order(8) を呼び出す
配列 tree[8] は要素を持たないので8を出力して終了し、呼出し元の order(4) の処理に戻る
order(4) は自身の節番号4を出力した後、2番目の要素（tree[4][2]）である節番号9を対象として order(9) を呼び出す
配列 tree[9] は要素を持たないので9を出力して、order(4) の処理に戻る

まだ処理は続いていきますが、ここまでの出力順は8→4→9であることから、正解は「ウ」であると判断できます。