階層構造でデータを管理する構造。木を逆さにした形。
節を「根・左・右」のどの順で訪れるかで3種類。
| 走査 | 訪れる順 |
|---|---|
| 前順（先行順） | 根 → 左 → 右 |
| 間順（中間順） | 左 → 根 → 右 |
| 後順（後行順） | 左 → 右 → 根 |
1つの節が複数の子をもつ木。葉までの深さがすべて等しい多分木をB木という。 データ量が多くても効率がよく、データベースの索引などに使われる。
Q1 ★走査の順序（前順）
次の2分木を前順（根→左→右）で走査したときの並びはどれか。
正解：ア（A B D E C F）
「根をいつ訪れるか」だけを意識する（前＝先、間＝真ん中、後＝最後）。
A B D E C F（Aを先に→左部分木→右部分木）D B E A C F（左を全部→根A→右）＝選択肢イD E B F C A（子を全部訪れてから根Aは最後）＝選択肢ウ▼速解法：前順の先頭＝必ず根、後順の末尾＝必ず根。この2つを最初にチェックすると選択肢を一気に絞れる。
▼ 解説つきの類題を探す：過去問道場・分野別「データ構造」
Q2 ★全2分木（正2分木）の全節点数
葉が n 個ある全2分木（正2分木）＝葉以外の節点がすべて子を2個もつ2分木の、全節点数はいくつか。
正解：ウ（2n − 1）
葉以外が子を2個ずつもつ木（全2分木）では、葉の数 = 内部節点の数 + 1。
よって葉が n 個なら内部節点は n−1 個 → 全節点数 = n + (n−1) = 2n − 1。
▼速解法：「葉 n 個 → 全体 2n−1 個」とセットで暗記。
▼ 解説つきの類題を探す：過去問道場・分野別「データ構造」
Q3（H22秋 問6）★木を配列で表現する
節点 1〜n をもつ木を、大きさ n の配列 A で表す。A[i] には「節点 i の親」を入れ、根のときは 0 とする。次の配列が表す木の葉の数はいくつか。
| i (節点) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| A[i] (親) | 0 | 1 | 1 | 3 | 3 | 5 | 5 | 5 |
正解：ウ（5）
配列から木を描く。
子をもたない節点（＝葉。図の緑）は 2, 4, 6, 7, 8 の 5 個 → ウ。
▼速解法：葉＝「どの A[i] にも親として登場しない番号」。表の A[i] 欄に出てこない節点を数えるだけ（1,3,5 は親として登場→葉でない。残り 2,4,6,7,8 が葉）。
Q4 ★2分探索木の条件
2分探索木として正しく成り立っているといえる条件はどれか。
正解：イ
2分探索木の判定は、各節点で「左部分木の全値 < 節点の値 < 右部分木の全値」が成り立つかを確認する。1か所でも崩れたら2分探索木ではない。
過去問（図つき）で確認： H31春 問5
Q5 ★2分探索木の探索経路
次の2分探索木から値 40 を探索するとき、値を比較する節点を根から順に並べたものはどれか。
正解：イ（50 → 30 → 40）
2分探索木は「左の子 < 節点 < 右の子」。探索は必ず根から始め、探す値と比べて左右どちらへ進むかを決める。
▼速解法：探索は根から1本道。大小で左右に振り分けるだけなので、比較回数は木の深さぶん（この木なら最大3回）。整列済み配列の2分探索と同じ考え方。
▼ 解説つきの類題を探す：過去問道場・分野別「データ構造」