摘要:試題五(共15分)閱讀下列說明和C函數(shù)代碼,將應填入(n)處的字句寫在答題紙的對應欄內(nèi)。【說明】對二叉樹進行遍歷是二叉樹的一個基本運算。遍歷是指按某種策略訪問二叉樹的每個結點,且每個結點僅訪問一次的過程。函數(shù)InOrder()借助棧實現(xiàn)二叉樹的非遞歸中序遍歷運算。設二叉樹采用二叉鏈表存儲,結點類型定義如下:
試題五(共 15 分)
閱讀下列說明和C 函數(shù)代碼,將應填入 (n) 處的字句寫在答題紙的對應欄內(nèi)。
【說明】
對二叉樹進行遍歷是二叉樹的一個基本運算。遍歷是指按某種策略訪問二叉樹的每個結點,且每個結點僅訪問一次的過程。函數(shù)InOrder()借助棧實現(xiàn)二叉樹的非遞歸中序遍歷運算。
設二叉樹采用二叉鏈表存儲,結點類型定義如下:
typedef struct BtNode{
ElemType data; /*結點的數(shù)據(jù)域,ElemType的具體定義省略*/
struct BtNode *lchild,*rchild; /*結點的左、右孩子指針域*/
}BtNode, *BTree;
在函數(shù)InOrder()中,用棧暫存二叉樹中各個結點的指針,并將棧表示為不含頭結點
的單向鏈表(簡稱鏈棧),其結點類型定義如下:
typedef struct StNode{ /*鏈棧的結點類型*/
BTree elem; /*棧中的元素是指向二叉鏈表結點的指針*/
struct StNode *link;
}StNode;
假設從棧頂?shù)綏5椎脑貫?en、en-1、…、e1,則不含頭結點的鏈棧示意圖如圖5-1所示。
【C函數(shù)】
int InOrder(BTree root) /* 實現(xiàn)二叉樹的非遞歸中序遍歷 */
{
BTree ptr; /* ptr用于指向二叉樹中的結點 */
StNode *q; /* q暫存鏈棧中新創(chuàng)建或待刪除的結點指針*/
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是訪問結點的函數(shù),其具體定義省略*/
ptr = (5) ; /*進入右子樹*/
free(q); /*釋放原棧頂元素的結點空間*/
}
return 0;
}/*InOrder*/
[答案討論]
軟考備考資料免費領取
去領取