木、枝、木の深さ、節点の個数

応用情報技術者平成30年秋期 午前問6

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

問題文にある「葉以外の節点はすべて二つの子をもち，根から葉までの深さがすべて等しい木」は次のような構造をもつ木です。
概念としては、
・枝は６本　※根から葉までの枝数の総数
・葉は４個
・深さは２　※根から葉までの枝数
・節点は７個

ア、イ、ウは間違いますね。

「葉以外の節点はすべて二つの子をもち，根から葉までの深さがすべて等しい木」は完全2分木と呼ばれ、木の深さが「n」であれば葉の数は「2n」、葉の数が「n」であれば、葉以外の節点の数(根を含む)は「n－1」であるという特徴を持っています。

参照：
https://www.ap-siken.com/kakomon/23_toku/q6.html