対象試験と出題頻度
木構造（ツリー構造）は、ITパスポート・基本情報技術者・応用情報技術者のすべてで出題されるテーマです。
データ構造の中でも出題範囲が広く、「二分木」「二分探索木」「走査（行きがけ順・通りがけ順・帰りがけ順・幅優先）」など派生トピックが多いのが特徴です。
基本情報の科目Bでは木構造を操作する擬似言語のプログラムが繰り返し出題されています。
詳細をクリックして確認
ITパスポート
基本情報技術者
応用情報技術者
★★★★☆
ランクA（重要）必ず覚えておくべき
用語の定義
情報処理試験を勉強していると、「木構造って何？ 二分木や探索木とどう違うの？」と混乱しがちです。
木構造（Tree Structure）とは、一言で言うと
「1つの根（ルート）から階層的に枝分かれしていくデータ構造」
のことです。
イメージとしては、「パソコンのフォルダ（ディレクトリ）構造」そのものです。
Cドライブの中にDocumentsフォルダがあり、その中にさらにサブフォルダがある。この階層構造がまさに木構造です。上を「根」、枝分かれの分岐点を「節（ノード）」、末端を「葉（リーフ）」と呼びます。
📊 木構造（ツリー構造）の基本情報
| 項目 | 内容 |
|---|---|
| 英語名 | Tree Structure |
| 構成要素 | 根（ルート）、節（ノード）、枝（エッジ）、葉（リーフ） |
| 代表的な種類 | 二分木、二分探索木、完全二分木、ヒープ、B木 |
| 主な用途 | ファイルシステム、データベースの索引、構文解析 |
解説
配列やリストは「一列に並んだ」データ構造ですが、実世界には「階層」や「親子関係」を持つデータが多く存在します。組織図、HTMLの要素、ファイルシステムなどがその典型です。こうした階層関係を自然に表現するために木構造が使われます。
木構造の構成要素
木構造を理解するうえで必ず覚えるべき用語は4つです。
▼ 木構造の構成要素と図解
A ← 根（ルート）：最上位のノード
／ ＼
B C ← 節（ノード）：枝分かれの分岐点
／ ＼ ／ ＼
D E F G ← 葉（リーフ）：子を持たない末端
※ A→B、A→C のような接続線を 枝（エッジ） と呼ぶ
Aが「親」、B・Cは「Aの子」。B・Cは互いに「兄弟」。根からの階層数を「深さ」と呼ぶ。
二分木と二分探索木
木構造の中で最も出題されるのが「二分木（バイナリツリー）」です。
各ノードが持てる子の数を最大2つに制限した木構造で、左の子と右の子で区別します。
さらに、二分木に「左の子 ＜ 親 ＜ 右の子」という大小関係のルールを加えたものが「二分探索木（バイナリサーチツリー）」です。このルールのおかげで、データの検索を効率的に行えます。
▼ 二分探索木のルール「左 ＜ 親 ＜ 右」
10
／ ＼
5 15
／ ＼ ／ ＼
3 7 12 18
どの部分を見ても「左 ＜ 親 ＜ 右」を満たしている。左端から右端へ値を読むと 3→5→7→10→12→15→18 と昇順になる。
▶ 二分木の走査方法（4種類）（クリックで展開）
二分木の全ノードを訪問する方法（走査・トラバーサル）は4種類あります。応用情報ではこの4種類の区別を問う出題が定番です。
| 走査方法 | 訪問順のルール | 上図（10,5,15,3,7,12,18）の結果 |
|---|---|---|
| 行きがけ順 （先行順・前順） |
親 → 左 → 右 ノードに到着した時点で読む |
10 → 5 → 3 → 7 → 15 → 12 → 18 |
| 通りがけ順 （中間順・間順） |
左 → 親 → 右 左の子を探索し終えた時点で読む |
3 → 5 → 7 → 10 → 12 → 15 → 18 ※昇順になる |
| 帰りがけ順 （後行順・後順） |
左 → 右 → 親 子を全て訪問し終えた時点で読む |
3 → 7 → 5 → 12 → 18 → 15 → 10 |
| 幅優先 （レベル順） |
根に近い階層から順に読む | 10 → 5 → 15 → 3 → 7 → 12 → 18 |
覚え方のコツは、「行きがけ＝到着時」「通りがけ＝左から戻った時」「帰りがけ＝全部終わった時」と、ノードを「いつ読むか」で区別することです。
通りがけ順で昇順に並ぶ点は二分探索木の大きな特徴なので、ここだけは確実に押さえてください。
では、この用語が試験でどのように出題されるか見ていきましょう。
💡 木構造（ツリー構造）の核心を3行で
・1つの根から階層的に枝分かれする構造。フォルダ階層が身近な実例
・二分木は子の数が最大2つ。「左＜親＜右」のルールを加えると二分探索木になる
・走査は4種類あり、通りがけ順で二分探索木を走査すると昇順に値が得られる
試験ではこう出る！
木構造は、試験区分ごとに問われるレベルが大きく異なります。ITパスポートでは用語レベル、基本情報では操作のトレース、応用情報では走査方法の区別が中心です。
📊 過去問での出題実績
| 試験回 | 出題内容 | 問われたポイント |
|---|---|---|
| IP R4 問90 |
ファイルシステムを木構造で表現したとき、「節」と「葉」に該当するものを問う問題。 | ・節＝ディレクトリ、葉＝ファイルの対応 ・木構造の用語（根・節・葉）を理解しているか |
| FE H28秋 午前 問6 |
4つの二分木の図から「二分探索木になっているもの」を選ぶ問題。 | ・「左＜親＜右」のルールを全ノードで満たすか確認できるか ・左端から右端へ読んで昇順になれば二分探索木 |
| AP R6秋 午前 問5 |
二分探索木の構造を問う問題。 | ・二分探索木の性質を正確に理解しているか ・H28秋FEと同系統の出題が繰り返されている |
| AP H26秋 午前 問4 |
配列で二分木を表現し、先頭から順に調べた場合の走査方法を問う問題。 | ・行きがけ順/通りがけ順/帰りがけ順/幅優先の違い ・配列インデックス順＝レベル順＝幅優先が正解 |
| FE 科目B サンプル 問9 |
二分木を走査するプログラムのトレース問題。 | ・擬似言語で再帰的に木を走査するコードを追えるか ・深さ優先探索の動きを1手ずつトレースする |
📝 IPA試験での出題パターン
パターン1：「二分探索木はどれか」（FE・AP科目A）
複数の二分木の図が提示され、二分探索木の条件を満たすものを選ぶ形式。各ノードを左から右へ読み、昇順になっているかを確認すれば即答できる。
パターン2：「走査方法の区別」（AP科目A）
AP H26秋 問4やR3春 問6のように、配列やプログラムで木を走査する手順を示し、4つの走査方法のどれに該当するかを問う形式。「行きがけ＝親が先」「帰りがけ＝親が最後」「幅優先＝階層順」で判別する。
パターン3：「擬似言語での木構造操作」（FE科目B）
科目Bサンプル問9のように、再帰を使って二分木を走査するプログラムをトレースする形式。木構造の知識に加え、再帰呼び出しの流れを追える力が必要になる。
ITパスポートでは「根・節・葉」の用語を押さえれば十分です。基本情報以上を受ける場合は二分探索木の「左＜親＜右」ルールと走査方法を確実に覚えてください。
【確認テスト】理解度チェック
ここまでの内容を理解できたか、簡単なクイズで確認してみましょう。
Q. 木構造（ツリー構造）に関する記述として、最も適切なものはどれでしょうか？
- A. 先に格納したデータから先に取り出す先入れ先出し（FIFO）方式のデータ構造であり、待ち行列とも呼ばれる。
- B. 各要素がポインタで次の要素を指し示す一方向の連結構造であり、先頭または末尾への挿入・削除が効率的である。
- C. 1つの根（ルート）から階層的に枝分かれする構造であり、各ノードが最大2つの子を持つものを二分木と呼ぶ。
正解と解説を見る
正解：C
解説：
木構造は1つの根から階層的に枝分かれするデータ構造であり、子の数を最大2つに制限したものが二分木です。ファイルシステムのディレクトリ階層が代表的な実例になります。
選択肢Aはキュー（Queue）の説明です。FIFO方式で到着順にデータを処理するデータ構造であり、木構造とは関係がありません。選択肢Bは連結リスト（Linked List）の説明です。ポインタによる線形な接続構造であり、階層的な枝分かれは持ちません。
よくある質問（FAQ）
Q. 「完全二分木」と「二分探索木」はどう違いますか？
完全二分木は「形」に関する条件で、葉以外の全ノードが2つの子を持ち、かつ全ての葉の深さが等しい二分木のことです。一方、二分探索木は「値の大小関係」に関する条件で、「左＜親＜右」を全ノードで満たす二分木です。両方の条件を同時に満たすケースもありますが、完全二分木でも値の大小関係が崩れていれば二分探索木ではありません。
Q. 「ヒープ」や「B木」も木構造の仲間ですか？
どちらも木構造の一種です。ヒープは「親の値が子の値より常に大きい（または小さい）」という条件を持つ完全二分木で、優先度付きキューの実装に使われます。B木は1つのノードが複数のキーを持ち、子の数も2つを超えることができる多分木で、データベースのインデックス構造に採用されています。IPA試験ではB木は応用情報の午後問題で出題される程度なので、ITパスポートや基本情報の受験では深追い不要です。
Q. 二分探索木の検索は配列の検索より速いですか？
バランスの取れた二分探索木であれば、検索の計算量はO(log n)となり、配列の線形探索O(n)より高速です。ただし、データの追加順によって木が一方に偏ると、最悪の場合はO(n)に退化します。この偏りを自動的に修正するデータ構造がAVL木や赤黒木で、応用情報の過去問ではAVL木に関する出題もあります。
Q. 実務のプログラミングで木構造はどんな場面で使いますか？
Webフロントエンド開発では、HTMLの要素をDOMツリー（Document Object Model）という木構造で管理しています。JavaScriptでdocument.querySelectorを使ってHTML要素を検索する処理は、裏側でこのDOMツリーを走査しています。また、JSONやXMLのパースも木構造として処理されるため、日常的なWeb開発で意識せずとも木構造に触れている場面は多いです。
