平成25年度 秋期 応用情報技術者試験 午前 問6

この木は完全二分木です。深さ d の完全二分木では，葉の個数は 2ᵈ，節点の総数は 2ᵈ⁺¹ − 1 です。例えば深さ2なら，葉は4個，葉以外の節点は 1＋2＝3 個，節点の総数は7個，枝は6本です。

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

• イ: 木の深さが n ならば，葉の個数は 2ⁿ⁻¹ である。
  誤り。深さ n のとき葉の個数は 2ⁿ です（深さ2なら葉は4個）。

• ウ: 節点の個数が n ならば，深さは log₂n である。
  誤り。節点の個数 n ＝ 2ᵈ⁺¹ − 1 なので，深さ d ＝ log₂(n＋1) − 1 です。log₂n にはなりません。

• エ: 葉の個数が n ならば，葉以外の節点の個数は n−1 である。
  正しい。葉の個数が n（＝2ᵈ）のとき，葉以外の節点の個数は 1＋2＋…＋2ᵈ⁻¹ ＝ 2ᵈ − 1 ＝ n − 1 です。

答え

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