最終更新日:2026年11月7日
fe fe-technology algorithm data-structure
まず結論
完全2分木では、各段の節点数が 1、2、4、8、… と2倍ずつ増えることを押さえると、多くの問題を判断できます。
基本情報技術者試験では、まず次の関係を使えるようにしておくと十分です。
深さ d
→ 葉の数 = 2^d
葉の数 L
→ 葉以外の節点数 = L - 1
全節点数 N
→ 2^(d+1) - 1
枝の数
→ 全節点数 - 1
特に重要なのは、式を丸暗記することではありません。
小さい木を書いて数えると、式を忘れても判断できます。
このページでは、完全2分木の形・節点数・葉・深さの関係を中心に扱います。左右の大小関係を使って探索する木は、2分探索木とは? を参照してください。
直感的な説明
深さ2の完全2分木を考えます。
○
/ \
○ ○
/ \ / \
○ ○ ○ ○
この木では、
- 根:1個
- 深さ1の節点:2個
- 深さ2の節点:4個
なので、全節点数は、
1 + 2 + 4 = 7
です。
一番下の4個は葉なので、
葉 = 4個
葉以外 = 3個
となります。
また、節点をつなぐ枝は6本です。
全節点 7
枝 6
木では、枝の数は節点数より1少ないという関係があります。
定義・仕組み
2分木とは
2分木は、各節点が最大2個の子をもつ木構造です。
親
/ \
子 子
子をもたない節点を 葉(leaf) といいます。
一番上の節点を 根(root) といいます。
完全2分木とは
FEの問題では、「葉以外の節点はすべて2つの子をもち、根から葉までの深さがすべて等しい木」が出てきます。
このような木では、各深さの節点数が、
深さ0:1
深さ1:2
深さ2:4
深さ3:8
と増えます。
つまり、深さ d にある節点数は、
2^d
です。
葉の数
すべての葉が同じ深さ d にあるので、葉の数は、
2^d
です。
例えば深さ3なら、
2^3 = 8
なので、葉は8個です。
全節点数
深さ d の完全2分木では、全節点数は、
1 + 2 + 4 + ... + 2^d
です。
この和は、
2^(d+1) - 1
になります。
例えば深さ2なら、
2^(2+1) - 1
= 8 - 1
= 7
です。
葉以外の節点数
葉の数を L とすると、葉以外の節点数は、
L - 1
です。
例えば葉が4個なら、葉以外の節点は3個です。
葉 = 4
葉以外 = 3
この関係は、完全2分木の選択問題で非常に使いやすいです。
枝の数
木構造では、節点数を N とすると枝の数は、
N - 1
です。
例えば全節点が7個なら、枝は6本です。
科目Aでどう出る?
科目Aでは、完全2分木の葉、節点、枝、深さについて、正しい関係を選ぶ問題が出ます。
判断軸1:深さから葉を求める
根の深さを0とすると、深さ d の完全2分木の葉の数は、
2^d
です。
深さ0 → 1
深さ1 → 2
深さ2 → 4
深さ3 → 8
と並べると分かりやすいです。
判断軸2:全節点数は葉だけではない
深さ2なら、葉は4個ですが、全節点は7個です。
葉 = 4
全節点 = 7
葉の数と全節点数を混同しないようにします。
判断軸3:枝は節点より1少ない
木では、
枝 = 節点 - 1
です。
「枝の数と節点数が同じ」という選択肢は切れます。
判断軸4:葉と葉以外の関係
完全2分木では、
葉 = L
葉以外 = L - 1
です。
この関係は、具体例を1つ覚えておくと確認しやすいです。
葉4個
→ 葉以外3個
判断軸5:最大比較回数は「深さ」ではなく通る節点数
節点の数だけでなく、根から最も深い葉まで何回比較するかを問われる場合があります。ここでは、根の深さを0と数え、各段がすべて埋まった2分探索木を考えます。
| 根からの段(レベル) | 深さ | その段の節点数 | 累計節点数 |
|---|---|---|---|
| 1段目(根) | 0 | 1 | 1 |
| 2段目 | 1 | 2 | 3 |
| 3段目 | 2 | 4 | 7 |
| 4段目(葉) | 3 | 8 | 15 |
15節点がこの形に並ぶと、最大深さは3(枝が3本)、比較回数は4回(通る節点が4個)です。
次は記事独自の探索例です。左右の大小関係を満たす木で、値「25」を探します。
40 ① 40と比較:左へ
/ \
20 60 ② 20と比較:右へ
/ \ / \
10 30 50 70 ③ 30と比較:左へ
/\ /\ /\ /\
5 15 25 35 45 55 65 75 ④ 25と比較:発見
40 → 20 → 30 → 25
1 2 3 4 回目の比較
この場合は最下段の25を見つけるまで4回比較します。探す値が存在しない場合も、葉まで比較してから子が空であると分かることがあります。「データと節点の値を比較した回数」と、実装上の「子が空か確認する処理回数」は分けて数えます。
すべての段が埋まったこの形なら、次の関係が使えます。
最大深さ d(根=0)
全節点数 N = 2^(d+1) - 1
最大の節点比較回数 = d + 1 = log2(N + 1)
ただし、15節点ならどんな2分探索木でも4回で済む、という意味ではありません。子が片側に偏った木では比較回数が増えます。今回の関係を使えるのは、与えられた木の形が全段そろっている場合です。左右の大小関係を追う操作は2分探索木とは?で確認できます。
どんな場面で使う?
完全2分木は、木構造の基本を理解するために使われます。
FEでは、次のようなテーマにつながります。
- 二分木
- ヒープ
- 二分探索木
- 優先度付きキュー
- 木の探索
ただし、今回のような問題では、まず構造を大きく広げず、
1 → 2 → 4 → 8
という増え方と、葉・節点・枝の関係を確実に押さえる方が重要です。
よくある誤解・混同
深さ d なら葉は 2^(d-1)
根の深さを0とする定義では誤りです。
深さ0 → 葉1個
深さ1 → 葉2個
深さ2 → 葉4個
なので、葉の数は、
2^d
です。
全節点数は 2^d
2^d は最下段、つまり葉の数です。
全節点数は、上の段もすべて足すので、
2^(d+1) - 1
です。
節点数 N なら深さは log2 N
そのままでは成り立ちません。
完全2分木では、
N = 2^(d+1) - 1
なので、
d = log2(N + 1) - 1
となります。
試験では、式を変形するよりも、節点数が、
1, 3, 7, 15, 31, ...
と増えることを覚えておくと判断しやすいです。
「完全2分木」という言葉は教材によって使い方が異なることがある
木構造の用語は、教材によって「完全2分木」「完備2分木」「真2分木」などの呼び方が異なることがあります。
FEの問題では、問題文で与えられた条件を優先して読むのが安全です。
今回のように、
葉以外は必ず2つの子をもつ
すべての葉の深さが等しい
と書かれていれば、その条件から直接考えます。
まとめ(試験直前用)
- 各段の節点数は 1、2、4、8、… と増える
- 深さ d の葉の数は
2^d - 全節点数は
2^(d+1) - 1 - 葉が L 個なら葉以外の節点は
L - 1 - 枝の数は全節点数より1少ない
- 最大の節点比較回数は、根の深さを0とすると 最大深さ + 1(全段が埋まった木の例)
- 迷ったら深さ2程度の小さい木を書いて実際に数える
葉 L
→ 葉以外 L - 1
全節点 N
→ 枝 N - 1