【简答题】

试题三（共15分）
    阅读以下说明和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;
[C函数]
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 */