哈夫曼树的定义?如何构造?
• 给定一组数值作为叶子结点的权值构造一棵二叉树,若满足所有叶子结点到根结点的带权路径长度之和最小,即为哈夫曼树
• 长度称为WPL带权路径长度
• 给定n个权值,构成n棵二叉树的集合
• 从集合中选出两棵根结点权值最小的二叉树,作为左右子树,构成新二叉树,权值为两子树根结点权值之和
• 放入集合,删除原来的两棵树
• 重复,直到集合只剩下一棵二叉树
• 统计文件中字符出现的次数
• 用(1)中的统计结果来构造haffman树
• 根据haffman树生成haffman编码
• 将源文件用对应的haffman 编码替换(源文件一共有10个字符,占10字节的内存,但是经过用haffman code替换之后,只占3个字节,这样就能达到压缩的目的)
• 按序将编码输入到哈夫曼树,到叶子结点还原