题目

怎样证明：一棵有n个叶子的哈夫曼树共有2n-1 个结点?

提问时间：2021-03-21

答案

第1次必定是2个叶子组成二叉树,产生1新结点,接下来有2种情况：
1.此新结点与原剩下的叶子再组成二叉树又产生1新结点,这样就只有第1次时由2个叶子产生1新结点,以后每次由1叶子与新结点产生新结点,故n个叶子共有2n-1个结点.
2.剩下的叶子中又有2个叶子(比第1次产生的新结点权小)结合产生新结点,其它类似,那么必然会由2个都是新结点再产生新结点,所以实际上数量与第1种一样,共有2n-1个.
具体证明用一个构造哈夫曼树的算法.