基本情報技術者試験 2005年度 = 平成17年度・秋期 午前 問12

 すべての葉が同じ深さをもち、葉以外のすべての節点が二つの子をもつ2分木に関して、節点数と深さの関係を表す式はどれか。ここで、n は節点数、k は根から葉までの深さを表す。例に示す2分木の深さk は2である。


k = 2

ア n k (k +1)+1 イ n = 2k+3
ウ n = 2k+1-1 エ n = (k -1)(k +1)+4

解答



解説

 完全2分木とは、根から下方のレベルへ、同一のレベル内では左から右へノード(節点)が詰められている2分木です。
 すなわち、完全2分木は、最も下流側のレベル以外は、すべてノードが詰まっています。また、最下流のレベルは、もちろんすべて詰まっていてもよいのですが、左側から詰められていれば、途中までしかノードがなくても構いません。
 そのため、木の深さがk である完全2分木がもつことのできるノードは、最大で2k+1-1となります。
※たとえば、深さが1であれば3、深さが2であれば7、深さが3であれば15です。


BohYoh.comトップページへ