2. 计算机
  3. 阅读下列说明和C程序，将应填入(n)处的字句写在对应栏中。 [说明] 借助一个栈结构，可实现二叉树的非递归遍历算法。InOrderTraverse数实现中序非递归遍历，遍历 过程如下： 若不是空树，根节点入栈，进入左子树；若已

阅读下列说明和C程序，将应填入(n)处的字句写在对应栏中。 [说明] 借助一个栈结构，可实现二叉树的非递归遍历算法。InOrderTraverse数实现中序非递归遍历，遍历 过程如下： 若不是空树，根节点入栈，进入左子树；若已

admin2010-12-17  69
问题 阅读下列说明和C程序，将应填入(n)处的字句写在对应栏中。
   [说明]
   借助一个栈结构，可实现二叉树的非递归遍历算法。InOrderTraverse数实现中序非递归遍历，遍历
   过程如下：
   若不是空树，根节点入栈，进入左子树；若已经是空树，则栈顶元素出栈，访问该元素(根节点)，进入该节点的右子树，继续直到遍历完成。
   函数中使用的预定义符号如下：
   typedef struct BiTNode{
   int data；
   struct BiTNode *iChiid，*rChiid；
   } BiTNode，*BiTree；
   typedef struct SNode{/*链栈的节点类型*/
   BiTree elem；
   struct SNode *next；
   }SNode；
   [函数]
   int InOrderTraverse(BiTree root)
   {
   BiTree P；
   SNode *q，*stop=NULL；/*不带头节点的单链表作为栈的存储结构*/
   P=root；
   while(p !=NULL || stop !=NULL){
   if(  (1)  ){    /*不是空树*/
   q=(SNode*)malloc(sizeof q)；
   if(q==NULL)return-1；
   /*根节点指针入栈*/
     (2)；
   q-＞elem=P；
   stop=q；
   P=(3)；    /*进入根的左子树*/
   }else{
   q=stop；
     (4)；    /*栈顶元素出栈*/
   printf("%d|，q-＞elem-＞data)；  /*防问根节点*/
   P=(5)；    /*进入根的右子树*/
   free(q)；     /*释放原栈顶元素*/
   }/*if*/
   }/*while*/
   return 0；
   }/*InOrderTraverse*/
(5)
选项
答案q-＞elem-＞rChild
解析 本题考察的是二叉树的遍历以及链栈的使用。
   由注释可知，空(1)是“不是空树”的条件，应填P!=NULL。
   空(2)是链栈入栈操作，stop是指向链栈栈顶的指针，故空(2)应填q-＞next=stop。
   空(3)进入根的左子树，故应填P-＞lChild。
   空(4)是链栈出栈操作，stop是指向链栈栈顶的指针，出栈后，应修改栈顶指针，故应填stop=stop-＞next。
   空(5)是进入右子树，要注意的是，此处是通过链栈节点q进行访问，不能想当然的认为是q-＞rChild，而应该是q-＞elem-＞rChild。
转载请注明原文地址:https://kaotiyun.com/show/uvDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

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