在二叉树的操作中，二叉树的遍历是基本的操作，对于二叉树的遍历操作，主要分为：

• 前序遍历：根左右
• 中序遍历：左根右
• 后序遍历：左右根
• 层次遍历

后续遍历补充：

思想：相对于前序和中序，后续遍历的实现就稍显麻烦。我们要保证一个节点要在左孩子和右孩子之后才能访问，那么有下面三种情况：

1.它是叶子节点，没有左右孩子。可以直接访问。

2.它有左右孩子，但是左右孩子都已经被访问过，也可以直接访问该节点。

3.有左右孩子，且左右孩子没有访问过。此时要先入栈右孩子，再入栈左孩子。

为了确认一个节点的左右孩子是否被访问过，我们就要定义一个pPre指针。访问过一个节点后，就将pPre指向它，在下一轮判断就可以通过p->lchild || p->rchild  == pPre来作为子节点是否被访问过的条件了。

后序遍历代码调整：

#include "bits/stdc++.h"

using namespace std;


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal_zhongxu(TreeNode* root) {
        /*
        与中序的不同之处在于：

        中序遍历中，从栈中弹出的节点，其左子树是访问完了，可以直接访问该节点，然后接下来访问右子树。
        后序遍历中，从栈中弹出的节点，我们只能确定其左子树肯定访问完了，但是无法确定右子树是否访问过。
        因此，我们在后序遍历中，引入了一个prev来记录历史访问记录。

        当访问完一棵子树的时候，我们用prev指向该节点。
        这样，在回溯到父节点的时候，我们可以依据prev是指向左子节点，还是右子节点，来判断父节点的访问情况。
        */
        vector<int> ans;
        stack<TreeNode*> st;
        TreeNode* p = root, *pre = nullptr;
        while(p || !st.empty()){
            // cout << "test" << endl;
            while(p){
                st.push(p);
                p = p->left;
            }
            p = st.top();//左边已经被访问完毕，当前不能继续往左，要判断现在是访问根（右边已经被访问完毕或者为空）还是访问右边
            st.pop();//当前元素出栈
            if(p->right == nullptr || p->right == pre){
                //右节点为空，或者右节点刚刚已经被访问
                ans.push_back(p->val);
                pre = p;
                p = nullptr;//p已经被访问过，防止进入循环再次访问p
            }else{
                //右节点不为空，继续访问右子树
                st.push(p);//当前节点也未被访问输出，所以应该重新加入
                p = p->right;
            }
        }
        return ans;
    }

    vector<int> postorderTraversal_xianxu(TreeNode* root) {
        /*
        另外一种思路，先序遍历的翻转：根 右 左---->（翻转）左 右 根
        */
        vector<int> ans;
        stack<TreeNode*> st;
        TreeNode* p = root;
        while(p || !st.empty()){
            while(p){
                st.push(p);
                ans.insert(ans.begin(), p->val);
                p = p->right;
            }
            p = st.top()->left;//右边已经被访问完毕，现在需要访问左边
            st.pop();
        }
        return ans;
    }
};
    
};

直接见代码：

#include <iostream>
#include <stack>
#include <queue>
#include <malloc.h>
using namespace std;

typedef struct BiTNode
{
    int data;
    struct BiTNode *left, *right;
}BiTNode, *BiTree;

void Creat_Tree(BiTree &tree)
{
    int data;
    cin>>data;
    if(data == -1) tree = NULL;
    else
    {
        tree = (BiTNode *)malloc(sizeof(BiTNode));
        tree->data = data;
        Creat_Tree(tree->left);
        Creat_Tree(tree->right);
    }
}

//前序
void pre_visit(BiTree tree)
{
    stack<BiTNode *> s;
    BiTNode *q = tree;
    while(q != NULL || s.size() > 0)
    {
        while(q != NULL)
        {
            s.push(q);
            cout<<q->data<<" ";
            q = q->left;
        }
        if(s.size() > 0)
        {
            q = s.top()->right;
            s.pop();
        }
    }
    cout<<endl;
}
//中序
void infix_visit(BiTree tree)
{
    stack<BiTNode *> s;
    BiTNode *q = tree;
    while(q != NULL || s.size() > 0)
    {
        while(q != NULL)
        {
            s.push(q);
            q = q->left;
        }
        if(s.size() > 0)
        {
            q = s.top();
            s.pop();
            cout<<q->data<<" ";
            q = q->right;
        }
    }
    cout<<endl;
}
//后序
void suffix_visit(BiTree tree)
{
     stack<BiTNode *> s;
     BiTNode *q = tree, *pre, *top;
     s.push(q);
     while(s.size() > 0)
     {
         if(s.size() > 0)
            top = s.top();
         if((pre != NULL && (top->left == pre || top->right == pre)) || (top->left == NULL && top->right == NULL))
         {
            //pre为空对应到最开始时，并且此时的top为叶子节点。
             cout<<top->data<<" ";
             pre = top;
             s.pop();
         }
         else
         {
             if(top->right != NULL)
                s.push(top->right);
             if(top->left != NULL)
                s.push(top->left);
         }
     }
     cout<<endl;
}

//层序
void seq_visit(BiTree tree)
{
    queue<BiTNode *> q;
    BiTNode *p = tree;
    q.push(p);
    while(!q.empty())
    {
        p = q.front();
        cout<<p->data<<" ";
        q.pop();
        if(p->left != NULL)
            q.push(p->left);
        if(p->right != NULL)
            q.push(p->right);
    }
    cout<<endl;
}

int main()
{
    BiTree Tree;
    Creat_Tree(Tree);
    cout<<"先序遍历：";
    pre_visit(Tree);
    cout<<"中序遍历：";
    infix_visit(Tree);
    cout<<"后序遍历：";
    suffix_visit(Tree);
    cout<<"层序遍历：";
    seq_visit(Tree);
    return 0;
}