【問題】
葉以外の節点は全て二つの子をもち、根から葉までの深さが全て等しい木を考える。この木に関する記述のうち、適切なものはどれか。ここで、深さとは根から葉に至るまでの枝の個数を表す。また、節点には根及び葉も含まれる。
ア．枝の個数がｎならば、節点の個数もｎである。
イ．木の深さがｎならば、葉の個数は２^ｎ-1である。
ウ．節点の個数がｎならば、深さはlog2ｎである。
エ．葉の個数がｎならば、葉以外の節点の個数はｎ-1である。
【解答】
実際に、葉以外の節点は全て二つの子をもち、根から葉までの深さが全て等しい木を考えてみる。
根
節点 節点
葉 葉 葉 葉
項目アについて、枝の個数が６個の場合、節点の個数は（節点には根及び葉も含まれるので）７個となるので、不適切である。
項目イについて、木の深さが２ならば、葉の個数は４であり、２＾2-1 ＝ ２なので、不適切である。
項目ウについて、節点の個数が７個ならば、深さは２であり、log2７＝２．Ｘ（２より大きく、３より小さい）ではないので、不適切である。
項目エについて、葉の個数が４個ならば、葉以外の節点の個数は（根も節点として計算するから）３個となり、適切である。
よって、解答はエとなる。