木構造の問題の解き方

飛岡拓希公開 2026年10月26日

木構造の問題は、まず木を絵に描きます。配列やノードで書かれた木を、そのまま頭の中で追うのは無理があります。描いたら、たどった順に番号を書き込みながら追います。

配列で表した木を、絵に戻す

科目B では、二分木を配列で表すことがよくあります。根を要素番号 1 に置き、要素番号 i のノードの左の子を 2i、右の子を 2i + 1 に置く形です。

要素番号:  1   2   3   4   5   6   7
値      :  8   3  10   1   6   9  14

要素番号 1 の 8 の子は、2 と 3 の 3 と 10。要素番号 2 の 3 の子は、4 と 5 の 1 と 6。こうして1段ずつ描くと、次の木になります。

        8
      /   \
     3     10
    / \   /  \
   1   6 9    14

配列を読んだら、まず描く。描いた木の各ノードの横に要素番号を小さく書いておくと、プログラムが tree[2 × i] のような式で動いたときに、絵の上で追えます。

二分木を全部たどる順番には、自分（根）をいつ処理するかで3つの形があります。どれも「左の部分木を全部たどってから、右の部分木をたどる」のは同じです。

プログラムでは、これは再帰で書かれます。中間順なら次の形です。「自分を出力する」行が、2つの呼び出しのどこにあるかで、3つのどれかが決まります。

○inorder(整数型: i)
  if (i > nodeの要素数)
    return
  endif
  inorder(2 × i)        // 左の部分木
  node[i] を出力する
  inorder(2 × i + 1)    // 右の部分木

追い方は、再帰の「自分を2回呼ぶ形」と同じです。1つ目の呼び出し（左）を最後まで追ってから、2つ目（右）に進みます。手順は再帰のトレースのやり方にまとめています。

上の木は、どのノードでも左の子孫はすべて自分より小さく、右の子孫はすべて自分より大きい形になっています。これを二分探索木と言います。

二分探索木には、問題を解くときに使える性質が2つあります。

2つ目の性質は、「どの部分木を見なくてよいか」を問う問題でそのまま使います。比べた結果ごとに、描いた木の枝に×を付けていくと、見るべきノードが残ります。

木構造の問題:

グラフ（点と線のつながり）は、隣接行列という2次元配列で表されることが多いです。adj[i, j] が 1 なら、点 i から点 j へ線がある、という意味です。

        点1 点2 点3 点4
点1  :   0   1   1   0
点2  :   1   0   0   1
点3  :   1   0   0   1
点4  :   0   1   1   0

点1 の行を見ると、点2 と点3 に 1 があるので、点1 は点2・点3 とつながっています。行を1本選んで、1 のある列を拾うのが、隣の点を求める操作です。この表は左上から右下への斜めの線で折り返すと重なるので、向きの無いグラフだと分かります。

グラフをたどる問題でも、まず点と線を絵に描き、訪れた点に順番を書き込みます。キューを使うたどり方（幅優先）なら、キューの中身を1操作ごとに書く方法はリスト・スタック・キューの問題の解き方と同じです。

このサイト（極とれ）の問題は、解いたあとにトレースの手順と、選択肢ごとに「なぜ違うか」が開きます。登録なしで解けます。

記法は IPA が公開しているサンプル問題・公開問題の記述形式に基づいています。出題形式は改訂されることがあるため、受験の際は IPA の公表内容をご確認ください。

書いているのは飛岡拓希です。基本情報技術者試験の科目B だけを扱う学習サービス「極とれ」を 1人で作って運営しています。試験には高校3年生のときに合格しました（そのときの記録）。

数字を載せるときは、出典の資料を自分で開いて数えた値だけを使い、いつ時点のものかを本文に書いています。誤りに気づいたら goku.tore9@gmail.com までお知らせください。読んだ感想はフォームからも送れます。