木構造（tree structure）
1つの根から枝が分かれていくデータ構造。上下の関係を持たせたいときに使う。
もう少し詳しい説明
木構造は、1つの出発点から枝が分かれていくデータ構造です。会社の組織図やフォルダの入れ子と同じ形で、上下の関係を持たせたいときに使います。
名前を4つだけ
図を読むのに必要な言葉は4つです。
- 節（せつ）… 丸ひとつひとつ。データが入っている場所。ノードとも呼びます
- 枝（エッジ）… 丸と丸をつなぐ線。上下の関係を表す
- 根（ルート）… いちばん上の節。木全体の出発点で、必ず1つだけ
- 葉（リーフ）… 枝が下へ出ていない節。行き止まりのところ
上と下の節は親と子と呼びます。図のAはB・Cの親で、B・CはAの子です。
ある節とその下にぶら下がっている全部をまとめて部分木と呼びます。図のBとD・Eで1つの部分木です。木の一部を切り出しても、それがまた木になっているというのが、この構造の扱いやすさの正体です。
2分木
どの節も、子を2つまでしか持たない木を2分木と呼びます。試験に出る木は、ほとんどがこれです。
子が2つまでと決まっていると、左の子と右の子という呼び分けができます。この「左」「右」に意味を持たせると、探すのが速い構造になります。
- 完全2分木 … 葉以外のすべての節が子を2つ持ち、葉の深さがそろっている木
- 2分探索木 … 左の子は自分より小さい、右の子は自分より大きい、と決めて並べた木
2分探索木なら、探したい値と節を比べるたびに、片側を丸ごと捨てられます。探したい値が節より小さければ、右側は見る必要がないからです。
二分探索（並んでいるデータの真ん中と比べて、探す範囲を半分ずつ捨てていく方法）を木の形にしたもので、整った形なら計算量（件数が増えたときに、処理時間がどれくらいの勢いで伸びるか）は O(log n)（件数が2倍になっても、回数は1回しか増えない伸び方）です。
たどる順番が3つある
木の中身を全部見ていくことを巡回と呼びます。順番の決め方が3つあり、どれも試験に出ます。
3つはどれも、「自分」「左の子」「右の子」をどの順で書くかという形で表されます。たとえばこのあと出てくる先行順は、「自分 → 左 → 右」です。
この書き方の中の「自分を書く」が何をすることなのかを、先に説明します。ここがあいまいなままだと、3つの違いを追えません。
「自分を書く」とはどういうことか
巡回の答えは、節の名前を1列に並べたものです。「A B D E C F G」のような、あの並びを作るのが目的だと思ってください。
その並びを、左から1つずつ作っていきます。「自分を書く」は、いま見ている節の名前を、その並びの右端に1つ足すという意味です。「自分」はいま立っている節のことです。
分かりにくいのは、節のところを通るのと、その節を書くのが別の動作だからです。通っただけでは書きません。左の子へ降りるために通り過ぎるだけのこともあれば、下から戻ってきただけのこともあります。
先行順（自分 → 左 → 右）でAから始めると、こうなります。
- Aに立った。まず自分を書く → 並びは「A」
- 左の子Bへ降りた。ここでも自分が先なので書く → 「A B」
- 左の子Dへ降りた。書く → 「A B D」
- Dは葉なのでBまで戻る。Bはもう書いたので、ここでは何もしない
- Bの右の子Eへ降りた。書く → 「A B D E」
- Eも葉なのでBへ、さらにAまで戻る。Aもすでに書いたので何もしない
このあと右側のC・F・Gを同じように進めて、A B D E C F G となります。4と6のように、通ったけれど書かない瞬間がある。この「書かない回」をどこへ寄せるかが、3つの順番の違いです。
| 呼び方 | 順番 | 上の図では |
|---|---|---|
| 先行順（行きがけ） | 自分 → 左 → 右 | A B D E C F G |
| 中間順（通りがけ） | 左 → 自分 → 右 | D B E A F C G |
| 後行順（帰りがけ） | 左 → 右 → 自分 | D E B F G C A |
左が先で右が後、という点は3つとも同じです。変わるのは自分を書く位置だけなので、そこだけ覚えてください。
たどり方のコツ
紙に木を書いて、木全体を左回りにぐるりと囲むようになぞります。
根の左から出発し、左へ左へと降りていって、いちばん下の葉をぐるりと回り、右から戻ってくる。これが1周です。線が節のそばを通るとき、
- 左側を通ったときに書けば 先行順
- 下側を通ったときに書けば 中間順
- 右側を通ったときに書けば 後行順
どの節のそばも、左・下・右と必ず3回通ります。さきほどの「通ったけれど書かない瞬間」とは、この3回のうち書かなかった2回のことです。
たとえば中間順なら、Dの下を通ったときにDを書き、次にBの下を通ったときにBを書き、Eの下、Aの下…と進んで D B E A F C G。1周なぞるだけで、3つのうちどの順番でも作れます。試験では順番を取り違えやすいので、この1周を書いてしまうのが確実です。
深さ優先と幅優先
巡回とは別に、どちらの向きに広げていくかという分け方もあります。同じ木を2通りでたどって、番号を見比べてください。
深さ優先探索
行けるところまで下へ降りてから、戻って次へ進みます。
Aから左へ降りてB、さらに降りてD。Dは行き止まりなので1つだけ戻ってE。ここで左側は見終わったので、やっと右のCへ移ります。たどった順は A B D E C F G で、これは先行順の並びと同じです。先行順・中間順・後行順は、どれも深さ優先の仲間です。
使う入れ物はスタックです。戻る先は「最後に通った分かれ道」なので、後に入れたものから取り出す形がそのまま当てはまります。
幅優先探索
同じ深さの節を全部見てから、1段下へ降ります。
1段目のAを見たら、2段目のB・Cを両方見る。それから3段目のD・E・F・Gへ。たどった順は A B C D E F G で、段ごとに左から読む形になります。
使う入れ物はキューです。先に見つけた節から順に処理するので、先に入れたものから出す形が当てはまります。
番号の散らばり方で見分ける
2枚の図で、番号の付き方を比べてください。
- 深さ優先 … 番号が縦に伸びてから、横へ移る（1→2→3と左を掘り下げる）
- 幅優先 … 番号が段ごとに横へ流れる（1段目、2段目、3段目と埋まる）
深さ優先はスタック、幅優先はキュー。この対応はそのまま出題されるので、セットで覚えてください。
何に使われているのか
フォルダがいちばん身近です。1つのドライブを根として、フォルダの中にフォルダがあり、いちばん下がファイル（葉）。「このフォルダ以下をまとめて移動」ができるのは、部分木がそのまま木だからです。
ほかにも例があります。
- データベースの索引（B木。1つの節に複数の値を持たせた木で、ディスクの読み書きを減らせる）
- HTML（Webページの中身を書く言語）の構造 …
<html>の中に<body>、その中に<p>と入れ子になっている - BNF（プログラム言語（人がプログラムを書くための言葉）の文法を書き表す記法）の展開を表す構文木
入れ子になっているものは、たいてい木で表されています。
試験ではこう出る
科目A（旧・午前）のデータ構造分野で出ます。いちばん多いのは、木を与えて巡回の順番を答えさせる問題です。先行順・中間順・後行順のどれかを指定され、並びを選ばせます。
次に多いのが、2分探索木に値を入れたり探したりする問題。左が小さく右が大きい、という決まりだけで解けます。
深さ優先はスタック、幅優先はキューという対応も、単独で問われます。
解くときは、必ず木を書いてからなぞること。頭の中だけでたどると、戻る場所を見失います。応用情報では、節の追加・削除や、ヒープの作り直しまで広がります。
関連する用語
- 2分探索木
- 左は小さい、右は大きい、と決めて並べた2分木。探すのが速くなる
- 二分探索
- 半分ずつ絞る探し方。2分探索木は、この考え方を木の形にしたもの
- スタック
- 後に入れたものから先に取り出す構造。木を深さ優先でたどるときに使う
- キュー
- 先に入れたものから先に出す構造。木を幅優先でたどるときに使う
- 計算量
- 件数が増えたときの伸び方。整った2分探索木の探索は O(log n) になる
ミニクイズ
根がA、Aの左の子がB・右の子がC、Bの左の子がD・右の子がE、Cの左の子がF・右の子がGである2分木がある。この木を中間順（左→根→右）でたどったとき、3つ目に現れる節はどれか。
正解は 4番：E
中間順は「左の部分木 → 自分 → 右の部分木」の順にたどります。AからまずBへ、BからさらにDへ降り、Dには子がないのでDを書きます。Dに戻ってBを書き、次にBの右の子Eを書きます。ここまでに書いたのは D・B・E なので、3つ目はEです。続きは A・F・C・G で、全体では D B E A F C G となります。たどる順番は、まず紙に木を書いて、矢印で囲むようになぞると間違えません。
この分野をまとめて解く → アルゴリズムとプログラミングのミニテスト（全44問）
最終更新：2026-10-06