用C++实现树的前序，后序的递归和非递归算法，应包含建树的实现

1.采用201933110041进行数据测试 编写二差树
2.要求
具体代码，实验结果截图，代码注释

C++实现递归，非递归遍历二叉树（前序，中序，后序）_Monster丶Xu的博客-CSDN博客_c++递归遍历二叉树 初学二叉树那会儿，始终掌握不好二叉树的遍历方法，更认为非递归遍历晦涩难懂没有掌握的意义。实际上非递归的遍历方法很有用处，由于每次递归都需要将函数的信息入栈，当递归层数太深很容易就导致栈溢出，所以这个时候就必须用到非递归遍历二叉树了。而且，当看懂非递归遍历后，你会发现，其实非递归也很简单。我们知道，要想处理二叉树，离不开其遍历方式。遍历二叉树有三种方式，前序遍历，中序遍历，后序遍历，每种... https://blog.csdn.net/Hairy_Monsters/article/details/82053541

详细代码如下，望采纳。

//二叉树结构
class TreeNode {
    public:
        TreeNode(int val_) :val(val_), left(NULL), right(NULL) {}
        TreeNode* left;
        TreeNode* right;
        int val;
 };

//前序遍历递归
void headPrint1(TreeNode* root) {
    if (root == nullptr) return;
    cout<<root->val<<endl;
    headPrint1(root->left);
    headPrint1(root->right);
}

//前序遍历非递归
void headPrint2(TreeNode* root) {
    if (root == nullptr) return;
    stack<TreeNode*> stk;
    TreeNode* node = root;
    stk.push(root);
    while (!stk.empty()) {
        node = stk.top();
        stk.pop();
        cout << node->val<<endl;
        if (node->right != nullptr) stk.push(node->right);
        if (node->left != nullptr) stk.push(node->left);
    }
}

//后序遍历递归
void tailPrint1(TreeNode* root) {
    if (root == nullptr) return;
    tailPrint1(root->left);
    tailPrint1(root->right);
    cout << root->val << endl;
}


//后序遍历非递归
void tailPrint1(TreeNode* root) {
    vector<int> res;
    if (root == nullptr) return;

    stack<TreeNode*> stk;
    TreeNode* prev = nullptr;
    while (root != nullptr || !stk.empty()) {
        while (root != nullptr) {
            stk.emplace(root);
            root = root->left;
        }
        root = stk.top();
        stk.pop();
        if (root->right == nullptr || root->right == prev) {
            cout<<root->val<<endl;
            prev = root;
            root = nullptr;
        }
        else {
            stk.emplace(root);
            root = root->right;
        }
    }

}

给定一个二叉树，返回它的前中后序遍历。

示例：输入[1,2,3,4,-1,5,6,-1,7,-1,-1,8,-1] ,-1代表无节点(null)
输出：二叉树的前序、中序、后序遍历序列。

完整实现代码（包括定义数据结构、建树等）如下：

#include<iostream>
#include<string>
#include<vector>
#include<cstring>
#include<stack>
#include<map>
#include<queue>
using namespace std;
struct TreeNode{
    int val;
    TreeNode *left,*right;
    TreeNode(int x):val(x),left(NULL),right(NULL){}
};
//---建树
TreeNode* creaTree(vector<int> x){
    queue<TreeNode*>nodequeue;
    TreeNode *root=new TreeNode(x[0]);
    nodequeue.push(root);
    TreeNode *p=root;
    int i=1;
   while(true){
        p=nodequeue.front();
        nodequeue.pop();
        if(i>=x.size())break;
        if(x[i]!=-1){
            p->left=new TreeNode(x[i]);
            nodequeue.push(p->left);
        }
        i ++;
        if(i>=x.size())break;
        if(x[i]!=-1){
            p->right=new TreeNode(x[i]);
            nodequeue.push(p->right);
        }
        i++;
    }
    return root;
}
class Solution {
public:
    //-------------前序递归---
    vector<int>res1;
    vector<int> recpreorderTraversal(TreeNode* root){
        if(root){
            res1.push_back(root->val);
            recpreorderTraversal(root->left);
            recpreorderTraversal(root->right);
        }
        return res1;
    }
    //------------前序非递归
    vector<int> preorderTraversal(TreeNode* root){
        vector<int>res;
        TreeNode *p=root;
        stack<TreeNode*>s;
        while(p || !s.empty()){
            while(p){
                res.push_back(p->val);
                s.push(p);
                p=p->left;
            }
            if(!s.empty()){
                p=s.top();
                s.pop();
                p=p->right;
            }
        }
        return res;
    }
    //---------中序非递归
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*>s;
        vector<int>res;
        //map<TreeNode*,bool>instack;
        TreeNode *p=root;
        //s.push(root);
        while(p!=nullptr || !s.empty()){
            while(p!=nullptr){
                s.push(p);
                p=p->left;
            }
            if(!s.empty()){
                p=s.top();
                s.pop();
                //cout<<p->val;
                res.push_back(p->val);
                p=p->right;
            }
        }
        return res;
    }
    //--------------中序递归---------
    vector<int>res2;
    vector<int> recinorderTraversal(TreeNode* root) {
        if (root != nullptr) {
            recinorderTraversal(root->left);
            res2.push_back(root->val);
            recinorderTraversal(root->right);
        }
        return res2;
    }
    //-------------后序递归
    vector<int>res3;
    vector<int> recpostorderTraversal(TreeNode* root) {
        if(root){
            recpostorderTraversal(root->left);
            recpostorderTraversal(root->right);
            res3.push_back(root->val);
        }
        return res3;
    }
    //---------------后序非递归
    vector<int> postorderTraversal(TreeNode* root){
        vector<int>res;
        stack<TreeNode*>s;
        TreeNode *p,*pre= nullptr;
        s.push(root);
        while(!s.empty()){
            p=s.top();
            if((!p->left && !p->right) || ((pre!=nullptr) &&(pre==p->left ||pre==p->right))){
                res.push_back(p->val);
                s.pop();
                pre=p;
            }
            else{
                if(p->right)
                    s.push(p->right);
                if(p->left)
                    s.push(p->left);
            }
        }
        return res;
    }
};
 
int main(){
    vector<int>x={1,2,3,4,-1,5,6,-1,7,-1,-1,8,-1};
    //cout<<x.size();
    TreeNode *root=creaTree(x);
    vector<int>res=Solution().postorderTraversal(root);
    for(int i=0;i<res.size();i++) {
        cout << res[i] << " ";
    }
    return 0;
}