試題五（共 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*/ 
  [答案討論]

[1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]  [9]  [10]  [11]