基本情報 科目B 木構造（二分木）のトレース練習
基本情報技術者試験の科目Bで、データ構造の総仕上げになるのが 木構造（二分木） です。連結リストが「次の要素への参照を 1 本」持つのに対し、二分木は各ノードが 左の子・右の子の 2 本の参照 を持って枝分かれします。参照が増えるぶん、全ノードを「どの順でたどるか」が論点になります。本記事は、二分木を 1 ノードずつ手でたどる トレースで、深さ優先・幅優先の 4 つの巡回順を攻略する練習帳です。連結リストのトレース練習・再帰のトレース練習・スタックとキューのトレース練習 の集大成にあたります。
本記事は 過去問AI が学習用に作成したオリジナルの例題です。掲載している擬似言語は IPA の過去問・公式サンプルの転載ではなく、説明用に書き起こしたものです。擬似言語の正式な記述形式は必ず IPA 公式ページ で確認してください。クラス・メンバ変数・参照・未定義の記法そのものは 基本情報 科目Bの擬似言語 記法早見表 にまとめています。
木構造は「参照が枝分かれする」
連結リストは要素が一列に数珠つなぎでしたが、木構造はノードが 2 方向に枝分かれ します。各ノードは次の 3 つを持ちます。
- 値：そのノードが格納しているデータ
- 左の子への参照（left）：左側にぶら下がるノードを指す。無ければ 未定義
- 右の子への参照（right）：右側にぶら下がるノードを指す。無ければ 未定義
科目Bでは、こうしたノードを クラス で表します。本記事ではクラス名を Node、値を val、左右の子への参照を left・right とします（問題ごとにクラス名やメンバ名は変わるので、設問に添えられたクラスの説明を必ず先に読んでください）。
- メンバは 変数名.メンバ名 のドットでたどります。ノード t の値は t.val、左の子は t.left、右の子は t.right
- Node 型の変数には、ノードの実体ではなく インスタンスの参照 が入ります
- 木の出発点（根）は 大域: Node: 根 で保持します。左右どちらも子が無い末端（葉）の left・right は 未定義 です
記法そのものが不安なら、先に 記法早見表のクラス・メンバの節 でドット（.）と未定義の読み方を確認してから戻ってくるとスムーズです。
練習に使う木
本記事ではこの小さな二分木（ノード 5 個）を例にします。根は値1、その左右に値2・値3、さらに値2の左右に値4・値5がぶら下がります。
1
/ \
2 3
/ \
4 5
参照で書くと、根(1).left → 2、根(1).right → 3、2.left → 4、2.right → 5、3 と 4 と 5 の left・right はすべて未定義（葉）です。
例題1：深さ優先（行きがけ順）
深さ優先は「行けるところまで下に潜ってから戻る」たどり方で、再帰 で書くのが定番です。まず 行きがけ順（自分を出力してから左→右に潜る）を見ます。
大域: Node: 根
○行きがけ順(Node: t)
if (t が 未定義)
return
endif
t.val を出力する
行きがけ順(t.left)
行きがけ順(t.right)
「未定義なら何もせず戻る」が葉の先で再帰を止めるブレーキです。これが無いと未定義の .left を読もうとして破綻します。
行きがけ順をトレースする
根（値1）から 行きがけ順(根) を呼びます。未定義のノードへの呼び出しは即 return するので、値を持つノードに入った瞬間の出力だけを追います。
| 手順 | 呼び出し | 動作 | これまでの出力 |
|---|---|---|---|
| 1 | 行きがけ順(1) | 1を出力し、左(2)へ潜る | 1 |
| 2 | 行きがけ順(2) | 2を出力し、左(4)へ潜る | 1, 2 |
| 3 | 行きがけ順(4) | 4を出力。左右とも未定義で戻る | 1, 2, 4 |
| 4 | 行きがけ順(5) | 2の右。5を出力。左右とも未定義で戻る | 1, 2, 4, 5 |
| 5 | 行きがけ順(3) | 1の右。3を出力。左右とも未定義で戻る | 1, 2, 4, 5, 3 |
出力は 1 → 2 → 4 → 5 → 3。「自分を出してから左、左が尽きたら右」を守れば迷いません。呼び出しが入れ子に積み重なる感覚は 再帰のトレース練習 のコールスタックと同じです。
例題2：出力の位置を変えるだけ（通りがけ・帰りがけ）
深さ優先には、出力する 1 行をどこに置くか だけが違う 3 兄弟があります。木の形をたどる順序は同じで、val を出力するタイミングだけがずれます。
- 行きがけ順：左右に潜る前に出力（自分 → 左 → 右）
- 通りがけ順：左に潜ったあと、右に潜る前に出力（左 → 自分 → 右）
- 帰りがけ順：左右に潜り終えてから出力（左 → 右 → 自分）
通りがけ順は出力の行を 2 つの再帰呼び出しの間に置きます。
○通りがけ順(Node: t)
if (t が 未定義)
return
endif
通りがけ順(t.left)
t.val を出力する
通りがけ順(t.right)
同じ木をこの 3 つでたどると、出力順はこうなります（手で追って検算した結果です）。
| 巡回 | 出力する位置 | この木での出力順 |
|---|---|---|
| 行きがけ順 | 自分 → 左 → 右 | 1 → 2 → 4 → 5 → 3 |
| 通りがけ順 | 左 → 自分 → 右 | 4 → 2 → 5 → 1 → 3 |
| 帰りがけ順 | 左 → 右 → 自分 | 4 → 5 → 2 → 3 → 1 |
コードはほとんど同じなのに出力順がまるで変わります。設問が「どの巡回順か」を必ず確認し、出力の行が再帰呼び出しの前・間・後ろのどこにあるか を見るのが見分け方です。
例題3：幅優先（レベル順）
幅優先は「上の段から順に、左から右へ」横向きにたどる方法で、キュー（先入れ先出し）を使います。深さ優先の再帰とは道具が違う点に注意してください。
○レベル順(Node: 根)
Queue: q
q に 根 を入れる
while (q が 空でない)
Node: t ← q から取り出す
t.val を出力する
if (t.left が 未定義でない)
q に t.left を入れる
endif
if (t.right が 未定義でない)
q に t.right を入れる
endif
endwhile
「取り出したノードの子を後ろに足す」を繰り返すと、近い段のノードから順に処理されます。
レベル順をトレースする
キューの中身を「先頭 → 末尾」で書きながら追います。
| 周回 | 取り出す（出力） | 後ろに入れる子 | キューの中身（先頭→末尾） |
|---|---|---|---|
| （初期） | — | 根(1) | 1 |
| 1 | 1 | 2, 3 | 2, 3 |
| 2 | 2 | 4, 5 | 3, 4, 5 |
| 3 | 3 | （子なし） | 4, 5 |
| 4 | 4 | （子なし） | 5 |
| 5 | 5 | （子なし） | （空）→ 終了 |
出力は 1 → 2 → 3 → 4 → 5。同じ段（1 → 2,3 → 4,5）がきれいに左から右へ並びます。キューの出し入れの作法そのものは スタックとキューのトレース練習 と同じです。
つまずきやすい3つのポイント
- 未定義をたどろうとする。葉の left・right は未定義です。再帰なら「未定義なら return」、幅優先なら「未定義でない子だけキューに入れる」で止めないと、未定義の .val や .left を読んで破綻します。
- 巡回順を取り違える。行きがけ・通りがけ・帰りがけはコードがそっくりで、違いは出力する 1 行の位置だけです。設問の指定を読み、出力が再帰呼び出しの前・間・後ろのどこかを確認します。
- 深さ優先と幅優先で道具を混同する。深さ優先は再帰（＝コールスタック）、幅優先はキューです。「下に潜る」のか「段ごとに横へ」なのかで使う道具が変わります。
トレースで詰まらないためのコツ
二分木は、ノードを 丸、left・right を 2 本の矢印 で紙に描くのが最強です。深さ優先なら「いま潜っている経路」を指でなぞり、戻ったら 1 つ上のノードへ指を戻す。幅優先ならキューの箱を別に描き、取り出した順に番号を振ると、4 つの巡回順がすべて目で追えます。連結リストで「参照を 1 本ずつ追う」感覚を固めてから木に来ると、枝分かれが 2 本に増えただけだと分かります。
次のステップ
木構造まで追えれば、科目Bで問われるデータ構造（スタックとキュー・連結リスト・木）の主要パターンはひととおり手で追えるようになります。アルゴリズム側の基礎がまだなら、合計・最大値・線形探索のトレース練習、二分探索のトレース練習、ソート（整列）のトレース練習、再帰のトレース練習 を先にどうぞ。読む速度を上げる訓練法は 基本情報科目B｜擬似言語アルゴリズム読解の3ステップ訓練法、つまずきの切り分けは 科目Bがわからない人へ、科目B 全体の進め方は 基本情報技術者 科目B完全対策 が地図になります。
手を動かす練習台としては、過去問AI の 基本情報 アルゴリズムとプログラミング分野の過去問 が使えます（こちらは科目A 相当の選択式で、科目B そのものの形式ではない点だけ意識してください）。各問題ページの AI コパイロットに「この二分木を丸と矢印で描いて、行きがけ・通りがけ・帰りがけ・レベル順を 1 ノードずつトレースして」と頼めば、本記事と同じ追い方を対話でその場で再現できます。
よくある質問
Q. 行きがけ順・通りがけ順・帰りがけ順の違いは何ですか？ 3 つとも木を深さ優先でたどる順序で、違うのは値を出力するタイミングだけです。行きがけ順は左右の子に潜る前（自分→左→右）、通りがけ順は左に潜ったあと右に潜る前（左→自分→右）、帰りがけ順は左右に潜り終えてから（左→右→自分）出力します。コードは出力の 1 行を再帰呼び出しのどこに置くかが違うだけなので、設問ではその位置を確認します。
Q. 深さ優先と幅優先はどう使い分けますか？ 深さ優先は「行けるところまで下に潜ってから戻る」たどり方で、再帰（コールスタック）で書くのが定番です。幅優先は「上の段から順に左から右へ」横向きにたどる方法で、キュー（先入れ先出し）を使います。同じ木でも出力順が変わり、深さ優先は枝を深く、幅優先は段ごとに処理が進みます。科目Bでは設問の指定どおりにどちらかを選びます。
Q. 木のトレースで葉（末端）はどう扱えばよいですか？ 葉は左の子・右の子がどちらも未定義のノードです。再帰では「ノードが未定義なら何もせず戻る」を最初に置き、葉の先の未定義まで潜ったら戻ります。幅優先では「未定義でない子だけキューに入れる」とすれば、葉の先の未定義をキューに入れずに済みます。未定義のノードに対して .val や .left を読もうとすると破綻するので、未定義かどうかを先に確かめる順序を守ってください。