二叉树的递归遍历就不赘述了，下面主要熟悉二叉树的非递归遍历。

前序遍历

方法1

二叉树的前序遍历为：头 -> 左 -> 右

可以使用栈来模拟这个顺序：弹出头结点后打印（访问），先将头结点的右孩子压栈，再将左孩子压栈，以保证出栈时左孩子先于右孩子；重复此过程，最后就会惊奇地发现整棵树的打印是按照前序遍历进行的。代码如下：

void pre(TreeNode* root)
{
    if(root == nullptr)
        return;
    TreeNode* tmp;
    stack<TreeNode*> stk;
    stk.push(root);
    while(!stk.empty())
    {
        tmp = stk.top();
        cout << tmp->data << endl;
        stk.pop();
        if(tmp->right != nullptr)//!!!
            stk.push(tmp->right);
        if(tmp->left != nullptr) //!!!
            stk.push(tmp->left);
    }
}

方法2

我们发现，通过递归访问二叉树节点时，不管是前序、中序或是后序遍历，执行流总是先进入左孩子，再进入右孩子，只是访问时机的不同造成了这三种访问顺序的差异。也就是说，执行流总是先一路向左下跑，如果道路不通，再跳到最近的右节点，然后继续往该节点的左下方一直跑，如此循环。所以我们可以模拟这种执行流完成前序遍历，代码如下：

void pre_1(TreeNode* root)
{
    if(root == nullptr)
        return;
    TreeNode* tmp = root;
    stack<TreeNode*> stk;
    while(tmp != nullptr || !stk.empty())//为什么要tmp？因为当返回到root时,stk为空,但右子树还没有遍历
    {
        if(tmp != nullptr)
        {
            cout << tmp->data << endl;
            stk.push(tmp);
            tmp = tmp->left;
        }
        tmp = stk.top();
        stk.pop();
        tmp = tmp->right;
    }
}

中序遍历

中序遍历我们仍可以采用上面的方法 2 来完成，只需改变打印输出的位置，代码如下：

void in(TreeNode* root)
{
    if(root == nullptr)
        return;
    TreeNode* tmp = root;
    stack<TreeNode*> stk;
    while(tmp != nullptr || !stk.empty())//为什么要tmp？因为当返回到root时,stk为空,但右子树还没有遍历
    {
        if(tmp != nullptr)
        {
            stk.push(tmp);
            tmp = tmp->left;
        }
        tmp = stk.top();
        stk.pop();
        cout << tmp->data << endl;
        tmp = tmp->right;
    }
}

后序遍历

后序遍历就不能直接使用上面的两种方式了，不过我们可以利用方法 1 迂回地完成后序遍历。方法 1 中，我们先压右孩子，再压左孩子，这样就能够保证出栈时顺序为：

头节点 -> 左孩子 -> 右孩子 （序1）

那么如果我们先压左孩子，再压右孩子，那么出栈顺序就一定会变为：

头节点 -> 右孩子 -> 左孩子 （序2）

而后序遍历的访问顺序为：

左孩子 -> 右孩子 -> 头结点 （序3）

也就是说，后续遍历的顺序与上面的序 2 恰恰相反。所以我们可以采用以下方式完成后序遍历：弹出头结点，先压入左孩子，再压入右孩子；出栈时，将弹出的节点放入到另一个栈保存（而不是打印访问）；最后统一依次访问另一个栈，即可完成后序遍历。

另一个栈的作用其实就是为了反序打印序 2。代码如下：

void post(TreeNode* root)
{
    if(root == nullptr)
        return;
    TreeNode* tmp;
    stack<TreeNode*> stk1;
    stack<TreeNode*> stk2;
    stk1.push(root);
    while(!stk1.empty())
    {
        tmp = stk1.top();
        stk1.pop();
        stk2.push(tmp);
        if(tmp->left != nullptr)
            stk1.push(tmp->left);
        if(tmp->right != nullptr)
            stk1.push(tmp->right);
    }
    while(!stk2.empty())
    {
        tmp = stk2.top();
        stk2.pop();
        cout << tmp->data << endl;
    }
}

值得一提的是，序 1、序 2 和序 3 的这种关系也会在后序反序列化二叉树中得到应用。

层序遍历

层序遍历通过队列完成，弹出头结点时，先压入左孩子，再压入右孩子。代码如下：

void layer(TreeNode* root)  
{  
    if(root == nullptr)  
        return;  
    TreeNode* tmp = root;  
    queue<TreeNode*>que;  
    que.push(tmp);  
    while(!que.empty())  
    {  
        tmp = que.front();  
        que.pop();  
        cout << tmp->data << endl;  
        if(tmp->left != nullptr) /**容易忽略**/  
            que.push(tmp->left);  
        if(tmp->right != nullptr) /**容易忽略**/  
            que.push(tmp->right);  
    }  
}