哈弗曼树实现Word下载.docx

1、为了直观其见，在图中把带权的叶子结点画成方形，其他非叶子结点仍为圆形。请看图 中的三棵二叉树以及它们的带权路径长。a） wpl=38 （b） wpl=49 （c） wpl=36这三棵二叉树叶子结点数相同，它们的权值也相同，但是它们的 wpl 带权路径长各不相同。图 6.21（c）wpl 最小。它就是哈曼树，最优树。哈夫曼树是，在具有同一组权值的叶子结点的不同二叉树中，带权路径长度最短的树。也称最优树。2. 哈夫曼树的构造构造哈夫曼树的方法（贪婪方法）上图是是哈夫曼树构造过程图（a） 是一个拥有 4 棵小树的森林，图（b） 森林中还有 3 子棵树，图（c） 森林中剩下 2 棵树，图（d） 森林只

2、有一棵树，这棵树就是哈夫曼树。这里或许会提出疑问， n 个叶子构成的哈夫曼树其带权路径长度唯一吗？确实唯一。树形唯一吗？不唯一。因为将森林中两棵权值最小和次小的子棵合并时，哪棵做左子树，哪棵做右子树并不严格限制。图之中的做法是把权值较小的当做左子树 , 权值较大的当做右子树。如果反过来也可以，画出的树形有所不同，但 WPL 值相同。为了便于讨论交流在此提倡权值较小的做左子树 , 权值较大的做右子。3. 哈夫曼树的应用（1） 用于最佳判断过程。（上面已提到）（2） 用于通信编码 在通信及数据传输中多采用二进制编码。为了使电文尽可能的缩短，可以对电文中每个字符出现的次数进行统计。设法让出现次数多的

3、字符的二进制码短些，而让那些很少出现的字符的二进制码长一些。假设有一段电文，其中用到 4 个不同字符，它们在电文中出现的次数分别为 7 ， 2 ， 4 ， 5 。把 7 ， 2 ， 4 ， 5 当做 4 个叶子的权值构造哈夫曼树如图所示。在树中令所有左分支取编码为 0 ，令所有右分支取编码为1。将从根结点起到某个叶子结点路径上的各左、右分支的编码顺序排列，就得这个叶子结点所代表的字符的二进制编码，如图所示。这些编码拼成的电文不会混淆，因为每个字符的编码均不是其他编码的前缀，这种编码称做前缀编码。 关于信息编码是一个复杂的问题，还应考虑其他一些因素。比如前缀编码每个编码的长度不相等，译码时较困难

4、。还有检测、纠错问题都应考虑在内。这里仅对哈夫曼树举了一个应用实例。4、哈夫曼树的JAVA实现哈夫曼树节点:public class Node implements Comparable Node private T data; private double weight; private String coding = ;/此节点的哈夫曼编码 private Node left; right; public Node（T data, double weight） this.data = data; this.weight = weight; public T getData（） return

5、 data; public void setData（T data） public double getWeight（） return weight; public void setWeight（double weight） public Node getLeft（） return left; public void setLeft（Node left） this.left = left; getRight（） return right; public void setRight（Node right） this.right = right; public String getCoding（）

6、 return coding; public void setCoding（String coding） this.coding = coding; Override public String toString（） return data:+this.data+weight:+this.weight+Coding:+this.coding; public int compareTo（Node this.getWeight（） return 1; if（other.getWeight（） return -1; return 0;/构造哈夫曼树的类import java.util.ArrayDe

7、que;import java.util.ArrayList;import java.util.Collections;import java.util.List;import java.util.Queue;public class HuffmanTree/创建哈夫曼树 public static createTree（List 1） Collections.sort（nodes）; left = nodes.get（nodes.size（）-1）; right = nodes.get（nodes.size（）-2）; parent = new Node（null, left.getWeig

8、ht（）+right.getWeight（）; parent.setLeft（left）; parent.setRight（right）; nodes.remove（left）; nodes.remove（right）; nodes.add（parent）; return nodes.get（0）; /递归生成Huffman编码 public static void generateHuffmanCode（Node root） if （root=null） return; if（root.getLeft（）!=null） root.getLeft（）.setCoding（root.getCod

9、ing（）+0 if（root.getRight（）! root.getRight（）.setCoding（root.getCoding（）+1 generateHuffmanCode（root.getLeft（）; generateHuffmanCode（root.getRight（）; List breadth（Node root） /广度优先遍历哈夫曼树 list = new ArrayList（）; Queue queue = new ArrayDeque list.add（new Node（A,7）;T,5）;S,4）;C,2）; root = HuffmanTree.createT

10、ree（list）; HuffmanTree.generateHuffmanCode（root）; System.out.println（HuffmanTree.breadth（root）; /测试2 int a=5,24,7,17,34,5,13; String s=,BDEFG; list1 = new ArrayList for（int i=0;i a.length;i+） list1.add（new Node（si,ai）; root = HuffmanTree.createTree（list1）; list2=HuffmanTree.breadth（root）; for（Node n

11、ode: list2） System.out.println（node）;5、哈夫曼树的C+实现/*1、问题描述给定n个字符及其对应的权值，构造Huffman树，并进行huffman编码和译（解）码。构造Huffman树时，要求左子树根的权值小于右子树根的权值。进行Huffman编码时，假定Huffman树的左分支上编码为0，右分支上编码为1。2、算法 构造Huffman树算法：、根据给定的n个权值（w1, w2, , wn）构成n棵二叉树的集合F=T1, T2, , Tn，其中每棵二叉树Ti中只有一个权值为wi的根结点、在F中选取两棵根结点的权值最小的树，作为左、右子树构造一棵新的二叉树，且

12、置其根结点的权值为其左、右子树权值之和、在F中删除这两棵树，同时将新得到的二叉树加入F中、重复, ，直到F只含一棵树为止Huffman编码算法：、从Huffman树的每一个叶子结点开始、依次沿结点到根的路径，判断该结点是父亲结点的左孩子还是右孩子，如果是左孩子则得到编码0，否则得到编码1，先得到的编码放在后面、直到到达根结点，编码序列即为该叶子结点对应的Huffman编码Huffman译（解）码算法：、指针指向Huffman树的根结点，取第一个Huffman码、如果Huffman码为0，将指针指向当前结点的左子树的根结点；如果Huffman码为1，将指针指向当前结点的右子树的根结点、如果指针指

13、向的当前结点为叶子结点，则输出叶子结点对应的字符；否则，取下一个Huffman码，并返回、如果Huffman码序列未结束，则返回继续译码Input第一行：样本字符个数，假设为n。第二行，n个字符（用空格隔开）第三行，n个字符对应的权值（用空格隔开）第四行，待编码的字符串第五行，待译码的Huffman码序列Output第一行，每个字符对应的Huffman编码（用空格隔开）第二行，字符串对应的Huffman编码序列第三行，Huffman码序列对应的字符串Sample Input4a b c d9 3 2 6abcd111001010Sample Output0 101 100 1101011001

14、1dcba*/#includestringcstringusing namespace std;const int MaxW = 9999;/假设权值不超过9999/定义hufffman树节点类class HuffNodepublic: int weight; int parent; int leftchild; int rightchild; char data;/定义哈夫曼树类class HuffManprivate: void MakeTree（）;/建树，私有函数，被公有函数调用 void SelectMin（int pos,int *s1,int *s2）;/从1到pos找出权值最小

15、的两个节点，把下标存在s1,s2中 int len;/节点数量 int lnum;/叶子数量 HuffNode *huffTree;/哈夫曼树，用数组表示 string *huffCode;/每个字符对应的哈夫曼编码 void MakeTree（int n,int wt,char c）;/公有函数，被主函数调用 void Codeing（）; void CCodeing（string c2）;/编码，公有函数，被主函数调用 void CCCodeing（string c3）;/译码，公有函数，被主函数调用 void Destroy（）;/构建huffman树void HuffMan:MakeT

16、ree（int n,int wt,char c）/参数是叶子节点数量和叶子权值 int i; lnum = n; len = 2*n-1; huffTree = new HuffNode2*n; huffCode = new stringlnum+1;/位置从1开始计算 /hunffCode实质是个二维字符数组，第i行表示第i个字符对应的编码 /哈夫曼树初始化 for（i=1;=n; huffTreei.data = ci-1;/第0号不用，从1开始编号 huffTreei.weight = wti-1;=len; if（in） huffTreei.weight = 0;/前n个节点是叶子，已

17、经设值 huffTreei.parent = 0; huffTreei.leftchild = 0; huffTreei.rightchild = 0; MakeTree（）;/调用私有函数建树SelectMin（int pos,int *s1,int *s2）/找出最小的两个权值的下标/函数采用地址传递的方法，找出的两个下标保存在s1和s2中 int w1,w2,i; w1 = w2 = MaxW; *s1 = *s2 = 0;=pos; /如果第i节点的权值小于w1，且第i节点是未选择的节点（父亲为0） /把w1和s1保存到w2和s2，即原来的第一最小值变成第二最小值 /把第i个节点的权值

18、和下标保存到w1和s1，作为第一最小值 /else 如果第i节点的权值小于w2，且第i节点是未选择的节点 /把第i节点的权值和下标保存到w2和s2，作为第二最小值 if（huffTreei.weightw1&huffTreei.parent=0） w2=w1; *s2=*s1; w1=huffTreei.weight; *s1=i; else if（huffTreei.weightw2& w2=huffTreei.weight; *s2=i; MakeTree（） /私有函数，被公有函数调用 int i,s1,s2; /构造哈夫曼树HuffTree的n-1个非叶节点 for（i=lnum+1;

19、 SelectMin（i-1,&s1,&s2）; /将找出的两颗权值最小的子树合并为一棵树，过程包括 /节点s1和s2的父亲设为i /节点i的左右孩子分别设为s1和s2 /节点i的权值等于s1和s2的权值和 huffTrees1.parent=i; huffTrees2.parent=i; huffTreei.leftchild=s1; huffTreei.rightchild=s2; huffTreei.weight=huffTrees1.weight+huffTrees2.weight;/销毁哈夫曼树Destroy（） len = 0; lnum = 0; delete huffTree;

20、 delete huffCode;/哈夫曼编码Codeing（） char *cd; int i,c,f,start; /求n个叶节点的哈夫曼编码 cd = new charlnum; /分配求编码的工作空间 cdlnum-1 = 0=lnum;+i）/逐个字符求哈夫曼编码 start = lnum-2;/编码结束符位置 /参考课本p147的第2个for循环代码 /. c=i; while（huffTreec.parent!=0） f=huffTreec.parent; if（huffTreef.leftchild=c） cdstart=0 else if（huffTreef.rightchild=c）1 start-; c=f; huffCodei.assign（&cdstart+1）;/把cd中从start到末尾的编码复制到huffCode delete cd;/释放工作空间CCodeing（string c2） int i,j; for（i=0;c2.length（）; for（j=1;jj+） if（c2i=huffTreej.data） couthuffCodej;CCCodeing（string c2） int i,j=2*lnum-1; if（c2i=） j=huffTreej.l