２分木

質問

２分木で内点の数を q としたときに根から全ての葉まで
の路長の和は根から全ての内点までの路長の和＋２q で
あるということを示したいのですが、方針が立たないので
どなたかヒントをください。

回答No.1

gakutensoku

まず、「2分木」の定義を確認する必要があると思います。

私が通常考える2分木の定義ですと、
根―○―○―○―○―○―葉
という形状のものも2分木になりますが、上記の命題は
成り立ちません。

私の考えている2分木の定義よりも、bitofblueさんが用いられている定義の方がより厳しい条件となっているのではないでしょうか?

たとえば、「全ての内点は必ず2個の子(内点または葉)を持つ」などと言った条件は含まれていませんか?

bitofblueさんが用いられている定義を提示していただければ幸いです。