3.4 树的应用

二、综合应用题

　　1．综合应用题题目部分
　　● 习题1：设n0为哈夫曼树的叶子节点的个数，求哈夫曼树共有多少个节点？
　　● 习题2：假定用于通信的电文仅由8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4。试为这8个字母设计哈夫曼编码。
　　● 习题3：下面给出的6个符号串集合中，哪几个有前缀码？
　　B1={0,10,110,1111}；
　　B2={1,01,001,0000}；
　　B3={1,11,101,001,0011}；
　　B4={00,010,0110,1000}；
　　B5={b,c,aa,ac,aba,abb,abc}；
　　B6={b,c,a,aa,ac,aba,abb,abc}。
　　2．综合应用题的答案与分析
　　习题1分析：
　　设度分别为1和2的节点的个数分别为n1和n2，节点的总个数为n，则有：
　　n=n0+n1+n2
　　根据二叉树的性质有：
　　n0=n2+1
　　根据哈夫曼树的构造原理可知，哈夫曼树无度为1的节点，即n1=0，因此：
　　n=n0+n2=n0+n0-1=2n0-1
　　习题2分析：
　　根据C1，C2，…，C8各字母在电文中出现的频率，按其频率大小排序为：
　　3， 4， 5， 6 ， 10， 11， 25， 36
　　C3 C8 C1 C4 C5 C6 C2 C7
　　依此构成的哈夫曼树如图3-12所示。
　　因此，这8个字母的哈夫曼编码为：
　　C1：0100， C2：10， C3：0000， C4：0101
　　C5：001， C6：011， C7：11， C8：0001
　　 

　　习题3分析：
　　前缀码是通信中的一种编码，这种编码中任意字符的编码都不会成为另一个字符的编码的前缀，即使两个字符出现的次数相同，其编码也不相同。由此可见，B1、B2、B4、B5为前缀码，因为B3中的1为11和101的前缀，B6中的a为aa、ac、aba、abb、abc的前缀，因此，B3和B6不是前缀码。
　　3．训练自测表（如表3-6所示）

表3-6 应用题练习自测表