2. 计算机
  3. 阅读下列程序说明和C程序，把应填入其中(n)处的字句，写在对应栏内。 【程序说明】 已知某二叉树的前序遍历和中序遍历序列，可以得到该二叉树的结构。本程序实现了根据这两个遍历序列生成一棵链接表示的二叉树。 构造二叉树的算法要点是：由前序遍历序

阅读下列程序说明和C程序，把应填入其中(n)处的字句，写在对应栏内。 【程序说明】 已知某二叉树的前序遍历和中序遍历序列，可以得到该二叉树的结构。本程序实现了根据这两个遍历序列生成一棵链接表示的二叉树。 构造二叉树的算法要点是：由前序遍历序

admin2009-05-15  35
问题 阅读下列程序说明和C程序，把应填入其中(n)处的字句，写在对应栏内。
  【程序说明】
   已知某二叉树的前序遍历和中序遍历序列，可以得到该二叉树的结构。本程序实现了根据这两个遍历序列生成一棵链接表示的二叉树。
   构造二叉树的算法要点是：由前序遍历序列，该序列的第一个元素是根结点元素。该元素将中序遍历序列分成左、右两部分，那些位于该元素之前的元素是它的左子树上的元素，位于该元素之后的元素是它的右子树上的元素。对于左、右子树，由它们的前序遍历序列的第一个元素可确定左、右子树的根结点，参照中序遍历序列又可进一步确定子树的左、右子树元素。如此递归地参照两个遍历序列，最终构造出二叉树。
   两个遍历序列作为主函数main()的参数。为简单起见，程序假定两个遍历序列是相容的。主函数调用函数restore()建立二叉树。函数restore()以树(子树)的前序遍历和中序遍历两序列及序列长为参数，采用递归方法建立树(子树)。函数postorder()实现二叉树的后序遍历序列输出，用来验证函数restore()建立的二叉树。
   【程序】
   #include(stdio．h＞
   #include＜stdlib．h＞
   #define MAX 100
   typedef struct node{
       char data；
       struet node * llink，*rlink；
   }TNODE；
   charpred[MAX]，inod[MAX]；
   TNODE * restore (Char*，char*，int)；
   main(int argc，Char*  *argv)
   {
       TNODE * root；
       if(argc＜3)exit(0)；
       strcpy(pred，argv[1])；
       strcpy(inod，argv[2])；
       root=restore(pred，inod，strlen(pred))postorder(root)；
       printf("\n\n")；
   }
   TNODE * restore(Char * ppos，char * ipos，int n)
   {    /*参数包括前序遍历序列数组和中序遍历数组*/
       TNODE * ptr；
       Char * rpos；
       int k；
       if(n  ＜=0)return NULL；
       ptr=  (TNODE  *)malloc(sizeof(TNODE))；
       ptr→data=(1)；
       for  (2)  rpos=ipos；rpos  ＜ipos+n；rpos++  )
       if(*rpos== * ppos)break；
       k =(3)；
       ptr→llink = restore(ppos+1，  (4)，k)；
       ptr→rlink = restore  (5) +  k，rpos  +  1，n-1-k)；
       return ptr；
   }
   postorder(TNODE  *ptr)
   { if(ptr==NULL)return；
       postorder(ptr→llink)；
       postorder(ptr→rlink)；
       prinft("%c"，ptr→data)；
   }
选项
答案(4)ipos或rpos-k
解析 这里对左子树进行递归调用方法restore，左子树的中序遍历序列从ipos开始。
转载请注明原文地址:https://kaotiyun.com/show/CujZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

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