平成25年度 秋期 応用情報技術者試験 午前 問6
テクノロジ／アルゴリズム葉以外の節点は全て二つの子をもち，根から葉までの深さが全て等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，深さとは根から葉に至るまでの枝の個数を表す。また，節点には根及び葉も含まれる。
出典：平成25年度 秋期 応用情報技術者試験 午前 問6
- ア枝の個数がnならば，節点の個数もnである。
- イ木の深さがnならば，葉の個数は2ⁿ⁻¹である。
- ウ節点の個数がnならば，深さはlog₂nである。
- エ葉の個数がnならば，葉以外の節点の個数はn－1である。
正解：エ
解説
完全二分木（各内部節点が二つの子をもち，深さが全て等しい木）では，葉の個数がnのとき，各内部節点は必ず二つの子をもつため，葉以外の節点の個数はn－1になります（2分木の性質として，葉の数＝内部節点の数＋1）。
選択肢ごとの解説
- ア誤り。完全二分木では枝の個数は節点の個数から1を引いた数になるため，枝の個数がnのとき節点の個数はn＋1です。
- イ誤り。深さがnの完全二分木の葉の個数は2ⁿであり，2ⁿ⁻¹ではありません。
- ウ誤り。節点の個数がnのとき，深さはlog₂((n+1)/2)程度の関係になり，単純にlog₂nとは表せません。
- エ正しい。葉の個数がnならば，葉以外の節点（内部節点）の個数はn－1になります。