怎样证明:一棵有n个叶子的哈夫曼树共有2n-1 个结点?
来源:学生作业帮助网 编辑:作业帮 时间:2024/08/12 07:46:39
![怎样证明:一棵有n个叶子的哈夫曼树共有2n-1 个结点?](/uploads/image/z/8461566-54-6.jpg?t=%E6%80%8E%E6%A0%B7%E8%AF%81%E6%98%8E%EF%BC%9A%E4%B8%80%E6%A3%B5%E6%9C%89n%E4%B8%AA%E5%8F%B6%E5%AD%90%E7%9A%84%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91%E5%85%B1%E6%9C%892n-1+%E4%B8%AA%E7%BB%93%E7%82%B9%3F)
xR[NP݊`Inp- Bt(Cy (B1@6sg.rN|)GYtmcUȗ3\9'0*z*t(6}AS+6z*h2.4E~JU3J,2IDؼ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个.
具体证明用一个构造哈夫曼树的算法.