试题五
阅读下列说明和C函数代码，将应填入  (n)  处的字句写在的对应栏内。
[说明]
对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个节点，且每个节点仅访问一次的过程。函数InOrder()借助栈实现二叉树的非递归中序遍历运算。
设二叉树采用二叉链表存储，节点类型定义如下：
typedef struct BtNode{
ElemType data；    /*节点的数据域，ElemType的具体定义省略*/
struct BtNode * lchild * rchild；  /*节点的左、右孩子指针域*/
}BtNode，*BTree；
在函数InOrder()中，用栈暂存二叉树中各个节点的指针，并将栈表示为不含头节点的单向链表(简称链栈)，其节点类型定义如下：
typedef struct StNode{    /*链栈的节点类型*/
BTree elem；          /*栈中的元素是指向二叉链表节点的指针*/
struct StNode*link；
}StNode；
假设从栈顶到栈底的元素为en、en-1…、e1，则不含头节点的链栈示意图如图5-1所示。

[C函数]
int  InOrder(BTree root)        /*实现二叉树的非递归中序遍历*/
{
BTree ptr；                 /*ptr用于指向二叉树中的节点*/
StNode*q；                  /*q暂存链栈中新创建或待删除的节点指针*/
StNode*stacktop=NULL；      /*初始化空栈的栈顶指针stacktop*/
Ptr=root；                  /*ptr指向二叉树的根节点*/
while (  (1)  | | stacktop !=NULL) {
while (ptr!=NULL)  {
q=(StNode*)malloc(sizeof (StNode))；
if  (q= =NULL)
return-1；
q-＞elem=ptr；
(2)  ；
stacktop=q；            /*stacktop指向新的栈顶*/
ptr=  (3)  ；    /*进入左子树*/
}
q=stacktop；
(4)  ；        /*栈顶元素出栈*/
visit(q)；              /*visit是访问节点的函数，其具体定义省略*/
ptr=  (5)  ；    /*进入右子树*/
free(q)；               /*释放原栈顶元素的节点空间*/
}
return 0；
}/*Inorder*/