平成23年度 特別 応用情報技術者試験 午前 問6
テクノロジ／アルゴリズム葉以外の節点はすべて二つの子をもち，根から葉までの深さがすべて等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，深さとは根から葉に至るまでの枝の個数を表す。
出典：平成23年度 特別 応用情報技術者試験 午前 問6
- ア枝の個数がnならば，葉を含む節点の個数もnである。
- イ木の深さがnならば，葉の個数は2^(n-1)である。
- ウ節点の個数がnならば，深さはlog2 nである。
- エ葉の個数がnならば，葉以外の節点の個数はn－1である。
正解：エ
解説
すべての内部節点が2分岐し，根から葉までの深さが等しい木は「完全2分木」です。深さnの完全2分木では，葉の数は2^n個であり，全節点数は2^(n+1)－1，葉以外（内部）の節点数は2^n－1，すなわち葉の個数をnとすると葉以外の節点数はn－1になります。
選択肢ごとの解説
- ア誤り。枝の個数は節点数－1に等しく，葉を含む節点の個数と枝の個数は一致しません。
- イ誤り。深さnの完全2分木の葉の個数は2^nであり，2^(n-1)ではありません。
- ウ誤り。節点の個数がnのとき，深さはlog2(n+1)に近い形になり，単純にlog2 nとはなりません。
- エ正しい。完全2分木では内部節点は必ず2個の子をもつため，葉の個数がnならば内部（葉以外）の節点の個数はn－1になります。