応用情報技術者 2013年 秋期 午前2 問06

完全二分木の性質に関する問題【午前2 解説】

要点まとめ

• 結論：葉の数が$n$のとき、葉以外の節点数は必ず$n-1$になる。
• 根拠：完全二分木は全ての非葉節点が2つの子を持ち、節点数と葉数の関係が明確に定まるため。
• 差がつくポイント：深さや節点数から葉数を誤解しやすいが、葉以外の節点数と葉数の関係を正確に理解することが重要。

正解の理由

よくある誤解

解法ステップ

1. 問題文の条件「葉以外の節点は全て2つの子を持つ」「深さが全て等しい」を確認する。
2. 完全二分木の性質として、節点数$N$と葉数$L$の関係式を思い出す。
3. $N=2L-1$から葉以外の節点数を計算する。
4. 選択肢の中でこの関係を満たすものを選ぶ。

選択肢別の誤答解説

• ア: 「枝の個数が$n$なら節点の個数も$n$」は誤り。枝の数は節点数より1少ない。
• イ: 「深さが$n$なら葉の個数は$2^{n-1}$」は誤り。深さ$n$の完全二分木の葉数は$2^n$。
• ウ: 「節点の個数が$n$なら深さは${\log }_{2}n$」は誤り。深さは${\log }_2(n+1)$に近いが正確ではない。
• エ: 葉の個数が$n$なら葉以外の節点数は$n-1$で正しい。

補足コラム

FAQ