基本情報技術者試験 科目B サンプル問題 問9の解説｜2分木をたどって節番号を出力する order

科目B サンプル問題 問9難易度 ★★★★擬似言語・2分木・再帰最終更新 2026-09-22

答えは14個の並びですが、追うのは最初の3個だけで決まります。降りる → 戻る → 右へ、の3手です。

出題

出典：基本情報技術者試験 科目B サンプル問題 問9

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

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

手続order をorder(1)として呼び出すと，　 の順に出力される。

※ 親子は配列 tree でも確かめられます。たとえば tree[4] は {8, 9} なので、節4 の左の子が 8、右の子が 9 です。8番目から14番目は {} ＝ 節8〜14 に子はありません。

図　プログラムが扱う2 分木（正典 p14 の図。作図は当サイト）

注記1　○の中の値は節番号である。／注記2　子の節が一つの場合は，左の子の節とする。

〔プログラム〕

大域: 整数型配列の配列: tree ← {{2, 3}, {4, 5}, {6, 7}, {8, 9},
                                {10, 11}, {12, 13}, {14}, {}, {}, {},
                                {}, {}, {}, {}}  /​/ {}は要素数0の配列

○order(整数型: n)
  if (tree[n]の要素数 が 2 と等しい)
    order(tree[n][1])
    nを出力
    order(tree[n][2])
  elseif (tree[n]の要素数 が 1 と等しい)
    order(tree[n][1])
    nを出力
  else
    nを出力
  endif

解答群

ア　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(1) を呼ぶと、まず 8、次に 4 が出る

プログラムに行番号を付けておきます（当サイトで付けたもので、出題にはありません）。

 1: ○order(整数型: n)
 2:   if (tree[n]の要素数 が 2 と等しい)
 3:     order(tree[n][1])
 4:     nを出力
 5:     order(tree[n][2])
 6:   elseif (tree[n]の要素数 が 1 と等しい)
 7:     order(tree[n][1])
 8:     nを出力
 9:   else
10:     nを出力
11:   endif

1個目の 8 が出るまで

1. order(1) が始まる。n は 1。tree[1] は ｛2，3｝ なので子は2つ。2行目が真なので3行目へ。3行目は「左の子を呼ぶ」── tree[1][1] は 2 なので order(2) を呼び、ここで止まって待ちます。まだ何も出力していません。
2. order(2) が始まる。n は 2。tree[2] は ｛4，5｝ で子は2つ。同じく3行目で order(4) を呼んで止まります。
3. order(4) が始まる。n は 4。tree[4] は ｛8，9｝ で子は2つ。同じく3行目で order(8) を呼んで止まります。
4. order(8) が始まる。n は 8。tree[8] は ｛｝ ＝ 子がありません。2行目も6行目も偽なので else の10行目へ。呼ぶ相手がいないので、自分の 8 を出力します。これが1個目。

降りるあいだ（1〜3）は、どの呼び出しも「左の子を呼ぶ」で止まっていて、出力の4行目にはまだ誰も進んでいません。だから最初に出るのは、根の 1 ではなく、左へ降りきった 8 です。

2個目の 4 が出るまで

5. order(8) が終わる。11行目まで来たので、この呼び出しはおしまい。order(8) を呼んだのは order(4) の3行目でした。だから order(4) に戻り、その次の4行目から続きます。
6. order(4) の4行目。「nを出力」の行です。いま動いているのは order(4) なので n は 4。4 を出力します。これが2個目。

呼ばれた先が終わると、呼んだ側は止まっていた行の次から動きだします。8 が済んだので、order(4) の続き＝「自分を出力」が動いて 4 が出ました。

2個出れば、もう決まる

ここまでで 8，4。解答群の先頭だけを抜き出して見比べます。

ア　 1，2，3，…
イ　 1，2，4，…
ウ　 8，4，9，…
エ　 8，9，4，…

1個目の 8 で ア・イ が消え、2個目の 4 で エ も消えます。14個を最後まで追わなくても、2個で1つに決まります。（下のシミュレータでは、念のため3個目の 9 まで動かしています。）

答え合わせ

正解は ウ です。出力の位置を取り違えると、別の選択肢になります。「nを出力」を左の子をたどる前に置くと イ（1，2，4，8，9，…）、右の子をたどったあとに置くと エ（8，9，4，…，1）。アは節番号を1から並べただけです。

3個目まで、1コマずつ動かして確かめる

ここまでの流れを、コードの行と突き合わせて追えます。

次に読む

この問題でどこに手間取ったかで、行き先が変わります。