対象試験と出題頻度
2分木（二分木）は、ITパスポート・基本情報技術者・応用情報技術者の全区分で出題されるテーマです。
データ構造の基礎として、「2分探索木の条件判定」「要素の追加・削除後の木の再構成」「走査順（行きがけ順・通りがけ順・帰りがけ順）の判定」など、幅広い角度から繰り返し問われています。
詳細をクリックして確認
ITパスポート
基本情報技術者
応用情報技術者
★★★★☆
ランクA（重要）必ず覚えておくべき
用語の定義
情報処理試験を勉強していると、「2分木って木構造と何が違うの？2分探索木とは別物？」と混乱しがちです。
2分木（Binary Tree）とは、一言で言うと
「すべてのノード（節）が持つ子の数が最大2つ（左の子と右の子）である木構造」
のことです。
イメージとしては、「トーナメント表」です。
スポーツのトーナメント表を思い浮かべてください。各対戦カード（ノード）から伸びる線は必ず2本以下で、勝ち上がった先にまた次の対戦がある。この「どの分岐も最大2方向」という構造が2分木そのものです。
📊 2分木の基本情報
| 項目 | 内容 |
|---|---|
| 英語名 | Binary Tree（binary＝2つの、tree＝木） |
| 分類 | データ構造（木構造の一種） |
| 最大の特徴 | 各ノードの子が最大2つ（左の子・右の子） |
| 代表的な派生 | 2分探索木、完全2分木、ヒープ、ハフマン木 |
解説
木構造（ツリー構造）は、1つの根（ルート）から階層的に枝分かれするデータ構造の総称です。ファイルシステムのフォルダ階層やHTMLのDOM構造が身近な例です。
木構造の中でも「各ノードの子が最大2つ」という制約を加えたものが2分木であり、この制約があるからこそ探索や並べ替えの効率化に応用できます。
2分木の構成要素
2分木を構成する用語は、木構造全般と共通しています。根（ルート）は最上位のノード、葉（リーフ）は子を持たない末端のノード、そして各ノードから見た上位を親、下位を子と呼びます。
ノードの階層の深さを「深さ（depth）」、木全体の最大深さを「高さ（height）」と表現します。
📐 2分木の構造図
A ← 根（ルート）：深さ0
／ ＼
B C ← 深さ1
／ ＼ ＼
D E F ← 葉（リーフ）：深さ2
各ノードの子は最大2つ。Cの左の子は空でも問題なし。高さ＝2。
2分木の主な派生形
2分木はあくまで「形のルール」だけを定めた概念です。そこにデータの並び順や形状の制約を追加すると、用途別の派生形になります。
📊 2分木の派生形の比較
| 種類 | 追加の条件 | 用途 |
|---|---|---|
| 2分探索木 | どのノードも「左の子 ＜ 親 ＜ 右の子」を満たす | データの高速な検索・挿入・削除 |
| 完全2分木 | 最下層以外のすべての階層が埋まり、最下層は左詰め | ヒープの実装（優先度付きキュー） |
| ヒープ | 親 ≧ 子（最大ヒープ）または 親 ≦ 子（最小ヒープ） | 最大値・最小値の高速な取り出し |
| ハフマン木 | 出現頻度の低い要素から順に結合して構築 | データの可逆圧縮 |
| AVL木 | 左右の部分木の高さの差が常に1以下（平衡条件） | 偏りのない高速探索を保証 |
2分木の走査（たどり方）
2分木に格納されたデータを順番に処理するには「走査（traversal）」を行います。
走査には大きく深さ優先と幅優先の2系統があり、深さ優先はさらに3種類に分かれます。
▶ 3種類の深さ優先探索と幅優先探索（クリックで展開）
走査の対象となる2分木
1
／ ＼
2 3
／ ＼ ／ ＼
4 5 6 7
| 走査方法 | ルール | 結果 |
|---|---|---|
| 行きがけ順 （先行順／preorder） |
親 → 左の子 → 右の子 | 1, 2, 4, 5, 3, 6, 7 |
| 通りがけ順 （中間順／inorder） |
左の子 → 親 → 右の子 | 4, 2, 5, 1, 6, 3, 7 |
| 帰りがけ順 （後行順／postorder） |
左の子 → 右の子 → 親 | 4, 5, 2, 6, 7, 3, 1 |
| 幅優先探索 （レベル順） |
浅い階層から順に左→右 | 1, 2, 3, 4, 5, 6, 7 |
覚え方のコツは、「親をいつ読むか」で分類することです。行きがけ順は「最初に親」、通りがけ順は「左→親→右で真ん中に親」、帰りがけ順は「最後に親」と整理すれば混乱しません。
なお、通りがけ順で2分探索木を走査すると、データが昇順に並ぶ性質があります。これは頻出ポイントです。
▶ 2分探索木の追加・削除の仕組み（クリックで展開）
追加の手順：根から比較を開始し、追加する値が現在のノードより小さければ左へ、大きければ右へ進みます。空のポジションに到達したらそこに挿入します。
削除の手順：削除対象のノードの子の数で処理が分かれます。子がない場合はそのまま削除、子が1つの場合は子を繰り上げ、子が2つある場合は「左部分木の最大値」または「右部分木の最小値」を削除位置に移動させて木を再構成します。
R6秋期 応用情報 午前 問5では、まさにこの「子が2つあるノードの削除」が出題されました。削除対象に最も近い値を見つける操作がポイントです。
では、この用語が試験でどのように出題されるか見ていきましょう。
💡 2分木の核心を3行で
・各ノードの子が最大2つ（左の子・右の子）という形状ルールを持つ木構造
・2分探索木は「左 ＜ 親 ＜ 右」の大小関係、完全2分木は「全階層が左詰めで埋まる」という形状条件を追加した派生形
・走査は「親をいつ読むか」で行きがけ順・通りがけ順・帰りがけ順の3種+幅優先の計4種を区別する
試験ではこう出る！
2分木は、科目A（午前）の定番テーマとして毎回のように出題されています。科目B（午後）でも擬似言語を使った走査プログラムの読み取り問題として登場します。
出題パターンは大きく3つに分かれます。
📊 過去問での出題実績
| 試験回 | 出題内容 | 問われたポイント |
|---|---|---|
| FE R7年度 科目A 問3 |
2分探索木のa～gの値の大小関係として適切なものを選ぶ問題。 | ・「左 ＜ 親 ＜ 右」の条件を全ノードに適用できるか ・部分木単位での大小関係の理解 |
| AP R6秋 午前 問5 |
2分探索木から要素12を削除し、別の要素を移動するだけで再構成するにはどの要素を移動するか。 | ・子が2つあるノードの削除手順 ・「右部分木の最小値」の特定 |
| AP H29秋 午前 問5 |
配列で表現した2分木を先頭から順に調べることがどの探索に当たるか。 | ・配列のインデックス順＝レベル順（幅優先探索） ・深さ優先の3種との区別 |
| FE サンプル 科目A 問5 |
2分探索木になっている2分木を図から選ぶ問題。 | ・左から節点を並べて昇順になるかの確認 ・H28秋FE問6の流用問題 |
| FE サンプル 科目B 問9 |
擬似言語で2分木を再帰的に走査する関数の出力を問う問題。 | ・通りがけ順（inorder）の動作理解 ・再帰呼び出しのトレース力 |
📝 IPA試験での出題パターン
パターン1：「2分探索木の条件判定」
図示された木の中から2分探索木の条件を満たすものを選ぶ、または大小関係として正しいものを選ぶ形式。ひっかけとして、部分的には条件を満たすが全体では違反している木が選択肢に紛れ込む。「すべてのノードで左 ＜ 親 ＜ 右」を満たすかどうかを全体で確認することが必要。
パターン2：「要素の追加・削除後の再構成」
2分探索木から特定の要素を削除した後、どの要素を移動すれば木を維持できるかを問う形式。子が2つあるノードの削除では「左部分木の最大値」か「右部分木の最小値」を移動する――この手順さえ知っていれば即答できる。
パターン3：「走査順の判定」
2分木の走査結果がどの走査方法に該当するかを選ぶ形式。行きがけ順・通りがけ順・帰りがけ順・幅優先の4つを正確に区別できるかが問われる。科目Bでは擬似言語で再帰関数のトレースを求められることもある。
試験ではここまででOKです。AVL木の回転操作やB木の詳細構造まで問われることは稀なので、深追いは不要です。
【確認テスト】理解度チェック
ここまでの内容を理解できたか、簡単なクイズで確認してみましょう。
Q. 2分木に関する説明として、最も適切なものはどれでしょうか？
- A. すべてのノードが持つ子の数が最大2つである木構造であり、2分探索木やヒープなどの基盤となるデータ構造である。
- B. 親ノードの値が常に子ノードの値以上（または以下）である木構造であり、最大値や最小値の取り出しに特化している。
- C. どのノードも「左の子 ＜ 親 ＜ 右の子」の大小関係を満たす木構造であり、データの高速な検索・挿入・削除に使われる。
正解と解説を見る
正解：A
解説：
2分木は「各ノードの子が最大2つ」という形状の定義であり、データの大小関係や親子間の値の制約は含みません。この形状を基盤に、追加の条件を加えたものが各種の派生形です。
選択肢Bはヒープの説明です。ヒープは完全2分木の形状に「親 ≧ 子」（最大ヒープ）または「親 ≦ 子」（最小ヒープ）の条件を加えたもので、2分木とは別の概念です。選択肢Cは2分探索木の説明です。2分探索木は2分木の一種ですが、「左 ＜ 親 ＜ 右」という大小関係は2分木の定義には含まれません。
よくある質問（FAQ）
Q. 「完全2分木」と「飽和2分木（全2分木）」は何が違いますか？
完全2分木は「最下層以外のすべての階層が埋まっており、最下層は左詰め」である木です。一方、飽和2分木（full binary tree）は「すべての葉が同じ深さにあり、葉以外のノードがすべて子を2つ持つ」木です。完全2分木は配列で効率的に表現でき、ヒープの実装に使われます。飽和2分木はすべてのノードが完全に埋まった理想形であり、高さhの場合のノード数は 2^(h+1) – 1 個になります。
Q. 2分探索木の探索の計算量はどのくらいですか？
平均的にはO(log n)です。ただし、データが昇順や降順にしか入らない場合は木が一方向に偏り（縮退）、最悪でO(n)になります。この偏りを防ぐために、AVL木やB木のような「平衡2分探索木」が考案されました。試験では「平均O(log n)、最悪O(n)」の対比を問われることがあります。
Q. 逆ポーランド記法と2分木の走査には関係がありますか？
あります。数式を2分木で表現したとき、帰りがけ順（後行順）で走査すると逆ポーランド記法の式が得られます。同様に、行きがけ順で走査するとポーランド記法（前置記法）、通りがけ順で走査すると通常の中置記法が得られます。試験では「帰りがけ順＝逆ポーランド記法」の関連が問われることがあります。
Q. 実務では2分木はどのような場面で使われていますか？
データベースのインデックス構造（B木やB+木）、ファイル圧縮（ハフマン符号化）、優先度付きキュー（ヒープ）、構文解析（抽象構文木）など、あらゆる場面で2分木の考え方が活用されています。特にデータベースのインデックスはB+木を基盤にしており、大量データの高速検索を支える根幹技術です。
