基本介绍给定n个权值作为n个叶子节点，构造一棵二叉树，若树的加权路径长度（wpl）达到最小值，则为这样一棵二叉树称为最优二叉树，也称为哈夫曼树，有的书上翻译成哈夫曼树。哈夫曼树是加权路径长度最短的树，权值较大的节点离根节点很近。几个重要的概念**路径和路径长度：**在一个树种中，从一个节点向下可以到达的子节点或孙节点之间的路径称为路径。路径中的分支数称为路径长度。若指定根节点的层数为1，则根节点到L层节点的路径长度为：L-1。**节点的权重和加权的路径长度：**如果树型的节点分配给一个具有一定值的节点，这个值就称为该节点的权重。节点的加权路径长度为：从根节点到节点的路径长度与节点权重的乘积。树的加权路径长度：树的加权路径长度定义为所有叶节点的加权路径长度之和，即WPL（weightedpathlength）。权重值越大的节点离根节点越近。最优二叉树。WPL最小的就是哈夫曼树wpl=59就是哈夫曼树哈夫曼树的创建思路给定一个序列{13,7,8,3,29,6,1}，需要将其转化为哈夫曼树这棵树从小到大排序，每条数据看成一个节点，每个节点可以看成最简单的二叉树。取出根节点权重最小的两棵二叉树。形成一棵新的二叉树，新二叉树根节点的权值是前两棵二叉树根节点权值之和。然后根据根节点的权值对新的二叉树进行排序，重复1-2-3-4的步骤，直到处理完序列中的所有数据，得到一棵哈夫曼树。如下图所示：代码示例packagecom.xie.huffmantree;importjava.util.ArrayList;importjava.util.Collections;importjava.util.List;publicclassHuffmanTree{publicstaticvoidmain(String[]args){int[]arr={13,7,8,3,29,6,1};NodehuffmanTree=createHuffmanTree(arr);//前序遍历preOrder(huffmanTree);/***Node{value=67}*Node{value=29}*Node{值=38}*节点{值=15}*节点{值=7}*节点{值=8}*节点{值=23}*节点{值=10}*节点{值=4}*节点{值=1}*Node{value=3}*Node{value=6}*Node{value=13}*/}//创建哈夫曼树publicstaticNodecreateHuffmanTree(int[]arr){//第一步是为了方便操作//1。遍历arr数组//2.将arr的每个元素构造成一个Node//3。将Node放入ArrayListListnodes=newArrayList<>();for(intvalue:arr){nodes.add(newNode(value));}while(nodes.size()>1){//从小到大排序Collections.sort(nodes);System.out.println("nodes="+nodes);//取出根节点权值最小的两棵二叉树//(1)取出权值最小的节点(二叉树)NodeleftNode=nodes.get(0);//(2)取出次小的节点weight(binarytree)NoderightNode=nodes.get(1);//(3)新建一棵二叉树Nodeparent=newNode(leftNode.value+rightNode.value);parent.left=leftNode;parent.roght=rightNode;//(4)从ArrayList中删除处理后的二叉树nodes.remove(leftNode);nodes.remove(rightNode);//(5)添加父节点nodes.add(parent);}//返回哈夫曼树的根节点returnnodes.get(0);}publicstaticvoidpreOrder(Nodenode){if(node!=null){node.preOrder();}else{System.out.println("为空树不能遍历~~");}}}//创建节点类，为了让Node对象支持排序，实现Comparble接口classNodeimplementsComparable{//weightintvalue;//指向左边childnodeNodeleft;//指向右子节点Noderoght;//写一个前序遍历publicvoidpreOrder(){System.out.println(this);if(this.left!=null){this.left.preOrder();}if(this.roght!=null){this.roght.preOrder();}}publicNode(intvalue){this.value=value;}@OverridepublicStringtoString(){return"Node{"+"value="+value+'}';}@OverridepublicintcompareTo(Nodeo){//从小到大排序returnthis.value-o.value;}}【小编推荐】和妹子聊Java16的新特性，好甜！IT项目太多，太难管理？不！因为你还没有学会这七招。学习Python五年，这些网站让我认识了最近。快来一起体验吧。Java都到了16了，你怎么还在用8？是不是越来越糟了？太奇妙了！Windows10的这些黑科技功能你都用过吗？
