NO.9505

（）
　阅读以下说明和C 函数，将应填入 (n) 处的字句写在答题纸的对应栏内。
【说明】
已知某二叉树的非叶子结点都有两个孩子结点，现将该二叉树存储在结构数组 Ht中。结点结构及数组Ht的定义如下：

　　#define MAXLEAFNUM 30

　　struct node{

　　char ch; /*当前结点表示的字符，对于非叶子结点，此域不用*/

　　char *pstr; /*当前结点的编码指针，非叶子结点不用*/

　　int parent; /*当前结点的父结点，为0时表示无父结点*/

　　int lchild，rchild;

　　/*当前结点的左、右孩子结点，为0时表示无对应的孩子结点*/

　　};

　　struct node Ht[2 * MAXLEAFNUM]; /*数组元素Ht[0]不用*/

　　该二叉树的n个叶子结点存储在下标为1～n的Ht数组元素中。例如，某二叉树如图3-1所示，其存储结构如图3-2所示，其中，与叶子结点a对应的数组元素下标为1，a 的父结点存储在 Ht[5]，表示为 Ht[1].parent=5。Ht[7].parent=0 表示 7 号结点是树根，Ht[7].lchild=3、Ht[7].rchild=6 分别表示 7 号结点的左孩子是 3号结点、右孩子是 6 号结点。
　　

　　如果用“0”或“1”分别标识二叉树的左分支和右分支(如图 3-1 所示)，从根结点开始到叶子结点为止，按所经过分支的次序将相应标识依次排列，可得到一个 0、1序列，称之为对应叶子结点的编码。例如，图3-1中a、b、c、d的编码分别是100、101、0、11。
　　函数LeafCode(Ht[]，n)的功能是：求解存储在Ht中的二叉树中所有叶子结点(n个)的编码，叶子结点存储在Ht[1]～Ht[n]中，求出的编码存储区由对应的数组元素pstr域指示。
　　函数LeafCode从叶子到根逆向求叶子结点的编码。例如，对图3-1中叶子结点a求编码的过程如图3-3所示。

typedef enum Status {ERROR， OK} Status;

【函数】　　
Status LeafCode(struct node Ht[]， int n)

　　{

　　int pc， pf; /*pc用于指出树中的结点，pf则指出pc所对应结点的父结点*/

　　int i，start;

　　char tstr[31] = {‘\0’}; /*临时存储给定叶子结点的编码，从高下标开始存入*/

　　for(i=1;(1) ; i++) { /*对所有叶子结点求编码，i表示叶结点在HT数组中的下标*/

　　start = 29;

　　pc = i; pf = Ht[i].parent;

　　while (pf != (2) ) { /*没有到达树根时，继续求编码*/

　　if ( (3) .lchild == pc ) /*pc所表示的结点是其父结点的左孩子*/

　tstr[--start] = ‘0’;

　　else

　　tstr[--start] = ‘1’;

　　pc = (4) ; pf = Ht[pf].parent; /*pc和pf分别向根方向回退一层*/

　　}/* end of while */

　　Ht[i].pstr = (char *) malloc(31-start);

　　if (!Ht[i].pstr) return ERROR;

　　strcpy(Ht[i].pstr， (5) );

　　}/* end of for */

　　return OK;

　　}/* end of LeafCode */

参考答案:

（1） i<=n，或其等价表示　　（2） 0 （3） Ht[pf]，或(*(Ht+pf))
（4） pf 　　　　　　（5）&tstr[start]，或tstr+start

详细解析:

    本题考查C语言的基本控制结构、数组以及参数传递基础知识。
    哈夫曼算法构造最优二叉树的过程如下。
    （1）根据给定的n个权值{W 1，W2，…，Wn]构成n棵二叉树的集合F={T1，T2，…， Tn}，其中每棵二叉树Ti中只有一个带权为Wi的根结点，其左、右子树均空。
    （2）在F中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且置新二叉树的根结点的权值为其左、右子树根结点的权值之和。
    （3）在F中删除这两棵二叉树，同时将新得到的二叉树加入F中。
    （4）重复（2）和（3），直到F只含一棵树为止。这棵树便是最优二叉树。
    最优二叉树是从叶子到根构造起来的，每次都是先确定一棵二叉树的左、右子树，然后再构造出树根结点，因此，最优二叉树中只有叶子结点和分支数为2的内部结点。若已知叶子的数目为n，则内部结点数比叶子少1，因此，整棵树所需的存储空间规模是确定的，可以采用数组空间来存储最优二叉树。
    题目中已经指出该二叉树的n个叶子结点存储在下标为1~n的Ht数组元素中，同时举例说明父结点编号为0的结点式树根结点。因此，空（1）处应填入“i<=n”。同时，除了根结点之外，每个结点都有唯一的父结点，因此到达树根的标志为结点的父结点编号为0，因此，空（2）处应填入“0”。
    根据代码中pc和pf的作用：pc用于指出树中的结点，pf则指出pc所对应结点的父结点，则空（3）处应填入“Ht[pf]”，空（4）处填入“pf”使得pc回退至其父结点位置。
    空（5）考查了标准函数的调用，对于函数strcpy()，其原型为char* strcpy (char*，constchar*)。两个参数都是字符指针，根据代码中tstr的作用，应将tstr+start( tstr[start]~tstr[29]存放编码)作为实参调用strcpy，因此空（5）处应填入“tstr+start”或“&tstr[start]”。