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