<code>/*</code>
<code>先序周遊，首先通路根結點然後周遊左子樹，最後周遊右子樹。在周遊左、右子樹時，仍然先通路</code>
<code>根結點，然後周遊左子樹，最後周遊右子樹，如果二叉樹為空則傳回。</code>
<code>*/</code>
<code>//處理過如下</code>
<code>//對于任一結點p： </code>
<code>// 1)将結點p入棧,通路節點p,節點p出棧；</code>
<code>// 2)判斷結點p的右孩子是否為空，其次判斷p的左孩子是否為空，這樣先壓右子樹入棧，左子</code>
<code>// 樹後壓就可以先通路；</code>
<code>void</code> <code>PrevOrder_NonR()</code>
<code> </code><code>{</code>
<code> </code><code>stack<BinaryTreeNode<T>*> s;</code>
<code> </code><code>if</code> <code>(_root)</code>
<code> </code><code>{</code>
<code> </code><code>s.push(_root); </code><code>//将樹入棧</code>
<code> </code><code>}</code>
<code> </code><code>while</code> <code>(!s.empty()) </code><code>//棧不為空，根節點先出棧</code>
<code> </code><code>BinaryTreeNode<T>* top = s.top();</code>
<code> </code><code>s.pop();</code>
<code> </code><code>cout << top->_data << </code><code>" "</code><code>;</code>
<code> </code><code>if</code> <code>(top->_right) </code><code>//壓入右子樹</code>
<code> </code><code>{</code>
<code> </code><code>s.push(top->_right);</code>
<code> </code><code>}</code>
<code> </code><code>if</code> <code>(top->_left) </code><code>//壓入左子樹</code>
<code> </code><code>s.push(top->_left);</code>
<code> </code><code>cout << endl;</code>
<code> </code><code>}</code>
<code>中序周遊，中序周遊首先周遊左子樹，然後通路根結點，最後周遊右子樹。在周遊左、右子樹時，</code>
<code>仍然先周遊左子樹，再通路根結點，最後周遊右子樹。即：若二叉樹為空則結束傳回</code>
<code>否則：</code>
<code>（1）中序周遊左子樹。</code>
<code>（2）通路根結點。</code>
<code>（3）中序周遊右子樹。</code>
<code>// 處理過程如下：</code>
<code>// 對于任一結點cur， </code>
<code>// 1)若其左孩子不為空，則将cur入棧并将cur的左孩子置為目前的cur，然後對目前結點cur再進行相</code>
<code>// 同的處理；</code>
<code>// 2)若其左孩子為空，則取棧頂元素并進行出棧操作，通路該棧頂結點，然後将目前的cur置為棧頂</code>
<code>// 結點的右孩子；</code>
<code>// 3)直到cur為NULL并且棧為空則周遊結束</code>
<code>void</code> <code>InOrder_NonR()</code>
<code> </code><code>BinaryTreeNode<T>* cur = _root;</code>
<code> </code><code>while</code> <code>(cur || !s.empty())</code>
<code> </code><code>while</code> <code>(cur)</code>
<code> </code><code>s.push(cur);</code>
<code> </code><code>cur = cur->_left;</code>
<code> </code><code>if</code> <code>(!s.empty())</code>
<code> </code><code>BinaryTreeNode<T>* top = s.top();</code>
<code> </code><code>cout << top->_data << </code><code>" "</code><code>;</code>
<code> </code><code>s.pop();</code>
<code> </code><code>cur = top->_right;</code>
<code>後序周遊，</code>
<code>後序周遊首先周遊左子樹，然後周遊右子樹，最後通路根結點，在周遊左、右子樹時，仍然先周遊左子</code>
<code>樹，然後周遊右子樹，最後周遊根結點。即：若二叉樹為空則結束傳回</code>
<code>// 要保證根結點在左孩子和右孩子通路之後才能通路，是以對于任一結點P，先将其入棧。如果P不存在</code>
<code>// 左孩子和右孩子，則可以直接通路它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被</code>
<code>// 通路過了，則同樣可以直接通路該結點。若非上述兩種情況，則将P的右孩子和左孩子依次入棧，這</code>
<code>// 樣就保證了每次取棧頂元素的時候，左孩子在右孩子前面被通路，左孩子和右孩子都在根結點前面被</code>
<code>// 通路。</code>
<code>void</code> <code>PostOrder_NonR()</code>
<code> </code><code>BinaryTreeNode<T>* pre = NULL;</code>
<code> </code><code>//根節點要想被通路則該節點沒有右子樹或者沒有孩子節點</code>
<code> </code><code>if</code> <code>(top->_right == NULL || top->_right == pre)</code>
<code> </code><code>pre = top;</code>
<code> </code><code>else</code>
二叉樹層次周遊即按照層次通路，通常用隊列來做。通路根，通路子女，再通路子女的子女（越往後的層次越低）（兩個子女的級别相同）
<code>void</code> <code>LevelOrder()</code>
<code> </code><code>queue<BinaryTreeNode<T>*> q;</code>
<code> </code><code>q.push(_toot);</code>
<code> </code><code>while</code> <code>(!q.empty()) </code>
<code> </code><code>BinaryTreeNode<T>* front = q.front();</code>
<code> </code><code>q.pop();</code>
<code> </code><code>cout << front->_data << </code><code>" "</code><code>;</code>
<code> </code><code>if</code> <code>(front->_left)</code>
<code> </code><code>q.push(front->_left);</code>
<code> </code>
<code> </code><code>if</code> <code>(front->_right)</code>
<code> </code><code>q.push(front->_right);</code>
本文轉自 七十七快 51CTO部落格，原文連結:http://blog.51cto.com/10324228/1755467
![二叉樹周遊(遞歸)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)