| 基本情報技術者試験 |
2005年度 ＝ 平成17年度・秋期 |
午前 |
問12 |
すべての葉が同じ深さをもち、葉以外のすべての節点が二つの子をもつ２分木に関して、節点数と深さの関係を表す式はどれか。ここで、n は節点数、k は根から葉までの深さを表す。例に示す２分木の深さk は2である。
| ア n ＝ k (k ＋1)＋1
| イ n ＝ 2k＋3
|
| ウ n ＝ 2k＋1－1
| エ n ＝ (k －1)(k ＋1)＋4
|
ウ
完全２分木とは、根から下方のレベルへ、同一のレベル内では左から右へノード（節点）が詰められている２分木です。
すなわち、完全２分木は、最も下流側のレベル以外は、すべてノードが詰まっています。また、最下流のレベルは、もちろんすべて詰まっていてもよいのですが、左側から詰められていれば、途中までしかノードがなくても構いません。
そのため、木の深さがk である完全２分木がもつことのできるノードは、最大で2k＋1－1となります。
※たとえば、深さが1であれば3、深さが2であれば7、深さが3であれば15です。
