新らしくなった基本情報 科目 B 20問バージョン アルゴリズムとプログラミング サンプル問題9をJavaにしてみました
山崎講師2023 年 4 月からIPA （独立行政法人情報処理推進機構）の基本情報技術者試験の制度が変更されました。
ここでは、「基本情報技術者試験 科目 B のサンプル問題20問バージョン」の中から、アルゴリズムとプログラミングの問題を取り上げ、Javaのソースコードを示します。
新人エンジニア研修に参加されている皆様の参考になれば幸いです。
【Javaプログラム】
public class Q9 {
// Javaの配列が0から始まるため先頭要素に{}（空の配列）を追加しています。
static int[][] tree = { {}, { 2, 3 }, { 4, 5 }, { 6, 7 }, { 8, 9 }, { 10, 11 }, { 12, 13 }, { 14 }, {}, {}, {}, {},
{}, {}, {}, {} };
//本問で問われている手続
static void order(int n) {
if (tree[n].length == 2) {
order(tree[n][0]);
System.out.print(n + " ");
order(tree[n][1]);
} else if (tree[n].length == 1) {
order(tree[n][0]);
System.out.print(n + " ");
} else {
System.out.print(n + " ");
}
}
//以下はテスト
public static void main(String[] args) {
order(1);
}
}【結果】
| 8 4 9 2 10 5 11 1 12 6 13 3 14 7 |
【プログラムの解説】
このプログラムは、二分木を表現し、その木をインオーダー順（中間順）で巡回して出力します。
インオーダー順とは、まず左部分木、次にルート、そして最後に右部分木を訪れるという巡回方法です。
以下がプログラムの概要です。
treeという二次元配列を使用して二分木を表現しています。
この二分木の各要素は、その要素の子ノードを表すインデックスの配列として格納されます。
例えば、tree[1]は {2, 3}です。これは、ノード1の子ノードがノード2とノード3であることを意味します。
orderという再帰的なメソッドを使用して、インオーダー順序で二分木を巡回します。
インオーダー順序では、左の子ノード、親ノード、右の子ノードの順に処理を行います。orderメソッドは、引数nに与えられたノードから巡回を開始し、再帰的に子ノードを巡回します。
mainメソッドでは、ノード1（木のルート）からインオーダー順序で巡回を開始します。
このプログラムを実行すると、二分木のインオーダー順序での巡回結果である 8 4 9 2 10 5 11 1 12 6 13 3 14 7 が出力されます。
