<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=)