??作者简介：大家好呀！我是，大家可以叫我叶子哦！
??个人主页：【的博客】
??博主信息：四季轮换叶，一路招摇胜！
专栏【安利Java零基础】
【数据结构-Java语言描述】
??希望大家多多支持??一起进步呀！~
??若有帮助，还请【关注点赞收藏】，不行的话我再努力努力呀！??
————————————————
版权声明：本文由【】原创、在CSDN首发、需要转载请联系博主。
??想寻找共同成长的小伙伴，请点击【Java全栈开发社区】
目录
前言
” />概念1：什么是路径？
??? 概念2：什么是路径长度？
???概念3：什么是结点的权？
???概念4：什么是结点的带权路径长度？
???概念5：什么是 树的带权路径长度？
??最优二叉树（哈夫曼树）
??构建哈夫曼树
??哈夫曼编码
??哈夫曼编码类【算法实现】
前言
概念1：什么是路径？
在一棵树中，从一个结点到另一个结点所经过的所有结点，被我们称为两个结点之间的路径。
概念2：什么是路径长度？
在一棵树中，从一个结点到另一个结点所经过的**“边”的数量**，被我们称为两个结点之间的路径长度。
概念3：什么是结点的权？
在实际应用中，人们往往会给树中的每一个结点赋予一个具有某种实际意义的数值，这个数值被称为该结点的权值。
概念4：什么是结点的带权路径长度？
树的每一个结点，都可以拥有自己的**“权重”**（Weight），权重在不同的算法当中可以起到不同的作用。
结点的带权路径长度，是指树的根结点到该结点的路径长度与该结点的权值的乘积。
概念5：什么是 树的带权路径长度？
在一棵树中，所有叶子结点的带权路径长度之和，被称为树的带权路径长度，也被简称为WPL。
哈夫曼树是由麻省理工学院的哈夫曼博士于1952年发明，这到底是一颗什么样的树呢？
刚才我们学习了树的带权路径长度（WPL），而哈夫曼树（Huffman Tree）是在叶子结点和权重确定的情况下，带权路径长度最小的二叉树，也被称为最优二叉树。
” />- 同一组数据的最优二叉树不唯一，因为没有限定左右子树，并且有权值重复时，可能树的高度都不唯一，唯一的只是带权路径长度之和最小。 构建哈夫曼树的时候即可以推导出。
??构建哈夫曼树
(1) 由已知给定的n个权值{w1,w2,w3,…,wn}，构建一个有n棵二叉树所构建的森林
F={T1,T2,T3,…Tn}，其中每一棵二叉树中只含一个带权值为wi根节点，其左、右子树为空
(2) 在二叉树森林F中选取根节点的权值最小和次小的两棵二叉树，分别把它们作为左子树和右子树
去构建一颗新二叉树，新二叉树的根节点权值为其左右子树根节点的权值之和。
(3) 作为新二叉树的左右子树的这两棵二叉树从森林F中删除，同时加入刚生成的新二叉树
(4) 重复步骤(2)和(3)，直到森林F中只剩一颗二叉树为止，该二叉树就是哈夫曼树。
练习：
有5个带权结点 {A,B,C,D,E}，其权值分别为W={10,30,40,15,6}，权值作为结点数据，绘制一颗哈夫曼 。
” />
哈夫曼树进行译码
哈夫曼编码是一种前缀码，任何一个字符的编码都不是同一个字符集中另一个字符的编码的前缀。
译码过程是编码过程的逆过程。从哈夫曼树的根开始，从左到右把二进制编码的每一位进行判别，若遇到0，则选择左分支走向下一个结点；若遇到1，则选择右分支走向下一个结点，直至到达一个树叶结点，便求得响应字符。
练习：
有5个带权结点 {A,B,C,D,E}，其权值分别为W={10,30,40,15,6}，权值作为结点数据，绘制一颗哈夫曼，并编写哈夫曼编码。
A：1111
B：10
C：0
D：110
E：1110
编码：编码字符串 AABBEDCC–>111111111010111011000
” />
测试类 ：
public class Demo02 {public static void main(String[] args) {// 一组权值int[] W = {6,30,8,9,15,24,4,12};// 创建哈夫曼树HuffmanTree tree = new HuffmanTree();// 求哈夫曼编码int[][] HN = tree.huffmanCoding(W);//打印编码System.out.println("哈夫曼编码是： ");for (int i = 0; i < HN.length; i++) {System.out.print(W[i]+" ");for (int j = 0; j < HN[i].length; j++) {if(HN[i][j] == -1){for (int k = j+1; k <HN[i].length ; k++) {System.out.print(HN[i][k]);}break;}}System.out.println();}}}如果文章对您有帮助，就拿起小手赶紧给博主点赞??评论收藏?? 一下吧！
想要了解更多吗？没时间解释了，快来点一点！
的博客_CSDN博客-数据结构,安利Java零基础,spring领域博主擅长数据结构,安利Java零基础,spring,等方面的知识[这里是图片019]https://blog.csdn.net/zsy3757486?spm=1000.2115.3001.5343