2. 计算机
  3. 阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。 [说明] 已知一棵二叉树用二叉链表存储，t指向根结点，p指向树中任一结点。下列算法为输出从t到P之间路径上的结点。 [C程序] #define Maxsiz

阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。 [说明] 已知一棵二叉树用二叉链表存储，t指向根结点，p指向树中任一结点。下列算法为输出从t到P之间路径上的结点。 [C程序] #define Maxsiz

admin2010-12-16  62
问题 阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。
   [说明]
   已知一棵二叉树用二叉链表存储，t指向根结点，p指向树中任一结点。下列算法为输出从t到P之间路径上的结点。
   [C程序]
   #define Maxsize 1000
   typedef struct node{
   TelemType data;
   struct node*1child,*rchild;
   }BiNode,*BiTree;
   void Path(BiTree t,BiNode*P)
   { BiTree*stack[Maxsize],*stackl[Maxsize],*q;
   int tag[Maxsize],top=0,topl;
   q=t;
   /*通过先序遍历发现P*/
   do(while(q!=NULL && q!=p)
   /*扫描左孩子，且相应的结点不为P*/
   {  (1);
   stack[top]=q;
   tag[top]=0;
     (2);
   }
   if(top＞0)
   {  if(stack[top]==P)  break;    /*找到P，栈底到栈顶为t到P*/
   if(tag[top]==1)top--;
   else{q=stack[top];
   q=q-＞rchild;
   tag[top]=1;
   }
   }
   } (3);
   top--; topl=0;
   while(top＞0){
   q=stack[top];    /*反向打印准备*/
   topl++;
     (4);
   top--;
   }
   while((5)){    /*打印栈的内容*/
   q=stackl[topl];
   printf(q-＞data);
   topl--;
   }
   }
选项
答案(1) top++ (2) q=q-＞1child (3) while(top＞0) (4) stackl[top1]=q (5) top1＞0
解析 本题本质上是对二叉树的先序遍历进行考核，但不是简单地进行先序遍历，而是仅遍历从根结点到给定的结点p为止。本题采用非递归算法来实现，其主要思想是：①初始化栈：②根结点进栈，栈不空则循环执行以下步骤直到发现结点p；③当前结点不为空且不为P进栈；④栈顶为p，则结束，否则转③；⑤若右子树访问过，则栈顶的右孩子为当前结点，转③。
   扫描左孩子，当相应的结点不为P时进栈，所以(1)填“top++”，(2)填“q=q-＞1child”。在栈不为空时则一直在do while循环中查找，因此(3)填“while(top＞0)”。在进行反向打印准备时，读取stack[top]的信息放到stackl[top]中，即(4)填“stackl[top1]=q”。打印栈中所有内容，所以(5)填“top1＞0”。
转载请注明原文地址:https://kaotiyun.com/show/I6jZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

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