填空题
阅读下列说明和C程序,将应填入{{U}} (n) {{/U}}处的字句写在对应栏中。
[说明]
借助一个栈结构,可实现二叉树的非递归遍历算法。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({{U}} (1) {{/U}}){ /*不是空树*/
q=(SNode*)malloc(sizeof q);
if(q==NULL)return-1;
/*根节点指针入栈*/
{{U}} (2) {{/U}};
q->elem=P;
stop=q;
P={{U}} (3) {{/U}}; /*进入根的左子树*/
}else{
q=stop;
{{U}} (4) {{/U}}; /*栈顶元素出栈*/
printf("%d|,q->elem->data); /*防问根节点*/
P={{U}} (5) {{/U}}; /*进入根的右子树*/
free(q); /*释放原栈顶元素*/
}/*if*/
}/*while*/
return 0;
}/*InOrderTraverse*/
填空题