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