Java版哈夫曼树

PS：本文为转载文章，原文可读性会更好，文末有原文链接哈夫曼树的重要概念1，3哈夫曼树的创建思路1,4哈夫曼树的代码实现1,哈夫曼树1,1哈夫曼树基本介绍给定n个权重为n如果树的加权路径长度（wpl）达到最小值，这样一棵二叉树为称为最优二叉树，也称为霍夫曼树；一棵哈夫曼树是一种带权路径长度的最短树，权值越大的节点离根越近。“权重”、“树的加权路径长度”和“哈夫曼树是加权路径长度最短的树，权重越大的节点越靠近根”这三句话好像看不懂？没关系，我们先保留悬念，下面再进行分析。1.2哈夫曼树的重要概念为了更好的说明这些概念，我们先画一棵普通的二叉树，如图1所示：图片路径：在一棵树中，可以从一个节点向下到达子节点或孙节点之间的路径的;例如，图1中节点2到节点8的路径为2->4->8。路径长度：路径中的分支数。若指定根节点的层数为1，则根节点到L层节点的路径长度为L-1；例如8个节点所在的层为第4层，则8个节点的路径长度为4-1。节点的权重：给树中的节点赋一个具有一定意义的值，这个值称为节点的权重；例如9节点的值为9，则该节点的权重为9。例如9个节点的加权路径长度等于3（4-1）乘以9。树的加权路径长度：所有叶节点的加权路径长度之和，记为WPL（加权路径长度）;例如，图1中树的加权路径长度为8个节点、9个节点、5个节点、6个节点和7个节点的加权路径长度之和。哈夫曼树：是一棵WPL最小的二叉树，即树的加权路径长度最小。1,3哈夫曼树的创建思路假设我们有一个序列arr={13,7,8,3,29,6,2}，将这个序列转化为哈夫曼树，应该怎么做呢？好，我们来分析创建哈夫曼树的步骤：(1)将序列从小到大排序，把每个数看成一个节点，每个节点看成最简单的树。二叉树。(2)取出根节点权值最小的两棵二叉树，组成一棵新的二叉树。新二叉树根节点的权值是前两棵二叉树根节点权值之和。(3)如果组装完这棵新二叉树后没有其他树，则不执行步骤(4)就得到一棵霍夫曼树。(4)如果合并这棵新二叉树后还有其他树，则将这棵新二叉树的根节点的权值和其他根节点的权值合并成一个序列，然后返回(1)。结合哈夫曼树的创建步骤，我们可以将arr={13,7,8,3,29,6,2}转化为哈夫曼树。图（1）看图2，我们把arr={13,7,8,3,29,6,2}的数组从小到大排序并转为根节点，然后从最小的两个开始roots节点（2-node和3-node）组合成一棵二叉树，得到如图3所示的多棵二叉树。图中注意：白色数字节点是从arr数组中获取的，红色数字节点是组合形成的新节点。下面的图也有相同的描述。(2)看图3，用根节点2和根节点3组成一棵新的二叉树，并把节点5作为它们的根节点（新二叉树根节点的权值就是根节点的权值前两棵二叉树的值），然后得到一个新的序列并从小到大排序arr={5,6,7,8,13,29}，从arr序列中选出最小的2个根节点到形成一棵二叉树，并得到如图4所示的多棵二叉树。图（3）看图4，用根节点5和根节点6组成一棵新的二叉树，并用11个节点作为它们的根节点（新二叉树根节点的权值是前两棵二叉树根节点权值之和），然后得到一个新的序列，从小到大排序arr={7,8,11,13,29},并从arr序列中选出最小的2个根节点组成一棵二叉树，并得到多棵二叉树如图5所示。图片(4)看图5，用根节点7和根节点8来形成一棵新的二叉树，并以节点15作为它们的根节点（新的二叉树根节点的权值是前两棵二叉树根节点权值的总和），然后得到一个新的序列和从小到大排列arr={11,13,15,29}，从arr序列中选出最小的2个根节点组成一棵二叉树，得到如图6所示的多棵二叉树。图（5）看图6，用根节点11和根节点13组成一棵新的二叉树，用24个节点作为它们的根节点（新二叉树的根节点的权值是新二叉树的根节点）前两棵二叉树的权值之和），然后得到一个新的序列并从小到大排序arr={15,24,29}，从arr序列中选出最小的2个根节点组成二叉树，得到如图7所示的多棵二叉树。图（6）看图7，用根节点15和根节点24组成一棵新的二叉树，并把节点39作为它们的根节点（新二叉树的根节点的权值是新二叉树的根节点）前两棵二叉树的权值之和），然后得到一个新的序列并从小到大排序arr={29,39}，从arr序列中选出最小的2个根节点组成一棵二叉树，以及得到如图8所示的二叉树。图片到这里，一开始用序列arr={13,7,8,3,29,6,2}创建的哈夫曼树已经完成；“权重越大的节点越靠近根”怎么理解这句话呢？以图8中的哈夫曼树为例。第39个节点是否比第15个节点更重要？第39个节点比第15个节点更接近根节点68吗？这次我明白了。1.4哈夫曼树的代码实现了图8的二叉树，中序遍历的结果为：29687158392531162413中序遍历的文章可以看Java版的数据结构和算法（4），好了，现在我们用代码来实现，创建序列为arr={13,7,8,3,29,6,2}的哈夫曼树。（1）创建节点类Node：/**NodeimplementsComparable让Node对象连续排序Collections集合排序*/publicclassNodeimplementsComparable{privateintvalue;私有节点离开；私有节点权；publicNode(intvalue){super();this.value=value;}publicintgetValue(){returnvalue;}publicNodegetLeft(){returnleft;}publicvoidsetLeft(Nodeleft){this.left=左边;}publicNodegetRight(){returnright;}publicvoidsetRight(Noderight){this.right=right;}@OverridepublicintcompareTo(Nodearg0){returnthis.value-arg0.value;}@OverridepublicStringtoString(){return"Node[value="+value+"]";}}(2)创建构造哈夫曼树的类Test：publicclassTest{Noderoot;publicstaticvoidmain(String[]args){int[]arr={13,7,8,3,29,6,2};测试测试=新测试（）；测试。**建立一个霍夫曼树@paramarr*/privateNodecreateHuffmanTree(int[]arr){Listlist=newArrayList();for(inti=0;i1){//排序，从小到大Collections.sort(list);//System.out.println("list="+list);/***这必须是权重最小的节点*/NodeminNode=list.get(0);/***除minNode节点外，该节点为权重最小的节点，但该节点大于minNode节点，小于其他节点*/NodesecondMinNode=list.get(1);/***构建一个新的二叉树*/NodeparentNode=newNode(minNode.getValue()+secondMinNode.getValue());parentNode.setLeft(minNode);parentNode.setRight(secondMinNode);/***从list集合中删除2个已经构建成二叉树的节点*/list.remove(minNode);list.remove(secondMinNode);/***改变新的二叉树的父节点，将节点添加到列表集合中*/list.add(parentNode);}/***构建哈夫曼树后，列表集合中的第一个节点必须是根节点节点，除非该方法传入的数组arr为Empty*/returnlist.get(0);}//中序遍历privatevoidmidOrder(){if(root!=null){System.out.println("Inorder二叉树的遍历~~");midOrder(root);}else{System.out.println("Thisisanemptytree");}}publicvoidmidOrder(Nodenode){//递归对左子树进行前序遍历if(node.getLeft()!=null){midOrder(node.getLeft());}//输出当前节点System.out.println(node);//递归对右子树进行前序遍历if(node.getRight()!=null){midOrder(node.getRight());}}}程序运行如下：如果看到如图，构造完哈夫曼树之后，我们再对哈夫曼树进行中序遍历，得到的结果和图8中二叉树中序遍历的结果是一样的