問6 完全二分木

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

1. 枝の個数がnならば、葉を含む節点の個数もnである。
2. 木の深さがnならば、葉の個数はである。
3. 節点の個数がnならば、深さはである。
4. 葉の個数がnならば、葉以外の節点の個数はn-1である。

問のような性質を持つ木構造を、完全二分木と呼びます。図を描いてみればすぐに解けます。
1について、すべての枝はその下に1つの節点を持ちますが、一番上の「根」ノードを含めると、枝の数+1が節点の数になります。
2について、完全二分木の深さをnとすると、葉（最下層の節点）の数がとなる性質を持っています。
3について、葉の個数がnならば、深さはとなります。
4について、完全二分木は深さが1つ増えるたびに葉の数が2倍になります。深さnの木構造において、葉を除いた節点の数は となり（式の展開はWolframAlphaさんにお願いしました）、4が正解になります。