葉以外の節点はすべて二つの子をもち，根から葉までの深さがすべて等しい木を考える。
この木に関する記述のうち，適切なものはどれか。
ここで，深さとは根から葉に至るまでの枝の個数を表す。
正答4
解説
正解は4です。
この問題の木は、葉以外の節点がすべて2つの子をもち、葉の深さがすべて等しい完全2分木です。
深さnの完全2分木では、葉の数は2ⁿ個、節点の総数は2ⁿ⁺¹－1個になります。
また、根以外の節点には必ず親への枝が1本あるので、枝の数は節点数より1少なくなります。
【選択肢別解説】
1：× 枝は根以外の各節点から親へ1本ずつ出るので、枝の数がnなら節点の数はn＋1です。
節点の数はnではありません。
2：× 深さ0は根だけで葉が1個、深さ1で葉が2個と、深さが1増えるごとに葉は2倍になります。
深さnなら葉の数は2ⁿ⁻¹ではなく2ⁿです。
3：× 節点の数nは2^(深さ＋1)－1なので、深さはlog₂(n＋1)－1です。
log₂nではありません。
4：○ 葉以外の節点の数は1＋2＋…＋2ⁿ⁻¹＝2ⁿ－1です。
葉の数は2ⁿなので、葉の数をnとすると葉以外の節点の数はn－1になります。
【ポイント】
2つの子をもつ節点だけからなる2分木では、「葉の数＝葉以外の節点の数＋1」が常に成り立ちます。
小さな木（深さ1や2）を描いて各選択肢を確かめると、確実に判定できます。