数据结构（Java语言描述）（第2版）课件 4.5 哈夫曼树

数据结构主讲人：蒋卫祥常州信息职业技术学院4.5Huffman树引言IntroductionHuffmanTree，中文名是哈夫曼树或霍夫曼树，它是最优二叉树。哈夫曼树的应用很广，在不同的应用中叶子结点的值可以有不同的解释。当哈夫曼树应用到信息编码中，权值可看成是某个符号出现的频率：当应用到判定过程中，可看成是某类数据出现的频率；当应用到排序问题中，可看成是已排好次序而待合并的序列的长度等等。Part01Huffman树基本概念给定n个权值作为n个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树（HuffmanTree）。基本概念

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。

通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。路径和路径长度100和80的路径长度是1，50和30的路径长度是2，20和10的路径长度是3。哈夫曼树结点的权及带权路径长度哈夫曼树结点20的路径长度是3，它的带权路径长度=路径长度*权=3*20=60

若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。

结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。树的带权路径长度哈夫曼树树的WPL=1*100+2*50+3*20+3*10=100+100+60+30=290

树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。比较两棵二叉树WPL哈夫曼树右边树的WPL=1*100+2*50+3*20+3*10=290左边树的WPL=2*10+2*20+2*50+2*100=360Part02哈夫曼树的构造假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1、w2、…、wn，哈夫曼树的构造规则为：将w1、w2、…，wn看成是有n棵树的森林(每棵树仅有一个结点)；在森林中选出根结点权值最小的两棵树进行合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；从森林中删除选取的两棵树，并将新树加入森林；重复

、

步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。哈夫曼树的构造规则哈夫曼树的构造以{5,6,7,8,15}为例，来构造一棵哈夫曼树哈夫曼树的构造哈夫曼树构造实例步骤一哈夫曼树构造实例步骤二哈夫曼树构造实例步骤三以{5,6,7,8,15}为例，来构造一棵哈夫曼树哈夫曼树的构造哈夫曼树构造实例步骤四哈夫曼树构造实例步骤五创建哈夫曼树-算法实现哈夫曼树的构造算法实现//创建哈夫曼树public

voidcreateTree(){

//创建优先队列Queue<Node>q1=newPriorityQueue<Node>(

newComparator<Node>(){

public

intcompare(Nodeo1,Nodeo2){

return

o1.count-o2.count; }});

//将结点列表加入到队列中

q1.addAll(nodes);

//如果队列不为空

while(!q1.isEmpty()){

//出队一个结点 Noden1=q1.poll();

//出队一个结点 Noden2=q1.poll();

//通过两个结点创建父节点Nodeparent=newNode(n1,n2,n1.count+n2.count);

//如果队列为空

if(q1.isEmpty()){

root=parent;

return;}

//将父节点加入到队列中

q1.add(parent);}}Part03Huffman树的应用1.优化判断过程Huffman树的应用

将百分制转换成五级制的算法。显然，此算法很简单，只需利用if语句描述即可。

如果学生规模很大，该算法需反复多次执行，就应该考虑算法执行的时间问题。在实际应用中，学生的成绩呈正态分布，大部分在70~89分之间，优秀和不及格的概率较小。假设不及格、及格、中、良、优的百分比为5％、12%、40%、35%、8%，则上述算法80%以上的成绩需要进行三次或三次以上的比较才能得到结果。1.优化判断过程Huffman树的应用

若以这些百分比值5,12,40,35,8为权值，使用哈夫曼算法来构造一棵判定树，则得到的判定过程，可使多数成绩经过较少的比较即可得到结果。

未使用哈夫曼树判定

使用哈夫曼树判定2.哈夫曼编码Huffman树的应用

在数据通信中，需要将传送的文字转换成二进制的字符串，用0，1码的不同排列来表示字符。需传送的报文为“AFTER

DATA

EARAREARTAREA”，这里用到的字符集为“A，E，R，T，F，D”，各字母出现的次数为{8，4，5，3，1，1}，现要求为这些字母设计编码。要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别用000、001、010、011、100、101对“A，E，R，T，F，D”进行编码发送。算法分析在实际应用中，各个字符的出现频度或使用次数是不相同的，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。（非等长编码）设计时能够保证任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀，符合此要求的编码称为前缀编码。2.哈夫曼编码Huffman树的应用public

classTreeNode{ Characterch;//ch存储当前结点字符

int

val;

//若在构建二叉树的过程中该结点为左结点，则val=0,反之，val=1

int

freq;//存储字符出现的频次 TreeNodeleft;//左结点 TreeNoderight;//右结点

public

TreeNode(){

}

结点数据结构有参数构造方法publicTreeNode(Characterch,int

val,int

freq,TreeNodeleft,TreeNoderight){

this.ch=ch;

this.val=val;

this.freq=freq;

this.left=left;

this.right=right; }}2.哈夫曼编码Huffman树的应用初始化二叉树结点判断表空

选择最小频率的两个结点组成一颗二叉树2.哈夫曼编码Huffman树的应用选择最小频率的两个结点组成二叉树判断表空哈夫曼编码最终二叉树2.哈夫曼编码Huffman树的应用判断表空字符哈夫曼编码表使用哈夫曼编码的报文的最短传送长度为：

6

L=WPL=(wklk)=4×2+5×2+8×2+3×3+1×4+1×4=51

k=1若采用等长编码，报文的传送长度为：L=8×3+4×3+5×3+3×3+1×3+1×3=662.哈夫曼编码Huffman树的应用//遍历dataMap,初始化二叉树结点，并将所有初始化后的结点放到nodeList中，并进行排序LinkedList<TreeNode>nodeList=newLinkedList<TreeNode>();for(Map.Entry<Character,Integer>entry:dataMap.entrySet()){ Characterch=entry.getKey();

int

freq=entry.getValue();

int

val=0; TreeNodetmp=newTreeNode(ch,val,freq,null,null);

odeList.add(tmp);}//对存放结点的链表进行排序，方便后续进行组合Collections.sort(nodeList,newComparator<TreeNode>(){

public

intcompare(TreeNodet1,TreeNodet2){

return

t1.freq-t2.freq; } });while(nodeList.size()>0){TreeNodet1=nodeList.removeFirst();TreeNodet2=nodeList.removeFirst();

//左子树的val赋值为0，右子树的val赋值为1

t1.val=0;

t2.val=1;

//将取出的两个结点进行合并

if(nodeList.size()==0){//此时代表所有结点合并完毕，返回结果

root=newTreeNode(null,0,t1.freq+t2.freq,t1,t2);}else{

//此时代表还有可以合并的结点TreeNodetmp=newTreeNode(null,0,t1.freq+t2.freq,t1,t2);

if(tmp.freq>nodeList.getLast().freq){

nodeList.addLast(tmp); }else{ for(int

i=0;i<nodeList.size();i++){

int

tmpFreq=tmp.freq;

if(tmpFreq<=nodeList.get(i).freq){

nodeList.add(i,tmp);

break; }