基本情報技術者試験 - 令和7年6月修了 - 問5

葉以外の節点は全て二つの子をもち，根から葉までの深さが全て等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，木の深さとは根から葉に至るまでの枝の個数を表す。また，節点には根及び葉も含まれる。

ア	枝の個数がnならば，節点の個数もnである。
イ	木の深さがnならば，葉の個数は2^n-1である。
ウ	節点の個数がnならば，木の深さはlog₂nである。
エ	葉の個数がnならば，葉以外の節点の個数はn-1である。

◀ 問4　|　▲ 令和7年6月修了問題一覧　|　問6 ▶

答え：エ
分野：テクノロジ系 › 基礎理論 › アルゴリズムとプログラミング › データ構造

同一問題 ：〔令6修6問5〕〔令5修6問5〕〔令2修1問7〕〔平21修6問5〕

解説：
問題文の木は，葉以外のすべての節点が必ず2つの子を持ち，根から葉までの深さがすべて等しい「完全二分木」です。このような木では，葉の個数をnとすると，葉以外の節点（内部節点）の個数はn-1になるという性質があります。これは，二分木の性質として，内部節点の子の総数は葉の個数と内部節点の個数の合計から根を除いたものに等しくなることから導かれます。正解は「エ」です。

「ア」は枝の個数と節点の個数の関係が誤っています（枝の個数はn，節点の個数はn+1です）。「イ」は深さと葉の個数の関係式が誤りで，正しくは深さnのとき葉の個数は2のn乗になります。「ウ」は節点の個数と深さの関係が不正確です。二分木の基本的な性質は計算問題としてもよく出題されるため，具体例で確認しながら覚えるとよいでしょう。