葉以外の節点は全て二つの子をもち，根から葉までの深さが全て等しい木を考える。
この木に関する記述のうち，適切なものはどれか。
ここで，木の深さとは根から葉に至るまでの枝の個数を表す。
また，節点には根及び葉も含まれる。
正答4
解説
正解は4です。
この問題は、葉以外の節点が必ず2つの子をもち、全ての葉が同じ深さにある木（完全2分木）の性質を問うています。
例えば深さ2の木は、根1個、深さ1の節点2個、葉4個の合計7節点で、枝は6本です。
この例を当てはめると、各選択肢の正誤を確かめられます。
【選択肢別解説】
1：× 木では、根以外の全ての節点に、親へつながる枝が1本ずつあります。
そのため枝の個数は節点の個数より1少なく、枝がnなら節点はn＋1個です。
2：× 深さが1増えるごとに節点数は2倍になるので、深さnの木の葉は2^n個です。
深さ2の例では葉は4個で、2^(2－1)＝2個にはなりません。
3：× 深さnの木の節点数は2^(n＋1)－1個です。
節点がn個なら深さはlog_2(n＋1)－1となり、log_2nではありません。
深さ2の例では、log_2 7は約2.8で一致しません。
4：○ 葉以外の節点の個数をm、葉の個数をnとします。
葉以外の節点は2本ずつ枝を出すので、枝は2m本です。
枝の数は節点数より1少ないので、2m＝(m＋n)－1が成り立ち、m＝n－1となります。
深さ2の例でも、葉4個に対して葉以外の節点は3個です。
【ポイント】
「枝の数＝節点数－1」は全ての木で成り立つ基本性質です。
全ての非葉節点が子を2つもつ2分木では、葉の数は常に非葉節点の数より1多くなります。