1、6.8 哈 夫 曼 树 与 哈 夫 曼 编 码l 最优树的定义最优树的定义l 如何构造最优树如何构造最优树l 前缀编码前缀编码l 赫夫曼编码赫夫曼编码 一、最优树的定义一、最优树的定义树的路径长度树的路径长度定义为：树中每个结点的路径长度之和。结点的路径长度结点的路径长度定义为：从根结点到该结点的路径上 分支的数目。树的带权路径长度树的带权路径长度定义为：树中所有叶子结点的带权路径长度结点的带权路径长度之和 WPL(T)=wklk(对所有叶子结点)。假设有n个权值w1,w2,wn，构造一棵有n个叶子结点的二叉树，每个叶子结点带权为Wi，则其中带权路径长度取最小带权路径长度取最小值值的二叉树称为
2、“最优树最优树”。例如：例如：27 9 75492WPL(T)=72+52+23+43+92 =60WPL(T)=74+94+53+42+21 =89 54 根据给定的 n 个权值 w1,w2,wn，构造 n 棵二叉树的集合 F=T1,T2,Tn，其中每棵二叉树中均只含一个带权值 为 wi 的根结点，其左、右子树为空树；二、如何构造最优树二、如何构造最优树(1)(赫夫曼算法)以二叉树为例：在 F 中选取其根结点的权值为最 小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并 置这棵新的二叉树根结点的权值 为其左、右子树根结点的权值之 和；(2)从F中删去这两棵树，同时加入 刚生成的新树；重
3、复(2)和(3)两步，直至 F 中只 含一棵树为止。(3)(4)9例如:已知权值 W=5,6,2,9,7 5627527697671395276713952795271667132900001111000110110111从根结点到叶子结点的路径上分支字符组成的字符串，可以作为每个叶子结点编码。约定左分支表示字符0，右分支表示字符1。若要设计不等长的编码，则必须任何一个字符任何一个字符的编码都不是同一字符集中另一个字符的编码的编码都不是同一字符集中另一个字符的编码的前缀的前缀，这种编码称为前缀编码。三、前缀编码三、前缀编码以传送的电文为例比较等长编码和不等长编码方法：以传送的电文为例比较等长编
4、码和不等长编码方法：一、一、等长编码：等长编码：电文中所需传送的字符有电文中所需传送的字符有A A、B B、C C、D D，编码分，编码分别为别为0000、0101、1010、1111，若要发送，若要发送ABACCDAABACCDA电文，则以字符串电文，则以字符串0001001010110000010010101100发送，根据字符对应的编码，在接收端能发送，根据字符对应的编码，在接收端能知道发送的电文为知道发送的电文为ABACCDAABACCDA。二、二、不等长编码：不等长编码：当当A A、B B、C C、D D的编码分别为的编码分别为0 0、0000、1 1、1010，要发送上述电文以电文
5、要发送上述电文以电文ABACCDA ABACCDA，相应的字符串为，相应的字符串为000011100000011100，在接收端，对于子串，在接收端，对于子串00000000的译法就有多种，的译法就有多种，可以是可以是AAAAAAAA、BBBB、ABAABA、BAABAA等等。等等。四、赫夫曼编码四、赫夫曼编码 如何得到使电文如何得到使电文 总长最短的二进制前缀编码呢？总长最短的二进制前缀编码呢？假设每种字符在电文中出现的次数为假设每种字符在电文中出现的次数为wi，其编码长度，其编码长度为为li，电文中只有，电文中只有n种字符，则电文总长为种字符，则电文总长为wili。对应到二叉树上，置对应到
6、二叉树上，置wi为叶子结点的权，为叶子结点的权，li为根到为根到叶子的路径长度，则叶子的路径长度，则 wili恰为二叉树上带权路径长度。恰为二叉树上带权路径长度。设计电文总长最短的二进制前缀编码即为以设计电文总长最短的二进制前缀编码即为以n种字种字符出现的频率作权，设计一棵赫夫曼树的问题，由此符出现的频率作权，设计一棵赫夫曼树的问题，由此得到的二进制前缀编码称为赫夫曼编码。得到的二进制前缀编码称为赫夫曼编码。利用赫夫曼树可以构造一种不利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得等长的二进制编码，并且构造所得的的赫夫曼编码赫夫曼编码是一种是一种最优前缀编码最优前缀编码，即使所传即使所
7、传电文的总长度最短电文的总长度最短。例例62：1.熟练掌握二叉树的结构特性二叉树的结构特性，了解相应的证明方法。2.熟悉二叉树的各种存储结构存储结构的特点及适用范围。3.遍历二叉树遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算递归算法法，灵活运用遍历算法灵活运用遍历算法实现二叉树的其它操作。层次遍历层次遍历是按另一种搜索策略进行的遍历。4.理解二叉树线索化的实质线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索线索化过程化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索线索化过程化
8、过程是基于基于对二叉树进行遍历遍历，而线索二叉树上的线索又为相应的遍历提供线索又为相应的遍历提供了方便方便。5.熟悉树的树的各种存储结构存储结构及其特点，掌握树和森林与二叉树的转换树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握掌握 1 至 2 种建立建立二叉树和树的存储结存储结构的方法构的方法。6.学会编写实现树的各种操作实现树的各种操作的算法。7.了解最优树的特性最优树的特性，掌握建立最优树建立最优树和哈夫曼编码和哈夫曼编码的方法。复习题复习题l一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。A.250B.500C.254D.505E.以上答案都不是
9、F.答案：El以下说法错误的是（）A.存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同。B.二叉树是树的特殊情形。C.由树转换成二叉树，其根结点的右子树总是空的。D.在二叉树只有一棵子树的情况下，也要明确指出该子树是左子树还是右子树。E.答案：Bl树的基本遍历策略可分为先根遍历和后根遍历，二叉树的基本遍历策略分为先序、中序和后序三种遍历。我们把由树转化得到的二叉树称该树对应的二叉树，则下面（）是正确的。A.树的先根遍历序列与其对应的二叉树先序遍历序列相同。B.树的后根遍历序列与其对应的二叉树后序遍历序列相同。C.树的先根遍历序列与其对应的二叉树中序遍历序列相同。D.以上均不对。E.答
10、案：Al下面几个符号串编码集合中，不是前缀编码的是（）。A.0,10,110,1111B.11,10,001,101,0001C.00,010,0110,1000D.b,c,aa,ac,aba,abb,abcE.答案：Bl对于前序遍历与中序遍历结果相同的二叉树为（），对于前序遍历和后序遍历结果相同的二叉树为（）。A.一般二叉树B.只有根结点的二叉树C.根结点无左孩子的二叉树D.根结点无右孩子的二叉树E.所有结点只有左子树的二叉树F.所有结点只有右子树的二叉树G.答案：F,B一、已知一棵完全二叉树共有892个结点，试求：1、树的高度。2、叶子结点数3、单支结点数4、最后一个非终端结点的序号。1.10 2.446 3.1 4.446
