3.4 树的应用

　　3.4 树的应用

　　考试大纲涉及本节的知识点有：等价类的问题、哈夫曼（Huffman）树和哈夫曼编码。

　　一、选择题

　　1．选择题题目部分
　　● 若一棵哈夫曼树共有9个顶点，则其叶子节点的个数为 （1）
　　（1）A．4 B．5 C．6 D．7
　　● 根据使用频率，为5个字符设计的哈夫曼编码不可能是 （2） 。
　　（2）A．111，110，10，01，00 B．000，001，010，011，1
　　C．001，000，10，01，11 D．110，100，101，11，1
　　● 在度为m的哈夫曼树中，其叶节点个数为n，则非叶节点的个数为 （3） 。
　　（3）A． B． C． D．

　　● 设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有 （4） 个节点。
　　（4）A．12 B．13 C．25 D．26
　　● 由带权1、3、5、6、9的5个叶子节点生成的哈夫曼树的带权路径长度为 （5） 。
　　（5）A．50 B．52 C．55 D．60
　　2．选择题练习答案与分析
　　题号（1）答案 B
　　习题分析：
　　2个叶子节点的哈夫曼树的构成，只需进行1次合并，即把2个叶子节点合并即可。合并的同时会产生1个根节点，所以一棵2个叶子节点的哈夫曼树共有3个节点。再比如3个叶子节点的哈夫曼树的构成，需要进行2次合并，第1次是把2个值较小的叶子节点合并，然后再把合并好的节点和第3个叶子节点合并。每进行1次合并会产生1个新的节点。所以1棵3个叶子节点的哈夫曼树共有5个节点。
　　或者用另一种方法来算：从哈夫曼树的构造过程，可以知道哈夫曼树中无1度的节点。只有2度节点和0度节点（即叶子节点）。设此树中度为2的节点有n2个，度为0的节点有n0个。因为此树共有9个节点，所以此树的总度数为n1=8度。所以现在可以得出两个等量关系式：
　　（1）树的总度数的等量关系8=n2×2；
　　（2）树的总节点数的等量关系9=n2+n0。
　　计算两式得n2=4，n0=5，即度为2的节点有4个，度为0的节点也就是叶子节点有5个，所以此题应选答案B。
　　题号（2）答案 D
　　习题分析：
　　哈夫曼编码属于前缀编码，根据前缀编码的定义，任一字符的编码都不是另一字符编码的前缀。而选项D中，1是前面4个字符的前缀，明显违反了这一原则，所以不属于哈夫曼编码。
　　题号（3）答案 B
　　习题分析：
　　在构造度为m的哈夫曼树的过程中，每次把m个子节点合并为一个父节点（第一次可能合并少于m个子节点），每次合并减少m-1个节点，从n个节点减少到最后只剩下一个父节点，共需 次合并，每次合并增加一个非叶节点。
　　题号（4）答案 C
　　习题分析：
　　由哈夫曼树的性质可知，具有n个叶子节点的哈夫曼树共有2n-1个节点，所以本题中的哈夫曼树共有2×13-1=25个节点。
　　题号（5）答案 B
　　习题分析：
　　构造的哈夫曼树如图3-11所示，该树的带权路径长度为52。
　　

　　3．训练自测表（如表3-5所示）

表3-5 选择题练习自测表