基本情報技術者試験〔科目B〕演習2022年サンプル問題 問9（二次元配列、再帰）
問9（二次元配列、再帰）
次の記述中の□に入れる正しい答えを、解答群の中から選べ。ここで、配列の要素番号は1から始まる。
手続orderは、図の２分木の、引数で指定した節を根とする部分木をたどりながら、全ての節番号を出力する。大域の配列treeが図の２分木を表している。配列treeの要素は、対応する節の子の節番号を、左の子、右の子の順に格納した配列である。例えば、配列treeの要素番号1の要素は、節番号1の子の節番号から成る配列であり、左の子の節番号2、右の子の節番号3を配列{2, 3}として格納する。
手続orderをorder(1)として呼び出すと、□の順に出力される。
〔プログラム〕
1: 大域: 整数型配列の配列: tree ← {{2, 3}, {4, 5}, {6, 7}, {8, 9}, {10, 11}, {12, 13}, {14}, {}, {}, {}, {}, {}, {}, {}} // {} は要素数0の配列
2: 〇order (整数型: n)
3: if (tree[n]の要素数が2と等しい)
4: order (tree[n][1])
5: nを出力
6: order (tree[n][2])
7: elseif (tree[n]の要素数が1と等しい)
8: order (tree[n][1])
9: n を出力
10: else
11: nを出力
12: endif
解答：8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7
用語の意味
1. 二分木（Binary Tree）
定義:
各節（ノード）が最大2つの子を持つことができる木構造のこと。
木構造とは、親と子の階層関係を持つデータの構造。
特徴:
親と子を明確に区別する。
子が「左の子」と「右の子」に分かれるのが二分木の特徴。
2. 根（Root）
定義:
二分木の最上部に位置する節（ノード）のこと。
二分木全体の出発点であり、親を持たない節。
例:
問題における根は「節番号1」である。
3. 子（Child）
定義:
ある節（親ノード）から直接接続されている次の節を「子」という。
二分木では、1つの節が最大2つの子（左の子、右の子）を持つことができる。
例:
問題では、節番号1の子は節番号2（左の子）と節番号3（右の子）。
4. 節（Node）
定義:
木構造を構成する各要素のこと。節、ノード、頂点は同じ意味で使われる。
各節にはデータや他の節との関係（親・子）が格納されている。
例:
問題の木構造では、「節番号1」「節番号2」などが節に該当する。
5. 葉ノード（Leaf Node）
定義:
子を持たない節のこと。木構造の終端に位置する。
この節をたどると、それ以上深い階層は存在しない。
例:
問題では、「節番号8」「節番号9」「節番号10」などが葉ノードである。
6. 中間順序（In-order Traversal）
定義:
二分木をたどる際の順序の1つ。
順序は以下の通り:
左の子を訪問する。
自分自身（親ノード）を訪問する。
右の子を訪問する。
特徴:
再帰的なアルゴリズムで実装するのが一般的である。
中間順序でたどると、二分木の節が小さい順や並べ替えされた順に処理されることが多い（例えば、ソート木の場合）。
例:
問題の木構造では、中間順序の出力は「8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7」となる。
大域の配列とは
大域の配列とは、プログラム全体（すべての関数やメソッド）からアクセス可能な配列のことを指す。これは**グローバル変数（Global Variable）**の一種であり、特定のスコープに限定されず、プログラムのどこからでも参照または変更が可能。
1. 大域の配列の特徴
スコープが広い:
配列はプログラム全体で共有される。
関数やメソッドの外側で宣言されているため、任意の場所でアクセス可能。
長期間保持される:
プログラムの実行期間中、配列の内容は保持される。
どこでも変更可能:
どの部分のコードからでも配列の内容を変更できるため、意図しないバグの原因となることがある。
二分木の構造 (配列 tree に基づく):
根 (節番号1) の子: 左が節番号2、右が節番号3
節番号2の子: 左が節番号4、右が節番号5
節番号3の子: 左が節番号6、右が節番号7
節番号4の子: 左が節番号8、右が節番号9
節番号5の子: 左が節番号10、右が節番号11
節番号6の子: 左が節番号12、右が節番号13
節番号7の子: 左が節番号14
その他の節は葉ノードであり子を持たない（空配列 {}）。
プログラムの動作
order 手続きは節番号 n を根とする部分木をたどる。
節の子の数によって動作が異なる。
子が2つある場合:
左の子を再帰的に訪問。
節番号を出力。
右の子を再帰的に訪問。
子が1つある場合:
唯一の子を再帰的に訪問。
節番号を出力。
子がない場合: 節番号を出力。
ルートから順に処理を行うため、この処理は 中間順序（in-order traversal） に対応する。
中間順序の出力
木を中間順序でたどると以下の順序で節番号が出力される。
節番号1を根とする木:
節番号2を訪問
節番号4を訪問
節番号8（子なし → 出力: 8）
節番号4（出力: 4）
節番号9（子なし → 出力: 9）
節番号2（出力: 2）
節番号5を訪問
節番号10（子なし → 出力: 10）
節番号5（出力: 5）
節番号11（子なし → 出力: 11）
節番号1（出力: 1）
節番号3を訪問
節番号6を訪問
節番号12（子なし → 出力: 12）
節番号6（出力: 6）
節番号13（子なし → 出力: 13）
節番号3（出力: 3）
節番号7を訪問
節番号14（子なし → 出力: 14）
節番号7（出力: 7）
・Java でコーディング
import java.util.List;
public class BinaryTreeTraversal {
// 大域変数として二次元配列を表現
static List<List<Integer>> tree = List.of(
List.of(2, 3), // Node 1
List.of(4, 5), // Node 2
List.of(6, 7), // Node 3
List.of(8, 9), // Node 4
List.of(10, 11), // Node 5
List.of(12, 13), // Node 6
List.of(14), // Node 7
List.of(), // Node 8
List.of(), // Node 9
List.of(), // Node 10
List.of(), // Node 11
List.of(), // Node 12
List.of(), // Node 13
List.of() // Node 14
);
// 再帰的な中間順序トラバース
public static void order(int n) {
switch (tree.get(n - 1).size()) {
case 2 -> {
order(tree.get(n - 1).get(0)); // 左の子
System.out.print(n + " "); // 自分自身
order(tree.get(n - 1).get(1)); // 右の子
}
case 1 -> {
order(tree.get(n - 1).get(0)); // 唯一の子
System.out.print(n + " "); // 自分自身
}
default -> System.out.print(n + " "); // 子がない場合
}
}
public static void main(String[] args) {
order(1); // 根からスタート
}
}・Python でコーディング
# 二次元配列の表現
tree = [
[2, 3], # Node 1
[4, 5], # Node 2
[6, 7], # Node 3
[8, 9], # Node 4
[10, 11], # Node 5
[12, 13], # Node 6
[14], # Node 7
[], # Node 8
[], # Node 9
[], # Node 10
[], # Node 11
[], # Node 12
[], # Node 13
[] # Node 14
]
# 再帰的な中間順序トラバース
def order(n):
if len(tree[n - 1]) == 2:
order(tree[n - 1][0]) # 左の子
print(n, end=" ") # 自分自身
order(tree[n - 1][1]) # 右の子
elif len(tree[n - 1]) == 1:
order(tree[n - 1][0]) # 唯一の子
print(n, end=" ") # 自分自身
else:
print(n, end=" ") # 子がない場合
# 実行
order(1) # 根からスタート・トラバースとは
トラバース (Traversal) は、データ構造内の全てのノードや要素を規則的に訪問し、処理を行うことを指す。主に木構造やグラフ構造で使われる用語で、訪問順序に応じてさまざまな方法がある。
1. 木構造でのトラバース
木構造（特に二分木）では、ノードを訪問する順序に基づいて以下のトラバース方法がある。
a. 深さ優先探索 (Depth-First Search, DFS)
中間順序 (In-order traversal):
順序: 左部分木 → 現在のノード → 右部分木
例: 二分探索木でデータを昇順に出力する際に使う。
前順序 (Pre-order traversal):
順序: 現在のノード → 左部分木 → 右部分木
用途: 木をコピーする場合や式木の評価に使用。
後順序 (Post-order traversal):
順序: 左部分木 → 右部分木 → 現在のノード
用途: 木を削除する場合や式木の評価に使用。
b. 幅優先探索 (Breadth-First Search, BFS)
レベル単位でノードを訪問する方法。
通常、キュー（FIFO）を使用して実装される。
用途: 木の最短経路を求める場合など。
2. トラバースの用途
データ検索: データを順番に探すために木構造を効率よく巡回する。
ソート: 二分探索木を中間順序でトラバースすることで昇順にデータを取得できる。
式の評価: 木構造で表現された数式を評価する際に後順序トラバースを使用する。
グラフ探索: 木やグラフの各ノードに一度ずつ訪問するのに利用。
3. 中間順序 (In-order Traversal) の例
以下は、二分木における中間順序トラバースの例である。
木構造
1
/ \
2 3
/ \ / \
4 5 6 7中間順序 (In-order) の処理手順
左部分木を訪問する。
現在のノードを処理する。
右部分木を訪問する。
出力順: 4 → 2 → 5 → 1 → 6 → 3 → 7
擬似コード
中間順序トラバースを再帰で記述した場合:
function inOrder(node):
if node is not null:
inOrder(node.left) # 左部分木
print(node.value) # 現在のノード
inOrder(node.right) # 右部分木以上。