基本情報技術者試験のサンプル問題を解こう！（12）（科目B）「２分木の節番号を出力するプログラム」

IT系

2025.07.06

基本情報技術者試験のサンプル問題（科目B）を解いてみよう。

今回のテーマは、「２分木の節番号を出力するプログラム」である。

解答群
ア　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

正解：ウ

このプログラムは、二分木を「中順走査」（in-order traversal）する擬似コードで、根から深く左→親→右、という順に節点をたどって出力する。

これにより、左の枝を最深部まで降りて葉を出力し、祖先に戻って出力、右の枝へ、と進む（中順）。

問題の構成

節点情報は tree という連想配列に格納されており、各節点 n の子が配列として格納されている。（最大2つ、左・右の順）
関数 order(n) は 中順走査（左 → 親 → 右） を再帰的に行う。
order(1) から開始し、節点番号を出力していく。

この問題では、2分木（左右の子を持つ木構造）を表す配列 tree を使って、再帰的に節（ノード）を走査する関数 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

この関数は、左の子 → 自分自身 → 右の子の順で出力する、つまり中間順（中順）走査（in-order traversal）を行っている。

order(1)を呼び出した場合の流れを確認しよう

order(1) → 左の子 2 を探索
order(2) → 左の子 4 を探索
order(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

出力結果を確認しよう

順番に並べると、

8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7

これは選択肢「ウ」に該当する。

C言語のプログラムでこの中間順走査を出力しよう

以下のC言語のコードでは、木構造を配列で表現し、中間順で節点を出力するようにしている。

#include <stdio.h>

// 子ノード情報（左、右）を格納した配列
int tree[14][2] = {
    {2, 3},   // 1
    {4, 5},   // 2
    {6, 7},   // 3
    {8, 9},   // 4
    {10, 11}, // 5
    {12, 13}, // 6
    {14, 0},  // 7（右子が存在しない）
    {0, 0},   // 8（葉ノード）
    {0, 0},   // 9
    {0, 0},   // 10
    {0, 0},   // 11
    {0, 0},   // 12
    {0, 0},   // 13
    {0, 0}    // 14
};

// 再帰的に中間順で木を走査する関数
void order(int n) {
    if (n == 0) return;

    int left = tree[n - 1][0];
    int right = tree[n - 1][1];

    if (left != 0)
        order(left);

    printf("%d ", n);

    if (right != 0)
        order(right);
}

int main() {
    order(1); // 根ノードからスタート
    return 0;
}

実行結果

このコードを実行すると、以下の順で節点が出力される。