数据结构第六章哈夫曼树

6.6Huffman树及其应用王玲教学内容《数据结构》远程通信中的一个问题1最优二叉树——Huffman树2Huffman编码及其实现3《数据结构》远程通信中的一个问题设有一段信息（报文）需要编码传输：CASTCASTSATEATATASA信道发送端（编码）对接收端（解码）001000011100001000011100011000…CASTCASTSATEATATASA解决方案1

等长编码：CASTCASTSATEATATASA

A:000,C:001,E:010,S:011,T:100信息编码如下：

001000011100001000011100011000

100010000100000100000011000

总编码长度为：(7+2+1+4+5)*3=57（bits）《数据结构》解决方案2

不等长编码，例如：

A:0,C:1,E:10,S:11,T:100信息编码如下（34bits）：

1011100101110011010010010001000110出现了二义问题。采用前缀码。Huffman编码是最优前缀码，要借助Huffman树来完成编码和解码。《数据结构》《数据结构》最优二叉树——Huffman树带权路径长度WPL达到最小的二叉树即为Huffman树（最优二叉树）。

1.结点的路径长度2.树的路径长度：树中结点的路径长度之和3．结点的权及带权路径长度若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。4．树的带权路径长度（WPL）树的带权路径长度规定为所有叶子结点的带权路径长度之和。《数据结构》最优二叉树——Huffman树最优二叉树(Huffman树）：给定n个权值{w1,w2,…，wn},构造一棵有n个结点的二叉树，使每个叶结点带权为wi，则其中带权路径长度WPL最小的二叉树称为最优二叉树。

2475

(b)

7524(c)

754(a)2√Huffman树的一个实例《数据结构》最佳判定树考试成绩分布表

Huffman树的一个实例《数据结构》不及格及格中良优<60?<70?<80?<90?0.100.150.250.350.15≥≥≥≥<<<<WPL=0.10*1+0.15*2+0.25*3+0.35*4+0.15*4=3.15

对10000个成绩，则总共需要31500次比较。Huffman树的一个实例《数据结构》WPL=0.10*3+0.15*3+0.25*2+0.35*2+0.15*2=0.3+0.45+0.5+0.7+0.3=2.25对10000个成绩，则总共需要22500次比较。不及格及格中良优<60?<70?<80?<90?0.100.150.250.350.15≥≥≥≥<<<<Huffman树的构造思路《数据结构》在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1，T2，…，Tn),其中每棵二叉树Ti中只有一个带权为wi的根结点,左右子树为空。在F中删除这两棵树，同时将新得到的二叉树加入F中。重复，直到F中只含一棵树为止。这棵树就是Huffman树。初始化选择合并《数据结构》12（1）42571213（2）457（3）2135477213745712（4）213745712（5）19以{7，2，1，4，5}为权值集合构造Huffman树。13练习：以｛9,

3,7,6,12,5｝为权值构造一棵Huffman树，并计算它的WPL。《数据结构》Huffman编码及其实现回到最初的问题，传输：CASTCASTSATEATATASAA：7T：5C：2E：1S：4CE3AST7121972145《数据结构》Huffman编码及其实现将Huffman树的左子树置0，右子树置1，这样每个叶子都获得一个码字：A(7)：0T(5)：10C(2)：1100E(1)：1101S(4)：111WPL=7×1+5×2+2×4+1×4+4×3=41这里的WPL就是编码的总长度。CE3AST712190000111172145解码算法：《数据结构》CE3AST71219000011117214511000111101100011110111010110101001001110CASTCASTSATEATATASA《数据结构》17Huffman编码算法实现1.有n个叶结点的Huffman树中共有m＝2n－1个结点，可将这些结点存储在一个一维数组中。结点结构weightparentlchildrchildtypedefstruct{ unsignedintweight; unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;2.可以采用动态分配的一维数组存储编码表。typedefchar**HuffmanCode;18例：以{7，5，2，4}为权值集合构造哈夫曼树。weightparentlchildrchild170002500032000440005-0006-0007-000（1）2457123419weightparentlchildrchild17000250003250044500560346-0007-000（2）245761234520weightparentlchildrchild17000256003250044500566346110257-000（3）24576111

23456

21（4）2457611181234567weightparentlchildrchild17700256003250044500566346117257

1801622权值={5,29,7,8,14,23,3,11}512927384236371181451.HT的初态weightparentlchildrchild150002290003700048000514000623000710008110009-00010-0001112-000-00013-00014-00015-0002024/5/2indexweightparentlchildrchild1500022900037000480005140006230007300081100090000100000110000120000130000140000150000i=n+1=9在前i-1=8个元素中找无父结点且有最小及次小权值元素的下标s1=7s2=1构造新结点，存储于下标为i=9的元素中权值=最小及次小权和

=5+3=8构造以元素9为根的子二叉树998712024/5/2noweightparentlchildrchild1590022900037100048100051400062300073900811000980711015034110000120000130000140000150000i+1=10在前i-1=9

个元素中找无父结点且有最小及次小权值元素的下标s1=3s2=4新结点存储于元素10权值=7+8=15构造元素10的子二叉树2024/5/2noweightparentlchildrchild1590022900037100048100051400062300073900811110098117110150341119098120000130000140000150000i+1=11在前i-1=10个元素中找无父结点且有最小及次小权值元素的下标s1=9s2=8新结点存储于元素11权值=8+11=19构造元素11的子二叉树2024/5/2noweightparentlchildrchild15900229000371000481000514120062300073900811110098117110151234111909812290510130000140000150000i+1=12在前i-1=11个元素中找无父结点且有最小及次小权值元素的下标s1=5s2=10新结点存储于元素12权值=14+15=29构造元素12的子二叉树2024/5/2noweightparentlchildrchild159002290003710004810005141200623130073900811110098117110151234111913981229051013420116140000150000i+1=13在前i-1=12个元素中找无父结点且有最小及次小权值元素的下标s1=11s2=6新结点存储于元素13权值=19+23=42构造元素13的子二叉树2024/5/2noweightparentlchildrchild1590022914003710004810005141200623130073900811110098117110151234111913981229145101342011614580212150000i+1=14在前i-1=13个元素中找无父结点且有最小及次小权值元素的下标s1=2s2=12新结点存储于元素14权值=29+29=58构造元素14的子二叉树2024/5/2noweightparentlchildrchild1590022914003710004810005141200623130073900811110098117110151234111913981229145101342151161458152121510001314i+1=15在前i-1=14个元素中找无父结点且有最小及次小权值元素的下标s1=13s2=14新结点存储于元素15权值=42+58=100构造元素15的子二叉树30513714

57384118891510292291258141911421323610015weightparentlchildrchild15900229140037100048100051412006231300719008111100981117101512341112191389291451013421561114581521215100013142.HT的终态2024/5/2intHuffman(HuffmanTreeHT,int*w,intn){ for(i=1;i<2*n;i++){//初始化

HT[i].parent=HT[i].lchild=HT[i].rchild=0;if(i<=n)HT[i].weight=w[i-1];//前n个结点赋权值

elseHT[i].weight=0;//后n-1个结点预留

}//初始化结束//待续…2024/5/2intHuffman(HuffmanTreeHT,int*w,intn){//…续

for(i=n+1;i<=2*n-1;i++){//构造HUFFMAN树

Select(HT,i-1,&s1,&s2);//最小及次小权元下标

HT[s1].parent=i;//设置新根结点

HT[s2].parent=i;HT[i].weight=HT[s1].weight+HT[s2].weight;//权值和

HT[i].lchild=s1;//根结点与子结点链接

HT[i].rchild=s2;

}//结束构造}33voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,intw[],intn){

if(n<=1)return0;

m=2*n-1;

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));

for(i=1;i<=m;i++)

if(i<=n)HT[i]={w[i],0,0,0};

elseHT[i]={0,0,0,0};

for(i=n+1;i<=m;i++){//建立Huffman树

Select(HT,i-1,s1,s2);

HT[s1].parent=i;HT[s2].parent=i;

HT[i].lchild=s1;HT[i].rchild=s2;

HT[i].weight=HT[s1].weight+HT[s2].weight;

}34

//求叶到根逆向求每个字符的Huffman编码

HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-1]=‘\0’;for(i=1;i<=n;i++){start=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if(HT[f].lchild==c)cd[--start]=‘0’;elsecd[--start]=‘1’;HC[i]=(char*)malloc((n-start)*sizeof(char));strcpy(HC[i],&cd[start]);}free(cd);}//HuffmanCoding35算法Huffman译码voidHuffmandeCoding(HuffmanTreeHT,intn){m=2*n-1;i=m;while((ch=getchar())!=‘\n’){

if(i<=n){printf(HT[i].data);i=m;}if(ch==‘0’)i=HT[i].lchild;elsei=HT[i].rchild;}//while}//HuffmandeCoding小结《数据结构》问题1Huffman树的不唯一性是否会影响到Huffman编码？问题3方法能否扩展到k元Huffman编码？Huffman树的构造中最困难的部分是什么？问题237本章小结1.定义和性质2.存储结构3.遍历4.线索化顺序结构链式结构二叉链表三叉链表先序线索树中序线索树后序线索树树二叉树森林Huffman编码先序遍历中序遍历遍历存储结构遍历孩子--兄弟先、后根遍历层次遍历线索二叉树Huffman树应用中序遍历后序遍历先序遍历层次遍历第6章结束38习题一、判断题1.二叉树是树的特殊形式。2.一棵度为2的树就是一棵二叉树。3.由树转换成二叉树，其根结点的右子树总是空的。4.如果结点A有3个兄弟，而且B是A的双亲，则B的度是5。5.给定二叉