设定权值的总数为N个,其哈夫曼树的结点总数是2n-1,不懂为什么?我想知道具体解法

10050 1年前 已收到1个回答 举报

凉心813 春芽

共回答了13个问题采纳率:92.3% 举报

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

1年前

4
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 16 q. 0.030 s. - webmaster@yulucn.com