二叉树的迭代遍历

二叉树前后序遍历（迭代）

#include <bits/stdc++.h>
using  namespace  std;
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int value=0):data(value),left(nullptr),right(nullptr){}
};
Node *insertEle();
void preorder(Node *pNode);
void midorder(Node* p);
void postorder(Node* p);
int main() {
    Node* root = insertEle();
    cout << "Inorder traversal of the tree is: ";
    preorder(root);
    cout << endl;
    postorder(root);
    return 0;
}
void postorder(Node* p){
    cout<<"Post order is :";
    stack<Node*> stk;
    vector<int> res;
    stk.push(p);
    while (!stk.empty()){
        Node* ele=stk.top();
        stk.pop();
        if(ele){
            res.push_back(ele->data);
            stk.push(ele->left);
            stk.push(ele->right);
        }
    }
    std::reverse(res.begin(), res.end());
    for(const auto& item:res){
        cout << item << " ";
    }
    cout << endl;
}
void  preorder(Node *pNode) {
    stack<Node*> stk;
    vector<int> res;
    stk.push(pNode);
    while (!stk.empty()){
        Node* p = stk.top();
        stk.pop();
        if(p){
            res.push_back(p->data);
            stk.push(p->right);
            stk.push(p->left);
        }
    }

    for(const auto& item:res){
        cout << item << " ";
    }
    cout << endl;
}

Node *insertEle() {
    Node* root = new Node(5);
    root->left = new Node(4);
    root->right = new Node(6);
    root->left->left = new Node(2);
    root->left->right = new Node(1);
    return root;
}

void midorder(Node* p){
    cout<<"----------------------------------------------------------------------"<<endl;
    cout<<"mid order is :";
    stack<Node*> stk;
    vector<int> res;

    Node* cur=p;
    while (!stk.empty()||cur){
        if(cur){
            stk.push(cur);

            cur=cur->left;
        }
        if(!cur){
            Node* ptr = stk.top();
            stk.pop();
            res.push_back(ptr->data);
            cur=ptr->right;
        }
    }
    for(const auto& item:res){
        cout << item << " ";
    }
    cout << endl;
}

原来的迭代法的前序遍历，是中左右，然后把

stk.push(p->right);
stk.push(p->left);//从栈里面出来的就是中左右

颠倒顺序

stk.push(p->left);
stk.push(p->right);//从栈里面出来的就是中右左

接着我直接reverse这个vector，就是左右中，直接得到后序遍历

中序的逻辑就是一直往左走，到底了，打印“中”（左中右里面的“中”），然后去右（right）部分里面

具体代码讲解！！！

【写出二叉树的非递归遍历很难么？这次让你不再害怕非递归！|二叉树的非递归遍历 | 二叉树的遍历迭代法 | 前序与中序】 【精准空降到 00:01】 https://www.bilibili.com/video/BV15f4y1W7i2/?share_source=copy_web&vd_source=afbacdc02063c57e7a2ef256a4db9d2a&t=1

【写出二叉树的非递归遍历很难么？这次再带你写出中序遍历的迭代法！|二叉树的非递归遍历 | 二叉树的遍历迭代法】 【精准空降到 00:05】 https://www.bilibili.com/video/BV1Zf4y1a77g/?share_source=copy_web&vd_source=afbacdc02063c57e7a2ef256a4db9d2a&t=5

层序遍历简单

void layerorder(Node* p){
    queue<Node*> q;
    cout<<"Layer order is :";
    q.push(p);
    while (!q.empty()){
        Node* ptr=q.front();
        q.pop();
        if(ptr){
            cout<<ptr->data<<" ";
            q.push(ptr->left);
            q.push(ptr->right);
        }
    }
    cout<<endl;
}