各种二叉树遍历

C++实现，二叉树的递归、非递归版本的前序、中序、后序遍历。

// 二叉树结点
struct Node{
    int val;
    Node *left,*right;
    Node():left(nullptr),right(nullptr){}
    Node(int _v):val(_v),left(nullptr),right(nullptr){}
};

// 二叉搜索树
struct Tree{
    Node *root; //根节点
    std::vector<int> p; //存储遍历的结果

    Tree():root(nullptr){}
    ~Tree(){
        release(root);
    }

    // 输出p数组的内容
    void print(){
        for(size_t i=0;i<p.size();++i){
            std::cout<<p[i]<<" ";
        }
        std::cout<<std::endl;
    }

    // 插入节点
    void insert(int val){
        if(root==nullptr){
            root = new Node(val);
            return ;
        }
        Node *cur = root;
        while(true){
            if(val<=cur->val){
                if(cur->left){
                    cur = cur->left;
                }else{
                    cur->left = new Node(val);
                    return ;
                }
            }else{
                if(cur->right){
                    cur = cur->right;
                }else{
                    cur->right = new Node(val);
                    return ;
                }
            }
        }
    }

    // 三种递归遍历方式
    void _rpreorder(Node *r){
        if(r){
            p.push_back(r->val);
            _rpreorder(r->left);
            _rpreorder(r->right);
        }
    }
    void rpreorder(){
        p.clear();
        _rpreorder(root);
    }

    void _rinorder(Node *r){
        if(r){
            _rinorder(r->left);
            p.push_back(r->val);            
            _rinorder(r->right);
        }
    }
    void rinorder(){
        p.clear();
        _rinorder(root);
    }

    void _rpostorder(Node *r){
        if(r){
            _rpostorder(r->left);
            _rpostorder(r->right);
            p.push_back(r->val);            
        }
    }
    void rpostorder(){
        p.clear();
        _rpostorder(root);
    }

    // 三种非递归遍历方式
    void preorder(){
        p.clear();
        if(root==nullptr) return ;
        std::stack<Node*> st;
        Node *cur = root;

        while(cur || !st.empty()){
            while(cur){
                p.push_back(cur->val);
                st.push(cur);
                cur = cur->left;
            }
            if(!st.empty()){
                cur = st.top();
                st.pop();
                cur = cur->right;
            }
        }
    }

    void inorder(){
        p.clear();
        if(root==nullptr) return ;
        std::stack<Node*> st;
        Node *cur = root;
        while(cur || !st.empty()){
            while(cur){
                st.push(cur);
                cur = cur->left;
            }
            if(!st.empty()){
                cur = st.top();
                st.pop();
                p.push_back(cur->val);
                cur = cur->right;
            }
        }
    }

    void postorder(){
        p.clear();
        if(root==nullptr) return ;
        Node *cur = root;
        Node *last = nullptr; //上一个输出的节点
        std::stack<Node*> st;

        while(cur || !st.empty()){
            while(cur){
                st.push(cur);
                cur = cur->left;
            }
            cur = st.top();
            if(cur->right==nullptr || cur->right==last){
                p.push_back(cur->val);
                st.pop();
                last = cur;
                cur = nullptr;
            }else{
                cur = cur->right;
            }
        }

    }
    void release(Node *r){
        if(r==nullptr) return ;
        if(r->left) release(r->left);
        if(r->right) release(r->right);
        delete r;
        r = nullptr;
    }
};