木構造の基本と巡回順序・グラフの表現
木の用語（根・葉・節点・深さ）を使って、親配列の葉の数、完全2分木の個数計算、行きがけ順・通りがけ順・帰りがけ順の出力を自分で求められるようになる。隣接行列からグラフを読み取り、木かどうかも判定できるようになる。
木とグラフは、ファイルのフォルダ階層、組織図、路線図、SNS のつながりなどの土台になるデータ構造です。科目Aでは「なぞる手順」を正確に追えるかが問われ、ルールさえ覚えれば確実に取れる問題です。
このレッスンで稽古する（用語チェック・過去問）結論：木は「根から下へ枝分かれする階層」
木構造は、一番上の根から下へ枝分かれしていくデータ構造です。データは上位の節点から下位の節点へたどって取り出します。会社の組織図（社長→部長→課長）やフォルダ階層をイメージすると分かりやすいです。
前のレッスンの連結リストは「次へ」が1本だけでした。木は「子」が複数あってもよい、と考えると整理できます。
| 構造 | 取り出し方 | 一言でいうと |
|---|---|---|
| 木 | 根から上位→下位へたどる | 組織図 |
| キュー | 入れた順に取り出す（FIFO） | レジの行列 |
| スタック | 入れた順の逆に取り出す（LIFO） | 積んだ皿 |
| 線形リスト | データ部＋ポインタ1つのセルを順にたどる | 数珠つなぎ |
試験では、この4つの説明を並べて「木構造の特徴はどれか」と聞いてきます。
木の用語を押さえる
- 節点（ノード）：データの入った点。根も葉も節点に含まれます
- 枝（エッジ）：節点どうしをつなぐ線
- 根：一番上の節点。親を持たない
- 葉：子を持たない、末端の節点
- 深さ：根から葉までの枝の本数。根だけなら深さ0
押さえておく関係：枝の数 ＝ 節点の数 − 1。根以外の節点には、親へ向かう枝が必ず1本ずつあるからです。
親配列で表した木から葉を数える
節点 i の親の番号を A[i] に入れる表し方です（根は 0）。一度も「親」として登場しない番号が葉になります。
手順は2つだけです。
- A[i] の値（0 は除く）を集める＝子を持つ節点の一覧
- 全節点からその一覧を除くと、残りが葉
よくある間違いは、親として出てくる番号の個数（＝子を持つ節点の数）をそのまま答えることと、根を葉として数えることです。
完全2分木の個数計算（公式は3つ）
「葉以外は全部ちょうど2つの子を持ち、葉の深さがすべて同じ」木を完全2分木と呼びます。下の段へ行くたびに節点が2倍になるトーナメント表と同じ形です。
深さを d とすると：
| 求めるもの | 式 | d=2 の場合 |
|---|---|---|
| 葉の数 | 2^d | 4 |
| 全節点数 | 2^(d+1) − 1 | 7 |
| 葉以外の節点数 | 2^d − 1 ＝ 葉の数 − 1 | 3 |
| 枝の数 | 節点数 − 1 | 6 |
迷ったら d=2（節点7個）の図を自分で描いて、選択肢に代入するのが一番確実です。トーナメントで考えると、参加者 n 人（葉）なら試合数（葉以外の節点）は n−1 になります。
2分木の巡回順序（3種類）
木のすべての節点を決まった順に1回ずつ訪れることを巡回といいます。どの巡回も「左の部分木を先に、右の部分木を後に」たどる点は共通で、違うのは自分（親）をいつ出力するかだけです。
| 名前 | 別名 | 出力の順 | 式の木に使うと |
|---|---|---|---|
| 行きがけ順 | 先行順・前順 | 自分→左→右 | ポーランド記法（前置） |
| 通りがけ順 | 中間順・間順 | 左→自分→右 | 普通の式（中置） |
| 帰りがけ順 | 後行順・後順 | 左→右→自分 | 逆ポーランド記法（後置） |
覚え方：木の外側を左から一周なぞるとき、節点の左側を通る瞬間に出す＝行きがけ、真下を通る瞬間＝通りがけ、右側を通る瞬間＝帰りがけ。
過去問の式の木（+ の左が a、右が *）は次の形です。
flowchart TD
P["+"] --> A["a"]
P --> M["*"]
M --> S["−"]
M --> D["d"]
S --> B["b"]
S --> C["c"]
- 行きがけ順：+ a * − b c d
- 通りがけ順：a + b − c * d
- 帰りがけ順：a b c − d * +
問題文が「左の子を呼ぶ→右の子を呼ぶ→自分を出力」のようにプログラムで書かれていても、出力の行がどこにあるかを見れば何順か分かります。
テキスト表現（左,節,右）と行きがけ順の番号付け
（左部分木, 節番号, 右部分木）と書き、空なら x という表現は、通りがけ順のかっこ付き版です。下の節点から順に組み立てると間違えません。選択肢では、空の x を書き忘れたものや左右を逆にしたものでひっかけてきます。
「行きがけ順で何番目に探索されるか」という問題は、根を0番として、訪れた瞬間に番号を振るだけです。左の子から深く潜り、行き止まりで戻って次の子へ進みます（深さ優先）。根を0から数えるのか1から数えるのかは、必ず問題文で確認します。
グラフと隣接行列（本試験に最もよく出る）
グラフは、節点を枝で自由につないだものです。木はグラフの特別な形で、「全部つながっていて、輪（閉路）がない」ものを指します。そのため節点が n 個なら、枝はちょうど n−1 本になります。
隣接行列は、i 行 j 列に「i と j の間に枝があれば1、なければ0」を書いた表です。向きのない無向グラフでは表が対角線を境に左右対称になり、1の個数÷2＝枝の本数になります。
解き方：
- 行列の右上半分（i<j）にある1を全部拾い、「a-b」のような組の一覧にする
- 選択肢のグラフと1本ずつ照らし合わせる。正解以外の選択肢は、1本足りないか1本多いだけのことがほとんど
- 「木になるもの」を選ぶ問題は、まず枝の数＝節点数−1で絞り込み、残った候補で輪がなくすべてつながっているかを確かめる
親配列から葉の数を数える
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| A[i] | 0 | 1 | 1 | 3 | 3 | 5 | 5 | 5 |
ア 1
イ 3
ウ 5
エ 7
解き方と答えを見る
- 表から A[i] を並べる：A = 0, 1, 1, 3, 3, 5, 5, 5（i=1〜8）
- 0（根の印）を除いて、親として出てくる番号を集める：{1, 3, 5}＝子を持つ節点
- 全節点 {1,2,3,4,5,6,7,8} から {1,3,5} を除く → {2, 4, 6, 7, 8}
- 葉は5個（確認：8節点−子を持つ3節点＝5）
答え：ウ：5
完全2分木の性質を選ぶ（d=2 を代入して確かめる）
ア 枝の個数が n ならば，節点の個数も n である。
イ 木の深さが n ならば，葉の個数は 2^(n-1) である。
ウ 節点の個数が n ならば，木の深さは log_2 n である。
エ 葉の個数が n ならば，葉以外の節点の個数は n－1 である。
出典：基本情報技術者試験 科目A免除 修了試験 20250608 実施分 問5
解き方と答えを見る
- 深さ d=2 の完全2分木を描く：根1、深さ1に2個、深さ2（葉）に4個、合計7個
- ア：枝の数は 7−1＝6、節点は7 → 同じにならないので×
- イ：深さ2なら葉は 2^(2−1)＝2 となるが、実際は4 → ×（正しくは 2^d）
- ウ：節点数7なら log₂7≒2.8 となり、深さ2と一致しない → ×
- エ：葉4個に対し、葉以外の節点は 1+2＝3＝4−1 → ○
答え：エ：葉の個数が n ならば、葉以外の節点の個数は n−1
節点数と深さの式
ア n = 2^k + 3
イ n = 2^(k+1) − 1
ウ n = (k−1)(k+1) + 4
エ n = k(k+1) + 1
出典：基本情報技術者試験 科目A免除 修了試験 200912 実施分 問5
解き方と答えを見る
- 深さ0〜k の各段の節点数は 1, 2, 4, …, 2^k
- 合計は 1+2+…+2^k ＝ 2^(k+1) − 1
- k=2 を代入：2^3 − 1 ＝ 7（例の図の7個と一致）
- ア 2^2+3＝7 も7になるので k=3 でも試す：正しくは 2^4−1＝15、アは 2^3+3＝11 → 不一致
答え：イ：n = 2^(k+1) − 1
帰りがけ順で式の木を出力する
ア +a*−bcd
イ a+b−c*d
ウ abc−d*+
エ b−c*d+a
解き方と答えを見る
- Proc は「左の子→右の子→自分を出力」の順＝帰りがけ順
- 根 + から：まず左の子 a。a は葉なので出力 → a
- 次に + の右の子 *。* の左の子 − に進む
- − の左 b を出力、右 c を出力、最後に − 自身を出力 → b c −
- * の右 d を出力、最後に * 自身を出力 → d *
- 最後に根 + を出力
- つなげると a b c − d * +
答え：ウ：abc−d*+
行きがけ順で●の番号を求める
ア 9
イ 10
ウ 11
エ 12
出典：基本情報技術者試験 科目A免除 修了試験 20260614 実施分 問6
解き方と答えを見る
- 根＝0。最初の子 X1 へ進む → X1＝1
- X1 の左の葉＝2、X1 の右のノード＝3、その子の葉2つ＝4, 5
- X2＝6。X2 の左のノード＝7、その子の葉＝8
- X2 の中央の葉＝9
- X2 の右のノード＝10、その左の子（●）＝11
答え：ウ：11
テキスト表現（左,節,右）を下から組み立てる
ア （（1，2），3，（4，5，6））
イ （（1，2，3），x，（4，5，6））
ウ （（1，2，x），3，（4，5，6））
エ （（1，2，x），3，（6，5，4））
出典：基本情報技術者試験 科目A免除 修了試験 20230122 実施分 問7
解き方と答えを見る
- 節2：左の子は1、右は空 → (1, 2, x)
- 節5：左の子は4、右の子は6 → (4, 5, 6)
- 根3：左部分木は節2の表現、右部分木は節5の表現 → ((1,2,x), 3, (4,5,6))
- ア は x が抜けている、エ は右部分木の左右が逆なので×
答え：ウ：((1,2,x),3,(4,5,6))
隣接行列からグラフを選ぶ
| a | b | c | d | e | f | |
|---|---|---|---|---|---|---|
| a | 0 | 1 | 0 | 0 | 0 | 0 |
| b | 1 | 0 | 1 | 1 | 0 | 0 |
| c | 0 | 1 | 0 | 1 | 1 | 0 |
| d | 0 | 1 | 1 | 0 | 0 | 0 |
| e | 0 | 0 | 1 | 0 | 0 | 1 |
| f | 0 | 0 | 0 | 0 | 1 | 0 |
ア [図] ノード a-f の無向グラフ。辺: a-b, c-d, d-e, e-f, c-e（上の弧）, b-d（下の弧）。b-c 間に辺なし
イ [図] ノード a-f の無向グラフ。辺: a-b, b-c, d-e, e-f, c-e（上の弧）, b-d（下の弧）。c-d 間に辺なし
ウ [図] ノード a-f の無向グラフ。辺: a-b, b-c, c-d, e-f, c-e（上の弧）, b-d（下の弧）。d-e 間に辺なし
エ [図] ノード a-f の無向グラフ。辺: a-b, b-c, c-d, d-e, e-f, c-e（上の弧）, b-d（下の弧）
解き方と答えを見る
- 右上半分の1を拾う：a行→b、b行→c, d、c行→d, e、d行→なし（b, c は拾い済み）、e行→f
- 枝の一覧：a-b, b-c, b-d, c-d, c-e, e-f（6本、1の個数12÷2＝6と一致）
- d-e は 0 なので枝なし
- 選択肢のうち、隣り合う点の間で d-e だけが抜けているのはウ
答え：ウ
隣接行列から木を見つける
ア [図] 5×5 隣接行列
0 1 0 0 1
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
イ [図] 5×5 隣接行列
0 1 0 0 1
1 0 1 1 0
0 1 0 0 0
0 1 0 0 0
1 0 0 0 0
ウ [図] 5×5 隣接行列
0 1 0 1 0
1 0 1 0 0
0 1 0 1 1
1 0 1 0 0
0 0 1 0 0
エ [図] 5×5 隣接行列
0 1 1 0 0
1 0 1 0 0
1 1 0 1 1
0 0 1 0 1
0 0 1 1 0
出典：基本情報技術者試験 科目A免除 修了試験 20221211 実施分 問7
解き方と答えを見る
- 木の条件：節点5個なら枝は 5−1＝4 本
- 各選択肢の1の個数÷2：ア 10÷2＝5本、イ 8÷2＝4本、ウ 10÷2＝5本、エ 12÷2＝6本
- 4本はイだけ。枝は 1-2, 1-5, 2-3, 2-4
- 全節点がつながっていて輪もない → 木
答え：イ
要点（試験直前に読む）
- 木は根から上位→下位へたどる階層構造。入れた順＝キュー、逆順＝スタック、ポインタ1つ＝線形リスト。
- 親配列（A[i]＝親の番号）では、一度も親として登場しない番号が葉。根（0）は葉に数えない。
- 完全2分木（深さ d）：葉 2^d、全節点 2^(d+1)−1、葉以外＝葉−1、枝＝節点−1。迷ったら d=2（7個）を描いて代入。
- 巡回順序は自分を出すタイミングで決まる：行きがけ＝最初、通りがけ＝真ん中、帰りがけ＝最後。帰りがけ順は逆ポーランド記法。
- 隣接行列は右上半分の1を拾って枝の一覧にし、選択肢と1本ずつ照らし合わせる。1の個数÷2＝枝の本数。
- 木の条件：すべてつながっていて閉路がない＝節点 n 個なら枝はちょうど n−1 本。
ひっかけ
- 巡回順序の問題では、選択肢に行きがけ順（+a*−bcd）と通りがけ順（a+b−c*d）の結果が必ず並ぶ。プログラムのどこで「出力」しているかを見て、何順かを先に決める。
- 親配列の葉の数では、「親として登場する番号の数（3）」や「根を含めた数」を答えさせようとする。全節点から子を持つ節点を除いた残りを数える。
- 完全2分木では 2^(n−1) と 2^n の取り違えを狙ってくる。深さは枝の本数（根＝0）なので、d=2 の具体例で代入して確かめる。
- 隣接行列の問題は、正解以外のグラフが「1本だけ欠けている／多い」ことが多い。0の位置（例：d-e）も確認して、ないはずの枝が描かれていないかを見る。
- テキスト表現（左,節,右）では、空部分木の x の書き忘れや、左右を逆にしたものが並ぶ。下の節点から組み立てると防げる。
用語（16）
根から枝分かれする階層を持ち、上位の節点から下位の節点へたどってデータを取り出すデータ構造。
⚠ キュー（入れた順）、スタック（逆順）、線形リスト（ポインタ1つでたどる）の説明と並べて出題される。「階層」「上位から下位」があれば木。
木やグラフでデータを持つ点のことで、根も葉も含む。
⚠ 枝（エッジ）と混同しない。枝の数＝節点の数−1。
木の一番上にあり、親を持たない唯一の節点。
⚠ 親配列表現では A[k]=0 の節点。葉として数えない。
子を持たない末端の節点。
⚠ 親配列で「親として登場する番号」は子を持つ節点なので葉ではない。
根からある節点までにたどる枝の本数で、根の深さは0。
⚠ 段の数（深さ＋1）と取り違えると、2^d と 2^(d−1) のずれが起きる。
各節点が持つ子が最大2つ（左の子・右の子）の木。
葉以外の節点がすべて2つの子を持ち、葉の深さがすべて等しい2分木で、深さ d なら節点は 2^(d+1)−1 個、葉は 2^d 個になる。
⚠ 葉の数 2^d と全節点数 2^(d+1)−1 を取り違えやすい。d=2 で描いて確かめる。
自分→左部分木→右部分木の順に訪れる巡回で、式の木に使うと前置記法になる。
⚠ 帰りがけ順とは自分を出すタイミングが逆。最初に根が出てくれば行きがけ順。
左部分木→自分→右部分木の順に訪れる巡回で、式の木に使うと普段の書き方（中置）になる。
⚠ （左,節,右）のテキスト表現はこの順。根が真ん中付近に出てくる。
左部分木→右部分木→自分の順に訪れる巡回で、式の木に使うと逆ポーランド記法になる。
⚠ 行きがけ順と逆で、根が最後に出てくる。
演算子を、計算する2つの値の後ろに書く式の表し方（例：a+b を ab+）。
⚠ 前置記法（+ab）と区別する。式の木を帰りがけ順でたどると得られる。
子があれば先にできるだけ深く進み、行き止まりで戻って次の枝へ進む探索方法。
⚠ 幅優先探索は、同じ深さの節点を全部見てから次の深さへ進む。
節点（頂点）と、それらを結ぶ枝（辺）で表したつながりの構造。
⚠ 木はグラフのうち、すべてつながっていて閉路を持たないもの。
枝に向きがなく、a-b と b-a を同じ枝として扱うグラフ。
⚠ 有向グラフは枝に矢印の向きがあり、隣接行列は対称にならない。
i 行 j 列に、節点 i と j の間に枝があれば1、なければ0を書いた正方形の表。
⚠ 無向グラフでは対角線を境に対称になる。枝の本数は1の個数÷2。
ある節点から出発し、同じ枝を通らずに元の節点へ戻れる経路。
⚠ 閉路があれば木ではない。節点 n 個で枝が n 本以上あれば閉路がある（つながっている場合）。
このレッスンの過去問
- 木構造の特徴(階層を上位から下位へたどる)基本情報技術者試験 科目A免除 修了試験 20140126 実施分 問6
- 親配列表現された木の葉の数平成22年度 秋期 基本情報技術者試験 午前 問6
- 完全2分木の節点数と葉の数の関係基本情報技術者試験 科目A免除 修了試験 20250608 実施分 問5
- 完全2分木の節点数と深さの関係基本情報技術者試験 科目A免除 修了試験 200912 実施分 問5
- 2分木の巡回順序(帰りがけ順)平成26年度 春期 基本情報技術者試験 午前 問6
- 木の行きがけ順(先行順)探索の番号計算基本情報技術者試験 科目A免除 修了試験 20260614 実施分 問6
- 2分木のテキスト表現(左部分木,節,右部分木)の読解基本情報技術者試験 科目A免除 修了試験 20230122 実施分 問7
- 隣接行列とグラフの対応読解令和元年度 秋期 基本情報技術者試験 午前 問3