阅读以下函数说明和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--;
}
}
参考答案: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”。