数据结构第6章二叉树

1、佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University1重点重点：二叉树的性质、遍历；二叉：二叉树的性质、遍历；二叉树与森林树与森林( (树树) )的相互转换的相互转换难点难点：树和二叉树应用的算法设计：树和二叉树应用的算法设计 佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University26.1 树的定义和基本术语树的定义和基本术语6.2 二叉树二叉树6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.6 赫夫曼树及其应用赫夫曼树及其应用佛山科学技术学院佛山科学技术学院 Fo

2、shan UniversityFoshan University3 树的定义树的定义(递归定义递归定义)：树是：树是n(n0)个结点个结点(元素元素)的有限集。的有限集。l若若 n=0，称为，称为空树空树。l若若 n 0，则，则l有且仅有一个特定的称为有且仅有一个特定的称为根根的结点的结点root；l当当n 1时，除根以外的其他结点划分为时，除根以外的其他结点划分为m(m0) 个互不相交的有限集个互不相交的有限集T1, T2, Tm，其中每一个，其中每一个集合本身又是一棵树，并且称为根的集合本身又是一棵树，并且称为根的子树子树。且。且对任意的对任意的i(mi1), Ti存在惟一的结点存在惟一的

3、结点xi , 有有H，H为树中元素之间的二元关系为树中元素之间的二元关系集。集。佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University4树的表示树的表示AABCDEFGHIJKL佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University5树的其他表示树的其他表示-嵌套集合、凹入表示嵌套集合、凹入表示GCABDHIJEKFLA* B* E* F* K* L* C* G* D* H* I* J*佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University6结点结点结

4、点的度结点的度结点的层次结点的层次终端结点终端结点(叶子叶子)非终端结点非终端结点(分支结点分支结点)内部结点内部结点基本术语基本术语ABCDEFGHIJKL第第1层层第第2层层第第3层层第第4层层高度为高度为4孩子孩子双亲双亲兄弟兄弟祖先祖先子孙子孙堂兄弟堂兄弟树的度树的度树的深度树的深度/高度高度有序树有序树无序树无序树森林森林佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University7基本操作基本操作： InitTree( &T) 操作结果：构造空树操作结果：构造空树T。 DestroyTree( &T ) 初始条件：树初始条件：树T已存在。已

5、存在。 操作结果：销毁树操作结果：销毁树T。 ClearTree( &T ) 初始条件：树初始条件：树T已存在。已存在。 操作结果：将树操作结果：将树T清为空树。清为空树。 TreeEmpty( T ) 初始条件：树初始条件：树T已存在已存在 操作结果：若操作结果：若T为空树则返回为空树则返回TRUE，否则，否则FALSE。佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University8 TreeDepth( T ) 初始条件：树初始条件：树T已存在已存在 操作结果：返回树操作结果：返回树T的深度。的深度。 Root( T ) 初始条件：树初始条件：树T

6、已存在。已存在。 操作结果：返回操作结果：返回T的根。的根。 Value( T, cur_e ) 初始条件：树初始条件：树T已存在，已存在，cur_e是是T中的某个结点。中的某个结点。 操作结果：返回操作结果：返回cur_e的值；的值； Assign( T, &cur_e, value ) 初始条件：树初始条件：树T已存在，已存在，cur_e是是T中的某个节点。中的某个节点。 操作结果：结点操作结果：结点cur_e赋值为赋值为value。佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University9 Parent( T, cur_e ) 初始条件：树初

7、始条件：树T已存在，已存在，cur_e是是T中的某个结点。中的某个结点。 操作结果：若操作结果：若cur_e是是T的非根结点，则返回它的双亲，的非根结点，则返回它的双亲， 否则函数值为否则函数值为“空空”。 LeftChild( T, cur_e ) 初始条件：树初始条件：树T已存在，已存在，cur_e是是T中的某个结点。中的某个结点。 操作结果：若操作结果：若cur_e是是T的非叶子结点，则返回它的最左的非叶子结点，则返回它的最左 孩子，否则返回孩子，否则返回“空空”。 RightSibling( T, cur_e ) 初始条件：树初始条件：树T已存在，已存在，cur_e是是T中某个结点。中

8、某个结点。 操作结果：若操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则有右兄弟，则返回它的右兄弟，否则 返回返回“空空”。佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University10 InsertChild( &T, p, i, c ) 初始条件：树初始条件：树T已存在，已存在，p指向指向T中某个结点，中某个结点，1 i p所指所指 结点的度结点的度+1，非空树，非空树c于于T不相交。不相交。 操作结果：插入操作结果：插入c为为T中中p所指结点的第所指结点的第i棵子树。棵子树。 DeleteChild( &T, p, i ) 初始条件：树初

9、始条件：树T已存在，已存在，p指向指向T中的某个结点，中的某个结点，1 i p所所 指结点的度指结点的度。 操作结果：删除操作结果：删除T中中p所指结点的第所指结点的第i棵子树。棵子树。 TraverseTree( T, visit() ) 初始条件：树初始条件：树T已存在，已存在，visit()是对结点操作的应用函数。是对结点操作的应用函数。 操作结果：按某种次序对操作结果：按某种次序对T 的每个结点调用函数的每个结点调用函数visit()一一 次且至多一次。一旦次且至多一次。一旦visit()失败，则操作失败。失败，则操作失败。佛山科学技术学院佛山科学技术学院 Foshan Univers

10、ityFoshan University116.1 树的定义和基本术语树的定义和基本术语6.2 二叉树二叉树6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.6 赫夫曼树及其应用赫夫曼树及其应用佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University12二叉树的定义二叉树的定义(递归定义递归定义)l特点：每个结点特点：每个结点至多只有两棵子树至多只有两棵子树，子树有，子树有左左右右之分之分l二叉树二叉树 : 度不大于度不大于2的有序树的有序树lADT BinaryTree二叉树二叉树无序树无序树佛山科学技术学院佛山科学

11、技术学院 Foshan UniversityFoshan University13 二叉树或为空树，或是由一个根结点加上两棵分二叉树或为空树，或是由一个根结点加上两棵分别称为别称为左子树左子树和和右子树右子树的、的、互不交的互不交的二叉树组成。二叉树组成。ABCDEFGHK根结点左子树右子树佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University14二叉树的五种基本形态：二叉树的五种基本形态：P空树空树只含根结点只含根结点PPPLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子树左右子树均不为空均不为空树树佛山科学技术学院佛山科学技术学

12、院 Foshan UniversityFoshan University15二叉树的性质二叉树的性质l性质性质1：二叉树的第：二叉树的第i层至多有层至多有2i-1个结点个结点(i1)l性质性质2：深度为：深度为h的二叉树至多有的二叉树至多有2h 1个结点个结点(h1) 思考：性质思考：性质1和性质和性质2推广到推广到k叉树，结果会如何？叉树，结果会如何？l性质性质3：n0 = n2 + 1结点总数结点总数 n = n0 + n1 + n2分支数分支数 n-1 = n1 + 2n2ki- -1(kh- -1)/(k- -1)佛山科学技术学院佛山科学技术学院 Foshan UniversityFo

13、shan University16定义定义1 满二叉树满二叉树 (Full Binary Tree) 一棵深度为一棵深度为k且有且有2 k-1个结点的二叉树称为满个结点的二叉树称为满二叉树。二叉树。62175438910 1113 14 1512满二叉树满二叉树佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University17215436 7216543非完全二叉树非完全二叉树定义定义2 完全二叉树完全二叉树 (Complete Binary Tree) 若设二叉树的高度为若设二叉树的高度为h，则共有，则共有h层。除第层。除第 h 层外，层外，其它各层其

14、它各层 (1 h-1) 的结点数都达到最大个数，第的结点数都达到最大个数，第 h 层层从右向左从右向左连续缺若干结点，这就是完全二叉树。连续缺若干结点，这就是完全二叉树。621754389 10 11 12完全二叉树完全二叉树佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University18l满二叉树满二叉树：一棵深度为：一棵深度为k且有且有2k 1个结点的二叉树个结点的二叉树(k0)l完全二叉树完全二叉树：对于深度为：对于深度为k的完全二叉树，则的完全二叉树，则1) 前前k-1层为满二叉树；层为满二叉树；2) 第第k层结点依次占据最左边的位置；层结点依

15、次占据最左边的位置；3) 一个结点有右孩子，则它必有左孩子；一个结点有右孩子，则它必有左孩子；4) 度为度为1的结点个数为的结点个数为0或或15) 叶子结点只可能在层次最大的两层上出现；叶子结点只可能在层次最大的两层上出现；6) 对任一结点，若其右分支下的子孙的最大层次对任一结点，若其右分支下的子孙的最大层次为为l, 则其左分支下的子孙的最大层次必为则其左分支下的子孙的最大层次必为l或或l+1。佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University19性质性质4：具有：具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 由性质由性质2 2

16、k-1-1 n 2k-1 或或 2k-1 n 2k 于是于是 k-1 log2n k即即 log2n1, 则其双亲是结点则其双亲是结点 ；(2) 如果如果2i n，则结点，则结点i无左孩子无左孩子(结点结点i为叶子结为叶子结点点)；否则其左孩子是结点；否则其左孩子是结点2i ；(3) 如果如果2i + 1 n，则结点，则结点i无右孩子；否则其右孩无右孩子；否则其右孩子是结点子是结点2i + 1。1log2n2/ i佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University221.已知完全二叉树有已知完全二叉树有100个结点，则该二叉树有多少个结点，则

17、该二叉树有多少个叶子结点个叶子结点？答：若认为每个结点均已编号，则最大的编号为答：若认为每个结点均已编号，则最大的编号为100，其父结点编号为其父结点编号为50（见右下图），从（见右下图），从51到到100均为叶均为叶子，因此叶子数为子，因此叶子数为100-50=50。佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University23已知完全二叉树有已知完全二叉树有50个叶子结点，则该二叉树个叶子结点，则该二叉树的总结点数至少应有多少个？的总结点数至少应有多少个？方法方法1： 假设完全二叉树的最大非叶结点编号假设完全二叉树的最大非叶结点编号为为m，则最大

18、叶结点编号为，则最大叶结点编号为2m+1,(2m+1)-m=50 m=49总结点数目总结点数目=2m+1=99方法方法2： 由性质由性质3：n0=n2+1 即：即：50=n2+1 所以：所以：n2=49 令令n1=0得：得：n= n0 + n2=99佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University24l二叉树的顺序存储结构l类型定义typedef ElemType SqBiTreeMAX_TREE_SIZE; /0号单元存储根结点 1) 依据性质5，用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素；结点在存储区中的相

19、对位置反映它们逻辑上的关系2) 仅适用于完全二叉树l一般二叉树的顺序存储方法通过补虚结点，将一般的二叉树变成完全二叉树空间开销大！佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University25完全二叉树的顺序表示完全二叉树的顺序表示11 2 3 4 5 6 7 8 9102489 105673佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University26l空间利用率问题： 在最坏情况下，一个深度为k且只有k个结点的单支树(树中不存在度为2的结点)，则需要长度为2k-1的一维数组。12345671 2 3 4

20、 5 0 0 0 0 6 7一般二叉树的顺序表示一般二叉树的顺序表示佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University27l二叉树的链式存储结构l引入辅助空间表示结点之间的关系：双亲-孩子二叉链表(左、右孩子链域)三叉链表(双亲及左、右孩子链域)l二叉链的类型定义(动态链表)typedef struct BiTNodel ElemType data; struct BiTNode *lchild, *rchild;/ 左右孩子指针 BiTNode, *BiTree;若有n个结点，则共有2n个链域；其中n-1不为空，指向孩子；另外n+1个为空链

21、域（为何？）佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University28链表表示链表表示lChild data rChilddatalChildrChild二叉链表含两个指针域的结点结含两个指针域的结点结构构lChild data parent rChild含三个指针域的结点结构含三个指针域的结点结构parentdatalChildrChild三叉链表佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University29二叉树链表表示的示例二叉树链表表示的示例 AAABBBCCCDDDFFFEEErootroot

22、root二叉树 二叉链表 三叉链表佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University30l遍历二叉树l基于先/中/后序遍历算法的应用l为什么强调使用函数调用的结果l先/中/后序遍历的非递归算法l层次遍历算法及其应用l二叉树的创建方法l线索二叉树佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University31l遍历二叉树按一定的搜索路径对树中的每一结点访问且仅访问一次l遍历时的搜索路线(约定：先左后右，D-根,L-左子树,R-右子树)l先(根)序遍历：1 2 4 5 6 7 3 (DLR) l中(根)序

23、遍历：4 2 6 5 7 1 3 (LDR)l后(根)序遍历：4 6 7 5 2 3 1 (LRD)l层次遍历：1 2 3 4 5 6 71234567佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University32练习：如图所示为一棵二叉树，试分别写练习：如图所示为一棵二叉树，试分别写出此树的中序、先序及后序序列。出此树的中序、先序及后序序列。D E C B H G F AD E C B H G F AA B C D E F G HA B C D E F G HB D C E A F H GB D C E A F H G佛山科学技术学院佛山科学技术学

24、院 Foshan UniversityFoshan University33如图所示为一棵二叉树，试分别写出如图所示为一棵二叉树，试分别写出此树的中序、先序及后序序列。此树的中序、先序及后序序列。中序序列：中序序列：BDCEAFHGBDCEAFHG先序：先序：ABCDEFGHABCDEFGH后序：后序：DECBHGFADECBHGFA佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University34l先/中/后序遍历的区别如右图，三者经过的搜索路线是相同的；只是访问结点的时机不同。每一结点在整个搜索路线中会经过3次：l第一次进入到该结点此时访问该结点，称

25、为先序遍历l由左子树回溯到该结点此时访问该结点，称为中序遍历l由右子树回溯到该结点此时访问该结点，称为后序遍历佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University35l遍历算法的递归实现l二叉树的递归定义性质，决定了它的很多算法都可用递归实现，遍历算法就是其中之一。l对于二叉树的遍历，可以不去具体考虑各子问题(左子树、根、右子树)的遍历结果是什么，而去考虑如何由各子问题的求解结果构成原问题(二叉树)的遍历结果递归规律的确定。必须注意的是，当二叉树小到一定程度，即空树时，应直接给出解答递归结束条件及处理。 佛山科学技术学院佛山科学技术学院 Fos

26、han UniversityFoshan University36先序遍历Status PreOrderTraverse( BiTree T, Status ( *Visit ) (ElemType e) ) if ( T != NULL ) if ( Visit(T-data) ) if ( PreOrderTraverse( T-lchild, Visit ) ) if ( PreOrderTraverse( T-rchild, Visit ) ) return OK; return ERROR; else return OK;佛山科学技术学院佛山科学技术学院 Foshan Univers

27、ityFoshan University376.1 树的定义和基本术语树的定义和基本术语6.2 二叉树二叉树6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.6 赫夫曼树及其应用赫夫曼树及其应用佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University38l最优树最优树l路径路径：从树中一个结点到另一个结点之间的分支：从树中一个结点到另一个结点之间的分支l路径长度路径长度：路径上的分支数目：路径上的分支数目l树的路径长度树的路径长度：树根到每一结点的路径长度之和：树根到每一结点的路径长度之和完全二叉树是这种路径长度最短的

28、二叉树完全二叉树是这种路径长度最短的二叉树l结点的带权路径长度结点的带权路径长度：该结点到树根之间的路径长度与：该结点到树根之间的路径长度与结点上权的乘积结点上权的乘积l树的带权路径长度树的带权路径长度：树中所有叶子结点的带权路径长度：树中所有叶子结点的带权路径长度之和之和l最优二叉树或赫夫曼树最优二叉树或赫夫曼树：树的带权路径长度最小的二叉：树的带权路径长度最小的二叉树树niiilwWPL1佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University39abcd010011000111cdbaWPL = 2*(7+5+2+4)=36WPL=1*7+2

29、*5+3*(2+4)=35佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University40赫夫曼树的应用赫夫曼树的应用最佳判定算法最佳判定算法分数分数05960697079808990100比例比例0.050.150.400.300.10等级等级不及格不及格及格及格中等中等良好良好优秀优秀a60?0.050.150.400.300.10a70?a80?a90?WPL=3.15佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University41赫夫曼树的应用赫夫曼树的应用最佳判定算法最佳判定算法0.050.150.4

30、00.300.10WPL=2.0570a8080a9060a70a60佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University4260?70?80?0 )，则树中，则树中 最多有最多有 2h-1 个结点个结点满二叉树满二叉树 最少有最少有2h-1个结点个结点佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University45l问题描述问题描述：已知电文中出现的一组字符及出现频率，试：已知电文中出现的一组字符及出现频率，试为该组字符编码以使得电文总长最短。为该组字符编码以使得电文总长最短。l前缀编码前缀编码：某字

31、符的编码不是其他字符编码的前缀。：某字符的编码不是其他字符编码的前缀。l赫夫曼编码过程赫夫曼编码过程：1) 由由n个权值，形成包含有个权值，形成包含有2n-1个结点的赫夫曼树个结点的赫夫曼树2) 约定赫夫曼树的左分支表示字符约定赫夫曼树的左分支表示字符0，右分支表示字符，右分支表示字符1，则从根结点到叶子结点的路径上的分支字符组成的，则从根结点到叶子结点的路径上的分支字符组成的字符串作为该叶子结点字符的编码。字符串作为该叶子结点字符的编码。佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University46赫夫曼树和赫夫曼编码的存储结构选取赫夫曼树和赫夫曼

32、编码的存储结构选取l由权值数由权值数n唯一确定树中的结点数为唯一确定树中的结点数为 (2n - 1)一次性分配结点空间一次性分配结点空间l编码：从叶子到根的路径编码：从叶子到根的路径快速访问双亲快速访问双亲l译码：从根到叶子的路径译码：从根到叶子的路径快速访问孩子快速访问孩子赫夫曼编码赫夫曼编码: 按实际长度动态分配空间，按实际长度动态分配空间， 需要一需要一个求编码的工作空间个求编码的工作空间,长度为长度为n赫夫曼树：赫夫曼树：三叉静态链表三叉静态链表佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University47平均码长平均码长 = (0.23+0

33、.29)*2+ (0.11+0.14)*3+ (0.05+0.03+0.07+0.08)*4 = 1.04+0.75+0.92 = 2.71若电文有若电文有1000个字符，则电文的个字符，则电文的码长为码长为2.71*1000 = 271081iiilpl赫夫曼编码的算法赫夫曼编码的算法5381119234278151429295810000000001111111佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University48 /* 赫夫曼树和赫夫曼编码的存储表示赫夫曼树和赫夫曼编码的存储表示 */ typedef struct unsigned i

34、nt weight; unsigned int parent, lchild, rchild; HTNode,*HuffmanTree; /* 动态分配数组存储赫夫动态分配数组存储赫夫曼树曼树 */ typedef char *HuffmanCode; /* 动态分配数组存储动态分配数组存储赫夫曼编码表赫夫曼编码表 */佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University49void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) m=2*n-1; HT=(HuffmanT

35、ree)malloc(m+1)*sizeof(HTNode); /* 0号号单元未用单元未用 */ for(p=HT+1,i=1;i=n;+i,+p,+w) *p = *w, 0, 0, 0 ; for( ;i=m;+i,+p) *p = 0, 0, 0, 0 ; for(i=n+1;i=m;+i) /* 建赫夫曼树建赫夫曼树 */ 佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University50/* 在在HT1i-1中选择中选择parent为为0且且weight最小的两最小的两个结点，其序号分别为个结点，其序号分别为s1和和s2 */ select(

36、*HT,i-1,&s1,&s2); HTs1.parent=HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; 佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University51/* 从叶子到根逆向求每个字符的赫夫曼编码从叶子到根逆向求每个字符的赫夫曼编码 */*HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/* 分配分配n个字符编码的头指针向量个字符编码的头指针向量(0不用不用) */cd=(char*)m

37、alloc(n*sizeof(char); /* 分配求编码的工作空分配求编码的工作空间间 */cdn-1=0; /* 编码结束符编码结束符 */for(i=1;i=n;i+) /* 逐个字符求赫夫曼编码逐个字符求赫夫曼编码 */ start=n-1; /* 编码结束符位置编码结束符位置 */ for(c=i, f=HTi.parent; f!=0; c=f, f=HTf.parent) 佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University52/* 从叶子到根逆向求编码从叶子到根逆向求编码 */ if(HTf.lchild=c) cd-star

38、t=0; else cd-start=1; HCi=(char*)malloc(n-start)*sizeof(char); /* 为第为第i个字符编码分配空间个字符编码分配空间 */ strcpy(HCi,&cdstart); /* 从从cd复制编码复制编码(串串)到到HC */ free(cd); /* 释放工作空间释放工作空间 */佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University5351429 7823 3111429 7823 1135887151429233581111358191429238715佛山科学技术学院佛山科学技术学院

39、 Foshan UniversityFoshan University54113581929 2314871529291487152911358192342佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University55例例 w=5, 29, 7, 8, 14, 23, 3, 11见见P1481135819234229148715295811358192342291487152958100佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University56例：例：假设用于通信的电文由字符集假设用于通信的电文由字符集

40、a，b，c，d，e，f，g，h中的字母构成，这中的字母构成，这8个字母在电文中出现的概率个字母在电文中出现的概率分别为分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。 (1) 为这为这8个字母设计哈夫曼编码。个字母设计哈夫曼编码。 (2) 若用这三位二进制数对这若用这三位二进制数对这8个字母进行等长编码个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少它使电文总长平均压缩多少?佛山科学技术学院佛山科学技术学院 Foshan UniversityFoshan University57解：解：(1)哈夫曼编码图见题图哈夫曼编码图见题图根据上图可得编码表：根据上图可得编码表： a:0010b:10 c:00000 d:0001 e:01 f:00001g:11 h:0011(2) 用三位二进行数进行的等长编码平均长度为用三位二进行数进行的等长编码平均长度为3，而根据哈，而根据哈夫曼树编码的平均码长为：夫曼树编码的平均码长为：4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10