応用情報技術者試験 平成30年秋 午前問6 解説付き過去問
問題
葉以外の節点はすべて二つの子をもち、根から葉までの深さがすべて等しい木を考える。
この木に関する記述のうち、適切なものはどれか。
ここで、木の深さとは根から葉に至るまでの枝の個数を表す。
また、節点には根及び葉も含まれる。
正解
解説
本問題では、二分木の構造に関する理解が試されています。特に注目されるのは、各節点が二つの子を持つ完全二分木における節点と葉の関係です。
- 完全二分木の定義
完全二分木とは、葉以外のすべての節点が正確に二つの子節点を持ち、葉のレベルを除いて全てのレベルが完全に充填されている木のことを指します。この性質から、木の構造が非常に規則正しく、数学的に扱いやすい特徴があります。 - 節点と葉の数の関係
完全二分木において、葉の数をnとすると、葉以外の節点の数は必ずn-1となります。これは、木の各レベルで節点数が前のレベルの2倍になる性質と、最下層にある葉の数がそれ以外の全節点の数よりも常に1多いことに起因します。具体的には、1つの節点が2つの葉を生むため、葉の数nに対して、それを生成する節点はn/2、その親はn/4と逆算していくと、最終的に根節点が1つとなり、これらを合計するとn-1となります。
したがって、葉の個数がnであれば、葉以外の節点の個数がn-1であるというのは正しい述べ方です。この問題は完全二分木の基本的な性質を問うものであり、その理解を正確に評価する内容となっています。