2分木の探索

■ 解き方の方針 子が二つある節では「左の部分木→自分→右の部分木」、子が一つなら「左の部分木→自分」の順です。これは2分木の 間順序(in-order) 走査です。 ■ 左側の部分木 節4:左の8、自分の4、右の9 → 8, 4, 9 節5:左の10、自分の5、右の11 → 10, 5, 11 節2:節4、自分の2、節5 → 8, 4, 9, 2, 10, 5, 11 ■ 右側の部分木 節6:左の12、自分の6、右の13 → 12, 6, 13 節7:子は左の14だけなので、14を出力してから7 → 14, 7 節3:節6、自分の3、節7 → 12, 6, 13, 3, 14, 7 ■ 根1を含めて結合する 節1では、節2の結果、自分の1、節3の結果の順につなぎます。 8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7 ■ 正解と誤答の見分け方 したがって、正解は ウ です。 根1を最初に出すのは先行順、最後に出すのは後行順です。このプログラムでは左右の再帰呼出しの間にnを出力します。

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

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

問題画像

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

図 プログラムが扱う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

出典令和4年度 基本情報技術者試験 科目B サンプル問題 問9
ア
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