2. 计算机
  3. [说明] 已知某二叉树的非叶子节点都有两个孩子节点，现将该二叉树存储在结构数组Ht中。节点结构及数组Ht的定义如下： #define MAXLEAFNUM 30 Struct node{ char ch; char *ps

[说明] 已知某二叉树的非叶子节点都有两个孩子节点，现将该二叉树存储在结构数组Ht中。节点结构及数组Ht的定义如下： #define MAXLEAFNUM 30 Struct node{ char ch; char *ps

admin2012-04-11  44
问题 [说明]
   已知某二叉树的非叶子节点都有两个孩子节点，现将该二叉树存储在结构数组Ht中。节点结构及数组Ht的定义如下：
   #define MAXLEAFNUM  30
   Struct node{
   char ch;
   char *pstr;
   int parent;
   int lchild, rchiid;
   };
   Struct node Ht[2 *MAXLEAFNUM];
   该二叉树的n个叶子节点存储在下标为1～n的Ht数组元素中。例如，某二叉树如图8-26所示，其存储结构如图8-27所示，其中，与叶子节点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”分别标识二叉树的左分支和右分支如图8-26所示，从根节点开始到叶子节点为止，按所经过分支的次序将相应标识依次排列，可得到一个0、1序列，称之为对应叶子节点的编码。例如，图8-26中a、b、c、d的编码分别是100、101、0、11。
   函数LeafCode(Ht[]，n)的功能是：求解存储在Ht中的二叉树中所有叶子节点(n个)的编码，叶子节点存储在Ht[1]～Ht[n]中，求出的编码存储区由对应的数组元素pstr域指示。

[函数]
   typedef enum Status {ERROR， OK} Status;
   Status LeafCode (Struet node Ht[], int n)
   {
     int pc, pf;
     int i, start;
     char tstr[31]={’\0’);
     for(i=1;  (1)  ; i++) {
        start=29;
        pc=i; pf=Ht.parent;
        while(Pf!=  (2)  ) {
            if(  (3)  . lchiid==pc)
              tstr[--start]=’0’;
            else
              tstr[-start]=’1’;
              pc=  (4)  ; pf=Ht[Pf].parent;
        }
        Ht.pstr=(char*)malloc(31-start);
        if(!Ht.pstr)return ERROR;
        strcpy(Ht. pstr,  (5)  ;
      }
       return OK;
   }
选项
答案i＜=n，或其等价形式 0 Ht[pf]，或(*(Ht+pf)) pf tstr+start或&tstr[start]
解析 题中已指出该二叉树的n个叶子节点存储在下标为1到n的Ht数组元素中，同时举例说明父节点编号为0的节点是树根节点。所以，(1)处应为“i＜=n”。而到达根即父节点为0时，所以(2)处为“0”。pc用于指出树中的节点，pf则用于指出pc所对应节点的父节点，所以(3)处应为“Ht[pf]”，(4)处应为“pf”。根据tstr的作用，strcpy函数的实参应该是“tstr+start”或“&tstr[start]”，所以(5)处应该为“tstr+start”或“&tstr[start]”。
转载请注明原文地址:https://kaotiyun.com/show/TEVZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

相关试题推荐
随机试题
最新回复(0)