前序遍历

/* 前序遍历递归版 */
void PreOrderRec(Node * node)
{
    if (node == nullptr)
        return;
    cout << node->data << " ";   // 先输出当前结点   
    PreOrderRec(node->left);     // 然后输出左孩子
    PreOrderRec(node->right);    // 最后输出右孩子
}

/* 前序遍历非递归版 */
void PreOrderNonRec(Node * node)
{
    if (node == nullptr)
        return;

    stack<Node*> S;
    cout << node->data << " ";
    S.push(node);
    node = node->left;

    while (!S.empty() || node)
    {
        while (node)
        {
            cout << node->data << " "; // 先输出当前结点  
            S.push(node);
            node = node->left;         // 然后输出左孩子
        }                              // while 结束意味着左孩子已经全部输出

        node = S.top()->right;         // 最后输出右孩子
        S.pop();
    }
}

中序遍历

/* 中序遍历递归版 */
void InOrderRec(Node * node)
{
    if (node == nullptr)
        return;

    InOrderRec(node->left);     // 先输出左孩子
    cout << node->data << " ";  // 然后输出当前结点
    InOrderRec(node->right);    // 最后输出右孩子
}

/* 前序遍历非递归版 */
void InOrderNonRec(Node * node)
{
    if (node == nullptr)
        return;

    stack<Node*> S;
    S.push(node);
    node = node->left;

    while (!S.empty() || node)
    {
        while (node)
        {
            S.push(node);
            node = node->left;
        }                             // while 结束意味着左孩子为空

        cout << S.top()->data << " "; // 左孩子已经全部输出，接着输出当前结点
        node = S.top()->right;        // 左孩子全部输出，当前结点也输出后，最后输出右孩子
        S.pop();
    }
}

后序遍历

/* 后序遍历递归版 */
void PostOrderRec(Node * node)
{
    if (node == nullptr)
        return;

    PostOrderRec(node->left);   // 先输出左孩子
    PostOrderRec(node->right);  // 然后输出右孩子
    cout << node->data << " ";  // 最后输出当前结点
}

/* 后序遍历非递归版 */
void PostOrderNonRec(Node * node)
{
    if (node == nullptr)
        return;

    Node * pre = nullptr;
    stack<Node*> S;
    S.push(node);

    while (!S.empty())
    {
        node = S.top();

        if ((!node->left && !node->right) ||                    // 第一个输出的必是无左右孩子的叶子结点，只要第一个结点输出，
            (pre && (pre == node->left || pre == node->right))) // 以后的 pre 就不会是空。此处的判断语句加入一个 pre，只是用来
        {                                                       // 确保可以正确输出第一个结点。
            cout << node->data << " ";  // 左右孩子都全部输出，再输出当前结点
            pre = node;
            S.pop();
        }
        else
        {
            if (node->right)
                S.push(node->right);  // 先进右孩子，再进左孩子，取出来的才是左孩子
            if (node->left)
                S.push(node->left);
        }
    }
}

二叉树遍历——递归、非递归版