DIV CSS 佈局教程網

二元樹先序遍歷的非遞迴實作與除錯歷程
編輯:JavaScript綜合知識     

先序遍歷用遞迴寫只要三行,但一旦要改成非遞迴版本,就必須自己維護狀態,而狀態就得靠堆疊。本文記錄了以堆疊實作先序遍歷的三個版本,以及前兩版為什麼會出錯。

先想清楚演算法

先序(先根)遍歷的非遞迴思路可以拆成四步:

  1. 根節點先入堆疊,接著立刻拜訪該節點。
  2. 用迴圈一路往左走,沿途拜訪並入堆疊,直到左孩子為空。
  3. 若當前節點有右孩子,回到步驟一的邏輯繼續。
  4. 若沒有右孩子,就出堆疊回到父節點,再檢查父節點的右子樹。

第一版:看起來對,其實錯了

int PreOrderTraverseNonRecursiveEx(const BiTree &T, int (*VisitNode)(TElemType data)) {
  if (T == NULL) { return -1; }

  BiTNode *pBiNode = T;
  SqStack S;
  InitStack(&S);
  Push(&S, (SElemType)T);

  while (!IsStackEmpty(S)) {
    while (pBiNode) {
      VisitNode(pBiNode->data);
      if (pBiNode != T) {
        Push(&S, (SElemType)pBiNode);
      }
      pBiNode = pBiNode->lchild;
    }
    if (pBiNode == NULL) {
      Pop(&S, (SElemType*)&pBiNode);
    }
    if (pBiNode->rchild == NULL) {
      Pop(&S, (SElemType*)&pBiNode); // 此時堆疊可能已空
    }
    pBiNode = pBiNode->rchild;
  }
  return 0;
}

這裡有個容易忽略的細節:入堆疊時存的是指標位址,並以 int 型別保存;因此出堆疊時傳的是 &pBiNode 而不是 pBiNode。若把宣告改成 BiTree pBiNode 會更好理解。

但這個版本本身是錯的。除錯過程中先遇到無限迴圈,接著又出現「左子樹退出後右子樹不顯示」的現象。問題出在:pop 之後若堆疊已空而右子樹還在,流程就無以為繼,而程式並沒有把 NULL 節點壓入堆疊作為哨兵。

第二版:用空節點當哨兵

int PreOrderTraverseNonRecursive(const BiTree &T, int (*VisitNode)(TElemType data)) {
  if (T == NULL) { return -1; }

  BiTNode *pBiNode = T;
  SqStack S;
  InitStack(&S);
  Push(&S, (SElemType)T);

  while (!IsStackEmpty(S)) {
    GetTop(S, (SElemType*)&pBiNode);
    while (pBiNode) {
      VisitNode(pBiNode->data);
      pBiNode = pBiNode->lchild;
      Push(&S, (SElemType)pBiNode);
    }
    if (pBiNode == NULL) {
      Pop(&S, (SElemType*)&pBiNode);
    }
    if (!IsStackEmpty(S)) {
      Pop(&S, (SElemType*)&pBiNode);
      pBiNode = pBiNode->rchild;
      Push(&S, (SElemType)pBiNode);
    }
  }
  return 0;
}

流程是:先壓入根節點,判斷左子樹是否為空,不為空就繼續壓棧;為空則退出迴圈把 NULL 出堆疊,再確認堆疊非空後取出父節點,轉去處理右孩子並壓棧,然後再檢查這個右子樹的左孩子,如此循環。

這個版本代價是兩處浪費:一是把空孩子節點也壓進堆疊,二是頻繁呼叫 GetTop 取堆頂。

第三版:把條件併進迴圈判斷

回到第一版的思路,它沒有壓入 NULL,卻也無法完整輸出。解法是把「當前節點是否為 NULL」一起放進外層 while 的條件:

// 非遞迴先序遍歷二元樹
int PreOrderTraverseNonRecursiveEx(const BiTree &T,
                                   int (*VisitNode)(TElemType data)) {
  if (T == NULL) { return -1; }

  BiTNode *pBiNode = T;
  SqStack S;
  InitStack(&S);
  Push(&S, (SElemType)T);

  while (!IsStackEmpty(S) || pBiNode) // 主要修改的就是這一句
  {
    while (pBiNode) {
      VisitNode(pBiNode->data);
      if (pBiNode != T) {
        Push(&S, (SElemType)pBiNode);
      }
      pBiNode = pBiNode->lchild;
    }
    if (pBiNode == NULL) {
      Pop(&S, (SElemType*)&pBiNode);
    }
    if (pBiNode->rchild == NULL) {
      Pop(&S, (SElemType*)&pBiNode);
    }
    pBiNode = pBiNode->rchild;
  }
  return 0;
}

實測驗證

第一個測試用的二元樹:

輸入 12 34 0 0 78 0 0,輸出為 12 34 78,符合預期。

再換一棵結構更複雜的二元樹:

輸入 12 34 24 0 0 50 0 0 78 37 0 0 0,輸出為 12 34 24 50 78 37,與先序遍歷的定義一致,結果正確。

還能延伸嗎?

可以。這套骨架不只適用先序。只要把 VisitNode 的呼叫位置從「第一次遇到節點時」移到合適的時機,同樣的結構稍作調整就能改寫成中序或後序遍歷。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved