2分木の走査（中間順）【基本情報技術者試験 科目B サンプル問題】

← 科目Bの公開問題一覧へ戻る

　基本情報技術者試験の科目Bのサンプル問題を題材に，2分木の走査（中間順）について学習します。この問題では，左の部分木 → 節 → 右の部分木の順に節をたどる処理と，再帰呼出しによる処理の流れを確認します。

（令和4年度12月公開） 基本情報技術者試験 サンプル問題 科目B 問9

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

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

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

〔プログラム〕

大域: 整数型配列の配列: 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

【参考】	「データ構造の基礎まとめ（2分木とは）」

この問題のポイント

　この問題から学べることは，

• 2分木の構造と，左の子・右の子の関係
• 左の部分木 → 節 → 右の部分木の順にたどる中間順走査
• 再帰呼出しによって，部分木を順番にたどる処理
• プログラムの実行順序を追跡して，節の出力順を求める方法

です。特に，中間順走査では「左の部分木 → 節 → 右の部分木」の順に処理することを理解しておきましょう。

基本情報技術者試験の学習におすすめの参考書

基本情報技術者試験の合格を目指す方におすすめの参考書です。