java哈夫曼树编码_哈夫曼树的编码实验

65 阅读 0 评论 43 点赞

我是靠谱客的博主无语自行车，最近开发中收集的这篇文章主要介绍java哈夫曼树编码_哈夫曼树的编码实验，觉得挺不错的，现在分享给大家，希望可以做个参考。

Java哈夫曼编码实验--哈夫曼树的建立，编码与解码

建树，造树，编码，解码

一、哈夫曼树编码介绍

1、哈夫曼树：

(1)定义：假设有n个权值{w1, w2, ..., wn}，试构造一棵含有n个叶子结点的二叉树，每个叶子节点带权威wi，则其中带权路径长度WPL最小的二叉树叫做最优二叉树或者哈夫曼树。

(2)特点：哈夫曼树中没有度为1的结点，故由n0 = n2+1以及m= n0+n1+n2，n1=0可推出m=2*n0-1，即一棵有n个叶子节点的哈夫曼树共有2n-1个节点。

2、哈夫曼编码步骤：

(1)计算字符出现的次数：

假设我们现在有一段文档需要进行编码，我们现在需要对于每一个字符出现的次数进行统计，然后分别计算出其在这篇文档的权重，也就是频率，我们用下面的一段文字进行举例；

在如下的文档中包括的字符有8个字母和2个空格，所以我们现在需要去统计这10个字符的个数，统计后的数据如下：

(2)对字符出现的次数作为一个权重，从小到大进行排序；

排序结果：0.1,0.1,0.1,0.1,0.1,0.1,0.2,0.2

(3)依照排序结果从小到大根据以下规则进行造树：

a、最小的前两个数进行权重的相加，形成他们两个作为左子树和右子树的父结点，如果是左结点就标记为0，如果是右结点就标记为1

b、然后将父结点作为一个新的结点进入排序结果，之后进行重新排序(ps：假如出

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。