【答案解析】这是一道要求读者在用哈夫曼算法构造的最优二叉树上进行编码和译码的程序设计题。本题的解答思路如下。 哈夫曼算法构造最优二叉树的过程如下。 ①根据给定的n个权值{W1，W2，W3，……Wn)构成n棵二叉树的集合F={T1，T2，T3，……Tn)，其中每棵二叉树Ti中只有一个带权为Wi的根结点，其左、右子树均空。 ②在F中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树根结点的权值之和。 ③在F中删除这两棵二叉树，同时将新得到的二叉树加入F中。 ④重复步骤②和③，直到F只含一棵树为止。这棵树便是最优二叉树。 综上所述，最优二叉树是从叶子到根构造起来的，每次都是先确定一棵二叉树的左、右子树，然后再构造出树根结点，因此最优二叉树中只有叶子结点和分支数为2的内部结点。若已知叶子的数目为n，则内部结点数比叶子少1，因此整棵树所需的存储空间规模是确定的，可以采用数组空间来存储最优二叉树。 例如，给定字符集合{a，b，c，d)及其权值2、7、4、5，构造最优二叉树的过程如图3-31所示。 由于算法中对构成左、右子树的二叉树不进行限定，因此用哈夫曼算法构造出的最优二叉树的形态不是惟一的。另外，题干中已给出了存放最优二叉树的结构数组Ht的类型定义，以及存储图3-31所构造出的最优二叉树的结构数组Ht(见表3-12)。 由于二叉树中的结点最多只有两个分支，若用“0”和“1”分别标识最优二叉树中的左子树分支和右子树分支，那么从根结点开始到叶子结点为止，按经过分支的次序将相应标识依次排列，可得到由“0”和“1”组成的一个序列，称此序列为该叶子结点的前缀编码。例如图3-26所示的最优二叉树叶子结点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。遍历路线如图3-32中箭头方向所示。