文档介绍：一、Huffman树二、(最优二叉树)若干术语:路径:由一结点到另一结点间的分支所构成。路径长度:路径上的分支数目。例如:a→e的路径长度=2二叉树的路径长度:从二叉树根到所有叶子结点的路径长度之和。树路径长度=8二叉树的带权路径长度:从二叉树根结点到所有叶子结点的路径长度与相应叶子结点权值的乘积之和(WPL)即树中所有叶子结点的带权路径长度之和Huffman树:带权路径长度最小的树。Huffman常译为哈夫曼、赫夫曼、霍夫曼等树的带权路径长度如何计算?WPL=åwklk构造Huffman树的基本思想:权值大的结点用短路径,权值小的结点用长路径。构造Huffman树的步骤(即Huffman算法):(1)由给定的n个权值{w1,w2,…,wn}构造n棵二叉树的集合F={T1,T2,…,Tn}(即森林),其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树均空。(2)在F中选取两棵根结点权值最小和次小的树分别做为左右子树构造一棵新的二叉树,且让新二叉树根结点的权值等于其左右子树的根结点权值之和。(3)在F中删去这两棵树,同时将新得到的二叉树加入F中。(4)重复(2)和(3),直到F只含一棵树为止。这棵树便是Huffman树。具体操作步骤:对权值进行合并、删除与替换——在权值集合{7,5,2,4}中,总是合并当前值最小的两个权具体操作步骤:对权值进行合并、删除与替换——在权值集合{7,5,2,4}中,总是合并当前值最小的两个权Huffman树特点:肯定没有度为1的结点;一棵有n0个叶子结点的Huffman树,共有2n0-1个结点;讨论:Huffman树有什么用?例:设有4个字符d,i,a,n,出现的频度分别为7,5,2,4,怎样编码才能使它们组成的报文在网络中传得最快?法1:等长编码令d=00,i=01,a=10,n=11,则:WPL1=2bit×(7+5+2+4)=36法2:不等长编码令d=0;i=10,a=110,n=111,则:WPL2=1bit×7+2bit×5+3bit×(2+4)=。具体构造方法如下:设需要编码的字符集合为{d1,d2,…,dn},各个字符在电文中出现的次数集合为{w1,w2,…,wn},以d1,d2,…,dn作为叶结点,以w1,w2,…,wn作为各叶结点的权值构造一棵二叉树,规定哈夫曼树中的左分支为0,右分支为1,则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的代码总长度最短的不等长编码称之为哈夫曼编码。明确:要实现哈夫曼编码,就要先构造哈夫曼树按左“0”右“1”对哈夫曼树的所有分支编号——在哈夫曼树的基础上构造哈夫曼编码哈夫曼编码结果:d=0,i=10,a=110,n=111WPL=1bit×7+2bit×5+3bit(2+4)=35(小于等长码的WPL=36)在建立不等长编码时,必须使任何一个字符的编码都不是另一个字符编码的前缀,这样才能保证译码的惟一性。例:若字符a的编码为01,b的编码为010,c的编码为10对于代码串01010,在译码时无法判定是将前两位码01译成字符a还是将前三位码010译为字符b。在哈夫曼树中,由于每个字符结点都是叶子结点,而叶子结点不可能