最終更新日：2026年9月16日

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分木を考えます。

        ○
      /   \
     ○     ○
    / \   / \
   ○  ○  ○  ○

この木では、

  • 根：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個

どんな場面で使う？

完全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少ない
  • 迷ったら深さ2程度の小さい木を書いて実際に数える
葉 L
→ 葉以外 L - 1

全節点 N
→ 枝 N - 1

© 2024-2026 stemtazoo. All rights reserved.