問題12
すべての葉が同じ深さをもち，葉以外のすべての節点が二つの子をもつ2分木に関して，節点数と深さの関係を表す式はどれか。ここで， n は節点数， k は根から葉までの深さを表す。例に示す2分木の深さ k は2である。
| ア | n ＝ k (k＋1)＋1 |
| イ | n ＝ 2k＋3 |
| ウ | n ＝ 2k+1－1 |
| エ | n ＝ (k－1)(k＋1)＋4 |
解答・解説を見る
解答：ウ
k は根から葉までの深さ k と節点数 n は、次のようになる。
- n ＝０……………１
- n ＝１……………３（１＋２）
- n ＝２……………７（１＋２＋４）
- n ＝３……………１５（１＋２＋４＋８）
よって、 n ＝ 2k+1－1 となる。