平成23年度 特別試験 応用情報技術者試験 午前 問6

この木は完全二分木（全ての段が埋まった二分木）です。深さをdとすると，次のようになります。

• 葉の個数：2ᵈ
• 葉以外の節点の個数：1＋2＋…＋2ᵈ⁻¹ ＝ 2ᵈ−1
• 節点の総数：2ᵈ⁺¹−1
• 枝の個数：節点の総数−1 ＝ 2ᵈ⁺¹−2

例えば深さ2なら，葉4個，葉以外3個，節点7個，枝6本です。

• ア: 枝の個数がnならば，節点の個数もn
  誤り。木では，節点の個数は常に枝の個数＋1です（根以外の各節点に1本ずつ親からの枝がある）。

• イ: 深さがnならば，葉の個数は2ⁿ⁻¹
  誤り。深さnの完全二分木の葉の個数は2ⁿです。例えば深さ1なら葉は2個で，2⁰＝1にはなりません。

• ウ: 節点の個数がnならば，深さはlog₂n
  誤り。節点数n＝2ᵈ⁺¹−1 なので，深さは log₂(n＋1)−1 です。例えば節点3個（深さ1）のとき log₂3 は1になりません。

• エ: 葉の個数がnならば，葉以外の節点の個数はn−1
  正しい。葉の個数が2ᵈのとき，葉以外の節点は2ᵈ−1個なので，葉の個数nに対してn−1個になります。

答え

エ: 葉の個数がnならば，葉以外の節点の個数はn−1