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

admin2012-12-10  65

问题 已知一棵二叉树用二叉链表存储,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)