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

Question

如题所述

Answer 1

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

Answer 2

设叶子节点个数为n，度为1的节点个数为m，度为2的节点个数为l.
显然易知：一颗二叉树的节点数 ＝ 这个树的度加1（因为每个节点都是前一个节点的度，根节点除外，所以要加1）
故有 l + m + n = 2l + m + 1
----> n = l + 1
由于哈夫曼树没有度为1的节点，在m ＝ 0
总节点 ＝ n ＋ m ＋ l ＝ 2n － 1

Answer 3

叶子节点就是出度为0的点，哈弗曼树结点有出度为0，2的点，设为n0，n2
每个节点（除了根）都有入度1，总入度e1=n0+n2-1
总出度e2=2n2,
出度=入度，由题意，n0=n，所求n0+n2
联立求解2n2=n0+n2-1 n2=n0-1=n-1
得 n0+n2=2n-1
得证。