二元樹先序遍歷的非遞歸演算法具體實作_javascript技巧

在前面一文，說過二元樹的遞歸遍歷演算法（二元樹先根（先序）遍歷的改進），此文主要講二元樹的非遞歸演算法，採用堆疊結構

總結先根遍歷得到的非遞歸演算法思想如下：

1）入棧，主要是先頭結點入棧，然後visit此結點

2）while，循環遍歷當前結點，直至左孩子沒有結點

3）if結點的右孩子為真，轉入1）繼續遍歷，否則退出當前結點轉入父母結點遍歷轉入1）

先看符合此思想的演算法：

複製程式碼 程式碼如下:

int PreOrderTraverseNonRecursive (TElemType data))
{
 if (T == NULL)
 {
  return -1;
 }

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

 while (!IsStackEmpty(S))
 {
  while (pBiNode)
  {
   {
    Push(&S, (SElemType)pBiNode);
   }   
   pBiNode = pBiNode->對    Pop (&S, (SElemType*)&pBiNode);
  }  
  if ( pBiNode->rchild == NULL)
  {  棧已空，就有問題
  }
  pBiNode = pBiNode->rchild;
 }

 return 0;
}



注意：1）這裡使用了堆疊結構，可參考上文

順序結構儲存的堆疊

            2）這裡在保存結點的時候，我保存的是指針也就是結點的地址，將其變為int型存儲，在pop的時候裡面使用的是指針，所以取的是&pBiNode，而不是pBiNode，為什麼請自行思考指標的使用，最好理解的就是BiTNode *pBiNode;定義改為BiTree pBiNode就很好理解了。

上面這個演算法其實是錯的！為什麼呢？ 這裡我檢查好久，期間出現還出現過無限循環，也出現過從左子樹退出後右邊子樹不顯示，最後我修改了第一個while判斷條件，為什麼呢？因為如果在pop之後，棧已空但是右子樹還有，就無法繼續了，這個在我寫出後並沒有進行太多驗證，後面再闡述，這裡並沒有壓入null指針，看一下壓入空指標的例子，主要是左子樹為空的時候才壓入堆疊的，如下：

複製程式碼

程式碼如下:

int PreOrderTraverseNonRecursive(concreed) (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) p   pBiNode = pBiNode->lchild;
   Push(&S, (SElemType)pBiNode);

  }  }  
  if ( !IsStackEmpty(S))
  {
   Pop(&S, (SElemType*)&pBichild Node> 🎜>   Push(&S, (SElemType)pBiNode);
  }
 }

 return 0;
}

這裡是這樣的，先壓入根節點，然後判斷左子樹是否為空，不為空就壓入棧，否則退出while循環之後就將NULL結點出棧，再判斷當前棧是否為空，如果非空就出棧得到父節點然後判斷右孩子，壓入右孩子結點，再判斷此右子樹的左孩子是否為空，繼續循環。

這裡有兩個浪費的地方：一個就是壓入空孩子結點入棧，二就是頻繁使用GetTop獲得棧頂元素

這裡返回過來再看初開始設計的演算法，那裡正好沒有壓入NULL指針或者說空的孩子結點，但是並不能輸出完整，這裡我們想到可以在判斷棧的時候加入，當前的結點是否為NULL就可以了，這樣就不會出現不會顯示退出左子樹結點不能顯示右子樹結點的尷尬了，如下：

複製程式碼 程式碼如下:

//非遞歸先序號PreOrderTraverseNonRecursiveEx(const BiTree &T,
           int (*VisitNode)(TElemTypedata))
{
{＠ (T == N 🎜 >
 BiTNode *pBiNode = T;
 SqStack S;
 InitStack(&S);
 Push(&S, (SElemType)T);

 while ( !IsStackEmpty(S) || pBiNode)  //主要修改的就是這句話
 {
  while (pBiNode)
  {

 >   if (pBiNode != T)

   {
    Push(&S, (SElemType)pBiNode);
   } >; if(pBiNode = = NULL)
  {
   Pop(&S, (SElemType*)&pBiNode);
  }  
  if (pBi SElemType*)&pBiNode); //如果此時堆疊已空，就有問題
  }
  pBiNode = pBiNode->rchild;
 }
 return 0;
}
}

 return 0;
}
}



在第一個while循環加入這個之後，就可以了，測試用例與二元樹先序遍歷類似。如下測試上節的二元樹範例：

此時輸入的資料仍仍是 12 34 0 0 78 0 0，測試結果如下：

--- BiTree ---Please Enter BiTree Node data:

12

Please Enter BiTree Node data:

34

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
Please Enter BiTree Node data:
0
Please Enter BiTree？
0
12 34 78

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

此時輸入資料應為：12 34 24 0 0 50 0 0 78 37 0 0 0，檢定結果如下：

--- BiTree ---

Please Enter BiTree Node data:
12
Please Enter BiTree Node data:
34
Please Enter BiTree Node data:
34
Please Enter BiTree Node data:2
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
50
Please Enter BiTree Node data:
50
Please Enter。 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

由先序遍歷可知，正好是正確的，另外這些演算法不光是對先序遍歷的，如果想變為中序或後序，只需將上面演算法中的visit之類的先去掉，然後將它加入適當的位置，就可以了