2. 计算机
  3. 已知一棵二叉树用二叉链表存储，t指向根节点，P指向树中任一节点。下列算法为输出从t到P之问路径上的节点。 [C程序] #define MaxSize 1000 typedef struct node { TelemType d

已知一棵二叉树用二叉链表存储，t指向根节点，P指向树中任一节点。下列算法为输出从t到P之问路径上的节点。 [C程序] #define MaxSize 1000 typedef struct node { TelemType d

admin2012-12-10  144
问题 已知一棵二叉树用二叉链表存储，t指向根节点，P指向树中任一节点。下列算法为输出从t到P之问路径上的节点。
   [C程序]
   #define MaxSize 1000
   typedef struct node {
      TelemType data ;
      struct node *ichiid，*rchiid；
   }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-＞rchiid;
                     tag[top]=1;
                   }
        }
   }  (3)  ；
   top--；topl=0；
   while(top＞0) {
        q=stack[top]；    /*反向打印准备*/
        topl++；
         (4)  ；
        top--;
   }
   while(  (5)   ){    /*打印栈的内容*/
       q=stackl[topl]j
       printf(q-＞data)；
       topl--；
   }
}
选项
答案(1)top++ (2) q=q-＞lchild (3) while(top＞0) (4) stackl[topl]=q (5) topl＞0
解析 本题本质上是对二叉树的先序遍历进行考核，但不是简单地进行先序遍历，而是仅遍历从根节点到给定的节点p为止。本题采用非递归算法来实现，其主要思想是：①初始化栈；②根节点进栈，栈不空则循环执行以下步骤直到发现节点p；③当前节点不为空且不为P进栈；④栈顶为p，则结束，否则转③；⑤若右子树访问过，则栈顶的右孩子为当前节点，转③。
   扫描左孩子，．当相应的节点不为P时进栈，所以(1)填“top++”，(2)填“q=q-＞lchild”。在栈不为空时则一直在do while循环中查找，因此(3)填“while(top＞0)”。在进行反向打印准备时，读取stack[top]的信息放到stackl[topl]中，即(4)填“stackl[top1]=q”。打印栈中所有内容，所以(5)填“topl＞0”。
转载请注明原文地址:https://kaotiyun.com/show/1njZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

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