0669デフォルトの名無しさん
2017/10/21(土) 16:51:58.42ID:edOw+XtB深さ d までの葉の総数が最多である二分木を T とする。
このとき、 T には深さ d 未満の葉が少なくとも一つ存在する。もしそうでないと仮定すると、 T の
すべての葉の深さは d 以上であるから、明らかに深さ d までの葉の総数は 2^d 個以下に
なってしまうが、これは矛盾である。
T の深さ d 未満の葉に子ノードを持たせれば、深さ d までの葉の総数が T よりも多い二分木が存在する
ことになってしまい矛盾が発生する。
よって、において、深さ d までの葉の総数は 2^d 個以下である。