応用情報技術者試験 応用情報技術者試験 平成30年度秋期 午前 問6: 葉以外の節点は全て二つの子をもち，根から葉までの深さが全て等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，木の深さとは根から葉に至るまで

問題本文

葉以外の節点は全て二つの子をもち，根から葉までの深さが全て等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，木の深さとは根から葉に至るまでの枝の個数を表す。また，節点には根及び葉も含まれる。

選択肢

• ア.枝の個数が n ならば，節点の個数も n である。
• イ.木の深さが n ならば，葉の個数は 2^(n-1) である。
• ウ.節点の個数が n ならば，木の深さは log2n である。
• エ.葉の個数が n ならば，葉以外の節点の個数は n-1 である。

正解

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

解説

この木は「葉以外は必ず子が2つ、全ての葉の深さが等しい」完全2分木である。深さdの完全2分木では、葉の個数は2^d、節点の総数は2^(d+1)−1となる。具体的な小さい木で各選択肢を検証すると、葉以外の節点の個数が常に「葉の個数−1」になる関係（エ）だけが成り立つため正解。

選択肢ごとの解説

• ア.木では節点の個数は常に「枝の個数＋1」になる（根以外の各節点に上向きの枝が1本対応するため）。枝がnなら節点はn+1であり、n個ではないので誤り。
• イ.深さnの完全2分木の葉の個数は2^n（深さ1なら葉2個=2^1）。2^(n-1)では1段分少なくなるため誤り。なお問題文の深さ定義（枝の個数）でも2^nが正しい。
• ウ.節点の総数nと深さの関係は n=2^(深さ+1)−1 であり、深さ=log2n と単純に表せない。例えば深さ2なら節点は7個でlog2(7)≒2.8となり一致しないため誤り。
• エ.完全2分木では葉がn個のとき、葉以外（内部節点）はn−1個になる。例えば葉4個なら内部節点は3個。この関係は深さによらず常に成り立つので正解。