作业帮怎样证明：一棵有n个叶子的哈夫曼树共有2n-1 个结点?
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/16 09:16:09
xR[NP݊`Inp- Bt(Cy (B 1@6sg.r N|)GYtmcUȗ3\9'0*z*t (6}AS+6z*h2.4 E ~JU3J,2 IDؼK-_-?Z9OҼǴ19h-}϶qltfQYl /a#[ha
eOY N,Z0gD}p@>G˹5!p4X= f eF /a3V3w}PhGErhz59XhO
@eq{WI@fƓDmQ Ej
怎样证明：一棵有n个叶子的哈夫曼树共有2n-1 个结点?
怎样证明：一棵有n个叶子的哈夫曼树共有2n-1 个结点?
怎样证明：一棵有n个叶子的哈夫曼树共有2n-1 个结点?
第1次必定是2个叶子组成二叉树,产生1新结点,接下来有2种情况：
1.此新结点与原剩下的叶子再组成二叉树又产生1新结点,这样就只有第1次时由2个叶子产生1新结点,以后每次由1叶子与新结点产生新结点,故n个叶子共有2n-1个结点.
2.剩下的叶子中又有2个叶子(比第1次产生的新结点权小)结合产生新结点,其它类似,那么必然会由2个都是新结点再产生新结点,所以实际上数量与第1种一样,共有2n-1个.
具体证明用一个构造哈夫曼树的算法.