題目：

遞歸和非遞歸倆種方法實現(xiàn)二叉樹的前序遍歷。

思路一：

對二叉樹的遞歸遍歷我相信大家只要學了數(shù)據(jù)結構后應當都很容易就能寫出，這里主要是討論二叉樹的非遞歸寫法。按照二叉樹前序遍歷的定義，無論是訪問整棵樹還是其子樹，均應該遵循先訪問根結點，然后訪問根結點的左子樹，最后訪問根結點的右子樹的。在整個二叉樹前序遍歷的過程中，程序始終要做的工作分成倆個部分：（借用輔助棧來實現(xiàn)）
1. 當前正在處理的樹（子樹）
2. 保存在棧中等待處理的部分。

當棧中元素位于棧頂即將出棧時，意味著其根結點和左子樹已訪問完成，出棧后，進入其右子樹進行訪問。

代碼如下：

擴展：

如果要求是非遞歸后序遍歷呢？非遞歸后序稍微有點復雜。按照二叉樹后序遍歷的定義，無論是訪問整棵樹還是起子樹，均應該遵循先訪問根結點左子樹，然后訪問根結點的右子樹，最后訪問根結點。值得注意的是，當一個元素位于棧頂即將處理的是，其左子樹的訪問一定完成，如果其右子樹不為空，接下來應該進入其右子樹訪問，但此時該棧頂元素時不能出棧的，因為它作為根結點，其本身的值還未被訪問。只有等到其右子樹也訪問完成后，該棧頂元素才能出棧，并輸出它的值。 因此，在二叉樹后序遍歷的算法中，必須每個節(jié)點維護一個類型為int的整數(shù)nTag，
其每個元素(節(jié)點)的nTag取值為0 或1，用于標識棧中每個元素的狀態(tài)。
1. 當一個元素剛進棧時，其對應的nTag 值置為0；
2. 當它位于棧頂即將被處理時，其nTag 值為0.意味著應該訪問其右子樹，于是將右子樹作為當前處理的對象，此時該棧頂元素仍應該保留在棧中，并將其對應的nTag 值改為1.
3. 當其右子樹訪問完成后，該元素又一次位于棧頂，而此時其nTag 值為1，意味著其右子樹已訪問完成，接下來，應該直接訪問的就是它，將其出棧。

代碼如下：