問6
葉以外の節点はすべて二つの子をもち，根から葉までの深さがすべて等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，深さとは根から葉に至るまでの枝の個数を表す。
○正解
×不正解
-
枝の個数がnならば，葉を含む節点の個数もnである。
-
木の深さがnならば，葉の個数は2n-1である。
-
節点の個数がnならば，深さはlog2nである。
-
葉の個数がnならば，葉以外の節点の個数はn－1である。
解説
問題の木は、根から一階層ずつ1，2，4，8，16…といったように節点が2倍になっていく構造です。葉の数は一番下の階層の節点の個数になります。
枝の個数がnならば，葉を含む節点の個数もnである。
枝の個数＝葉以外の節点の数×2 なので、葉を含む節点の個数＝n＋1です。
木の深さがnならば，葉の個数は2n-1である。
木の深さ＝根から葉までの枝の数 であるので、葉の個数＝2n です。
節点の個数がnならば，深さはlog2nである。
節点の個数＝2深さ＋1－1 であるので、深さ＝log2(n＋1）－1です。
葉の個数がnならば，葉以外の節点の個数はn－1である。
節点の個数＝葉の個数×2－1 なので、葉以外の節点の個数＝n－1 です。