二叉樹先序遍歷的非遞歸算法具體實現(xiàn)

更新時間：2014年01月09日 15:22:56 作者：

這篇文章主要介紹了二叉樹先序遍歷的非遞歸算法，有需要的朋友可以參考一下

在前面一文，說過二叉樹的遞歸遍歷算法（二叉樹先根（先序）遍歷的改進(jìn)），此文主要講二叉樹的非遞歸算法，采用棧結(jié)構(gòu)

總結(jié)先根遍歷得到的非遞歸算法思想如下：

1）入棧，主要是先頭結(jié)點(diǎn)入棧，然后visit此結(jié)點(diǎn)

2）while，循環(huán)遍歷當(dāng)前結(jié)點(diǎn)，直至左孩子沒有結(jié)點(diǎn)

3）if結(jié)點(diǎn)的右孩子為真，轉(zhuǎn)入1）繼續(xù)遍歷，否則退出當(dāng)前結(jié)點(diǎn)轉(zhuǎn)入父母結(jié)點(diǎn)遍歷轉(zhuǎn)入1）

先看符合此思想的算法：

復(fù)制代碼代碼如下:

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;
}

注意：1）這里使用了棧結(jié)構(gòu)，可參看上文順序結(jié)構(gòu)存儲的棧

2）這里在保存結(jié)點(diǎn)的時候，我保存的是指針也就是結(jié)點(diǎn)的地址，將其變?yōu)閕nt型存儲，在pop的時候里面使用的是指針，所以取的是&pBiNode，而不是pBiNode，為什么請自行思考指針的使用，最好理解的就是BiTNode *pBiNode;定義改為BiTree pBiNode就很好理解了。

上面這個算法其實是錯誤的！為什么呢？這里我檢查好久，期間出現(xiàn)還出現(xiàn)過無限循環(huán)，也出現(xiàn)過從左子樹退出后右邊子樹不顯示，最后我修改了第一個while判斷條件，為什么呢？因為如果在pop之后，棧已空但是右子樹還有，就無法繼續(xù)了，這個在我寫出后并沒有進(jìn)行太多驗證，后面再闡述，這里并沒有壓入null指針，看一下壓入空指針的例子，主要是左子樹為空的時候才壓入棧的，如下：

復(fù)制代碼代碼如下:

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;
}

這里是這樣的，先壓入根節(jié)點(diǎn)，然后判斷左子樹是否為空，不為空就壓入棧，否則退出while循環(huán)之后就將NULL結(jié)點(diǎn)出棧，再判斷當(dāng)前棧是否為空，如果非空就出棧得到父節(jié)點(diǎn)然后判斷右孩子，壓入右孩子結(jié)點(diǎn)，再判斷此右子樹的左孩子是否為空，繼續(xù)循環(huán)。

這里有兩個浪費(fèi)的地方：一個就是壓入空孩子結(jié)點(diǎn)入棧，二就是頻繁使用GetTop獲得棧頂元素

這里返回過來再看初開始設(shè)計的算法，那里正好沒有壓入NULL指針或者說空的孩子結(jié)點(diǎn)，但是并不能輸出完整，這里我們想到可以在判斷棧的時候加入，當(dāng)前的結(jié)點(diǎn)是否為NULL就可以了，這樣就不會出現(xiàn)不會顯示退出左子樹結(jié)點(diǎn)不能顯示右子樹結(jié)點(diǎn)的尷尬了，如下：

復(fù)制代碼代碼如下:

//非遞歸先序遍歷二叉樹
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;
}

在第一個while循環(huán)加入這個之后，就可以了，測試用例與二叉樹先序遍歷類似。如下測試上節(jié)的二叉樹例子：

此時輸入的數(shù)據(jù)仍然還是 12 34 0 0 78 0 0，測試結(jié)果如下：

--- BiTree ---
Please Enter BiTree Node data:
12
Please Enter BiTree Node data:
34
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
78
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
12 34 78

這個還不足以測試，再看如下的二叉樹

此時輸入數(shù)據(jù)應(yīng)該為：12 34 24 0 0 50 0 0 78 37 0 0 0，測試結(jié)果如下：

--- BiTree ---
Please Enter BiTree Node data:
12
Please Enter BiTree Node data:
34
Please Enter BiTree Node data:
24
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
50
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
78
Please Enter BiTree Node data:
37
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
12 34 24 50 78 37