哈夫曼树是给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
为封丘等地区用户提供了全套网页设计制作服务，及封丘网站建设行业解决方案。主营业务为网站设计制作、做网站、封丘网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！
例子：
1、将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
2、 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
3、从森林中删除选取的两棵树，并将新树加入森林；
4、重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
扩展资料：
按照哈夫曼编码构思程序流程：
1、切割的顺序是从上往下，直至数组中的元素全部出现在叶节点；
2、我们思路正好相反，从数组中找出最小的两个元素作为最下面的叶节点，在向备选数组中存入这两个叶节点的和（这个新的和加入累加运算，这个和也就是所求的最小值的一部分，原因如上图）。
3、以本题为例，备选数组中现有元素为{30，30}，再次取出两个最小元素进行求和，得到新的元素，回归备选数组并记入累加。
4、上述2.3布重复执行直至备选数组中只有一个元素，此时累加结束，返回累加值即可
5、求数组中的最小值，可以用小根堆进行提取最为方便；此题用到了贪心的思路，即用相同的策略重复执行，直至我们得到所需的结果。
参考资料来源:百度百科——哈夫曼树
1）编写函数实现选择parent为0且权值最小的两个根结点的算法
2）编写函数实现统计字符串中字符的种类以及各类字符的个数。
3）编写函数构造赫夫曼树。
4）编写函数实现由赫夫曼树求赫夫曼编码表。
5）编写函数实现将正文转换为相应的编码文件。
6）编写函数实现将编码文件进行译码。
7）编写主控函数，完成本实验的功能。
class HaffmanNode //哈夫曼树的结点类
{
int weight; //权值
int parent,left,right; //父母结点和左右孩子下标
public HaffmanNode(int weight)
{
this.weight = weight;
this.parent=-1;
this.left=-1;
this.right=-1;
}
public HaffmanNode()
{
this(0);
}
public String toString()
{
return this.weight+", "+this.parent+", "+this.left+", "+this.right;
}
return code;
}
public static void main(String[] args)
{
int[] weight={5,29,7,8,14,23,3,11}; //指定权值集合
HaffmanTree htree = new HaffmanTree(weight);
System.out.println("哈夫曼树的结点数组:\n"+htree.toString());
String[] code = htree.haffmanCode();
System.out.println("哈夫曼编码:");
for (int i=0; icode.length; i++)
System.out.println(code[i]);
}
}
哈夫曼树和字符编码对应你都弄完了，得到是如a :01 b :101对应关系，通过这个关系直接将像“asdsdfdfg”直接转换为“01110101”这样二进制编码。译码的时候，读取二进制编码，先读取一位，然后在关系表中查找该二进制数对应的字符，如果没有找到，继续读取二位，然后继续在关系表中查找该二位二进制对应的字符。如此循环，知道找到字符位置，然后将二进制数替换为相应的字符，知道所有的数都替换完为止。
