问答题
【说明】
对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合{a,b,c,d}及其权值2、7、4、5，可构造如图6-15所示的最优二叉树，以及相应的结构数组Ht(如表6-14所示，其中数组元素Ht[0]不用)。
{{B}}表6-14 结构数组Ht{{/B}}
结构数组Ht的类型定义如下：
#define MAXLEAFNUM 20
struct node{
char ch; /*扫当前节点表示的字符，对于非叶子节点，此域不用*/
Int weight； /*当前节点的权值*/
int parent; /*当前节点的父节点的下标，为0时表示无父节点*/
int lchild, rchild;
/*当前节点的左、右孩子节点的下标，为0时表示无对应的孩子节点*/
)Ht[2*MAXLEAFNUM];
用“0”或“广标识最优二叉树中分支的规则是：从一个节点进入其左(右)孩子节点，就用“0”(或“1”)标识该分支，如图6-15所示。
若用上述规则标识最优二叉树的每条分支后，从根节点开始到叶子节点为止，按经过分支的次序将相应标识依次排列，可得到由“0”、“1”组成的一个序列，称此序列为该叶子节点的前缀编码。例如，图6-15所示的叶子节点a、b、c、d的前缀编码分别是110、0、111、10。
对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合{a,b,c,d}及其权值2、7、4、5，可构造如图6-15所示的最优二叉树，以及相应的结构数组Ht(如表6-14所示，其中数组元素Ht[0]不用)。
{{B}}表6-14 结构数组Ht{{/B}}
|
{{B}}数组下标{{/B}} |
ch |
weight |
parent |
lchild |
rchild |
|
1 |
a | 2 | 5 | 0 | 0 |
|
2 |
b | 7 | 7 | 0 | 0 |
|
3 |
c | 4 | 5 | 0 | 0 |
|
4 |
e | 5 | 6 | 0 | 0 |
|
5 |
6 | 6 | 1 | 3 | |
|
6 |
11 | 7 | 4 | 5 | |
|
7 |
18 | 0 | 2 | 6 |
#define MAXLEAFNUM 20
struct node{
char ch; /*扫当前节点表示的字符，对于非叶子节点，此域不用*/
Int weight； /*当前节点的权值*/
int parent; /*当前节点的父节点的下标，为0时表示无父节点*/
int lchild, rchild;
/*当前节点的左、右孩子节点的下标，为0时表示无对应的孩子节点*/
)Ht[2*MAXLEAFNUM];
用“0”或“广标识最优二叉树中分支的规则是：从一个节点进入其左(右)孩子节点，就用“0”(或“1”)标识该分支，如图6-15所示。
若用上述规则标识最优二叉树的每条分支后，从根节点开始到叶子节点为止，按经过分支的次序将相应标识依次排列，可得到由“0”、“1”组成的一个序列，称此序列为该叶子节点的前缀编码。例如，图6-15所示的叶子节点a、b、c、d的前缀编码分别是110、0、111、10。
【正确答案】
【答案解析】(1)code[cdlen]='/0'或code[cdlen]=0
(2)Ht[p].parent
(3)—cdlen或其等价形式
(4)*buff='0'或其等价形式
(5)buff—或其等价形式
[要点解析]
这是一道要求读者在用哈夫曼算法构造的最优二叉树上进行编码和译码的程序设计题。本题的解答思路如下。
哈夫曼算法构造最优二叉树的过程如下。
1)根据给定的n个权值{W1,W2,W3,...Wn)构成n棵二叉树的集合F=(T1,T2,T3,...Tn)，其中每棵二叉树引中只有一个带权为Wi的根节点，其左、右子树均为空。
2)在F中选取两棵根节点权值最小的树作为左、右子树构造一棵新的二叉树，且设置新的二叉树的根节点的权值为其左、右子树根节点的权值之和。
3)在F中删除这两棵二叉树，同时将新得到的二叉树加入F中。
4)重复步骤2)和3)，直到F只含一棵树为止。这棵树便是最优二叉树。
综上所述，最优二叉树是从叶子到根构造起来的，每次都是先确定一棵二叉树的左、右子树，然后再构造出树根节点，因此最优二叉树中只有叶子节点和分支数为2的内部节点。若已知叶子的数目为n，则内部节点数比叶子少1，因此整棵树所需的存储空间规模是确定的，可以采用数组空间来存储最优二叉树。
例如，给定字符集合{a,b,c,d)及其权值2、7、4、5，构造最优二叉树的过程如图6-19所示。
由于算法中对构成左、右子树的二叉树不进行限定，因此用哈夫曼算法构造出的最优二叉树的形态不是唯一的。另外，题干中已给出了存放最优二叉树的结构数组Ht的类型定义，以及存储图6-19所构造出的最优二叉树的结构数组Ht(见表6-14)。
由于二叉树中的节点最多只有两个分支，若用“0”和“1”分别标识最优二叉树中的左子树分支和右子树分支，那么从根节点开始到叶子节点为止，按经过分支的次序将相应标识依次排列，可得到由“0”和“1”组成的一个序列，称此序列为该叶子节点的前缀编码。例如，如图6-15所示的最优二叉树叶子节点a、b、c、d的前缀编码分别是110、0、111、10。
当最优二叉树的构造完成后，每个节点的weight域就可挪做他用，在构造哈夫曼编码的过程中，weight域用做被遍历节点的遍历状态标志。从树根出发，以非递归方式遍历最优二叉树的方法是：先沿着树根的左分支向叶子方向搜索，并用code[]记下所经过的分支的标识，同时用cdlen记录节点的路径长度，一直到叶子节点为止，即可得到当前正在访问的叶子的编码。然后，从该叶子节点回退到其父节点F。若刚才是从F的左子树回到F，则下一次应进入F的右子树进行遍历；若是从F的右子树回到F节点，则下一步应继续向F的父节点回退。
由以上分析可知，对于节点F，遍历过程中最多可能以3种不同的情况经过该节点，因此要为F节点的weight域赋予不同的值进行标识。初始时weight=0，当沿遍历路径到达该节点时其weight域值等于0，则进入其左子树分支进行遍历，并将weight置为1：若沿遍历路径到达该节点时其weight域值等于1，则说明刚从其左子树返回，下面应进入其右子树进行遍历并将weight置为2；若沿遍历路径到达该节点时其 weight域值等于2，则说明刚从其右子树返回，下面应继续向该节点的父节点回退，并将weight置为0。遍历路线如图6-20中箭头方向所示。
函数void LeafCode(int root,int n)的功能是：采用非递归方法，遍历最优二叉树的全部叶子节点，为所有的叶子节点构造前缀编码。由于在该函数(1)空缺处之后的语句“strcpy(Hc[p1,code);”，是进行字符串的复制运算，则需要对源串中的串结束标志进行设置，因此(1)空缺处所填写的语句是“code[cdlen]='/0'”或“code[cdlen]=0”。
(2)空缺处是从右子树向父节点回退的处理，因此该空缺处所填入的内容是“Ht[p].parent”。由于每向上层回退一次，节点的路径长度就会减1，因此(3)空缺处所填写的语句是“—cdlen”或其等价形式。
函数void Decode(char *buff,int root)的功能是：将前缀编码序列翻译成叶子节点的字符序列，并输出。译码的过程是：从根出发，若编码序列的当前字符是“0”，则进入左子树分支，否则进入右子树分支，直到到达一个叶子节点时为止，此时叶子所表示的字符就是翻译出的字符。若编码序列还没有结束，则重新从树根出发，重复上述过程，直到将编码序列结束。所以(4)空缺处所填写的语句是“*buff=='0'”或其等价形式。
由于到达一个叶子节点时，超前读入了一个编码序列中的字符，因此(5)空缺处所填写的语句是“buff—”或其等价形式。
函数void LeafCode(int root,int n)的功能是：采用非递归方法，遍历最优二叉树的全部叶子节点，为所有的叶子节点构造前缀编码。由于在该函数(1)空缺处之后的语句“strcpy(Hc[p1,code);”，是进行字符串的复制运算，则需要对源串中的串结束标志进行设置，因此(1)空缺处所填写的语句是“code[cdlen]='/0'”或“code[cdlen]=0”。
(2)空缺处是从右子树向父节点回退的处理，因此该空缺处所填入的内容是“Ht[p].parent”。由于每向上层回退一次，节点的路径长度就会减1，因此(3)空缺处所填写的语句是“—cdlen”或其等价形式。
函数void Decode(char *buff,int root)的功能是：将前缀编码序列翻译成叶子节点的字符序列，并输出。译码的过程是：从根出发，若编码序列的当前字符是“0”，则进入左子树分支，否则进入右子树分支，直到到达一个叶子节点时为止，此时叶子所表示的字符就是翻译出的字符。若编码序列还没有结束，则重新从树根出发，重复上述过程，直到将编码序列结束。所以(4)空缺处所填写的语句是“*buff=='0'”或其等价形式。
由于到达一个叶子节点时，超前读入了一个编码序列中的字符，因此(5)空缺处所填写的语句是“buff—”或其等价形式。