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

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