試題五
閱讀下列說明和C函數(shù)代碼，將應(yīng)填入  (n)  處的字句寫在的對應(yīng)欄內(nèi)。
[說明]
對二叉樹進行遍歷是二叉樹的一個基本運算。遍歷是指按某種策略訪問二叉樹的每個節(jié)點，且每個節(jié)點僅訪問一次的過程。函數(shù)InOrder()借助棧實現(xiàn)二叉樹的非遞歸中序遍歷運算。
設(shè)二叉樹采用二叉鏈表存儲，節(jié)點類型定義如下：
typedef struct BtNode{
ElemType data；    /*節(jié)點的數(shù)據(jù)域，ElemType的具體定義省略*/
struct BtNode * lchild * rchild；  /*節(jié)點的左、右孩子指針域*/
}BtNode，*BTree；
在函數(shù)InOrder()中，用棧暫存二叉樹中各個節(jié)點的指針，并將棧表示為不含頭節(jié)點的單向鏈表(簡稱鏈棧)，其節(jié)點類型定義如下：
typedef struct StNode{    /*鏈棧的節(jié)點類型*/
BTree elem；          /*棧中的元素是指向二叉鏈表節(jié)點的指針*/
struct StNode*link；
}StNode；
假設(shè)從棧頂?shù)綏５椎脑貫閑n、en-1…、e1，則不含頭節(jié)點的鏈棧示意圖如圖5-1所示。

[C函數(shù)]
int  InOrder(BTree root)        /*實現(xiàn)二叉樹的非遞歸中序遍歷*/
{
BTree ptr；                 /*ptr用于指向二叉樹中的節(jié)點*/
StNode*q；                  /*q暫存鏈棧中新創(chuàng)建或待刪除的節(jié)點指針*/
StNode*stacktop=NULL；      /*初始化空棧的棧頂指針stacktop*/
Ptr=root；                  /*ptr指向二叉樹的根節(jié)點*/
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是訪問節(jié)點的函數(shù)，其具體定義省略*/
ptr=  (5)  ；    /*進入右子樹*/
free(q)；               /*釋放原棧頂元素的節(jié)點空間*/
}
return 0；
}/*Inorder*/