2009年上半年軟考軟件設計師下午試卷[9]
摘要：試題五（共15分）閱讀下列說明和C函數代碼，將應填入（n）處的字句寫在答題紙的對應欄內?！菊f明】對二叉樹進行遍歷是二叉樹的一個基本運算。遍歷是指按某種策略訪問二叉樹的每個結點，且每個結點僅訪問一次的過程。函數InOrder()借助棧實現二叉樹的非遞歸中序遍歷運算。設二叉樹采用二叉鏈表存儲，結點類型定義如下：
試題五（共 15 分）
閱讀下列說明和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*/
[答案討論]
溫馨提示：因考試政策、內容不斷變化與調整，本網站提供的以上信息僅供參考，如有異議，請考生以權威部門公布的內容為準！
備考學習
一鍵領取新人專享大禮包
備考學習
2025上半年軟考各科真題免費下載
備考學習
系統集成項目管理工程師報考指南視頻課程
備考資料
2025下半年軟考各科經典100題
歷年真題
軟考各科歷年真題在線答題練習
每日一練
備考2025年軟考不慌，每日一練陪伴你
延伸閱讀
軟考備考資料免費領取
去領取
距離考試還有
天
- 0
- 6
- 2
專注在線職業教育24年
APP 
微信群 
掃描二維碼
掃描二維碼
