二叉树的遍历（递归、迭代）

#include<iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <string.h>
#include<stack>
#include<ctime>
#include <sstream>
#include <queue>
using namespace std;
// 树节点的结构体
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 函数声明
void preorder (TreeNode * p);
void midorder (TreeNode *p);
void postorder(TreeNode *p);
void preorder_1 (TreeNode *p);
void preorder_2 (TreeNode *p);
void midorder_1(TreeNode* p);
void postorder_1(TreeNode* p);
void levelorder_1(TreeNode*p);

int main()
{
    TreeNode* a=new TreeNode (2);
    TreeNode* b= new TreeNode(3);
    TreeNode* c= new TreeNode(1);
    a->left=b;a->right=c;
    TreeNode* d= new TreeNode(6);
    TreeNode* e= new TreeNode(4);
    b->left=new TreeNode(5);b->right=d;
    d->left=new TreeNode(3);d->right=new TreeNode(0);
    c->right=e;
    e->left=new TreeNode (-1);e->right=new TreeNode(2);//创建一棵二叉树

    cout << "递归版: " <<endl; 
    preorder(a);
    cout << endl;
    midorder(a);
    cout << endl;
    postorder(a);
    cout << endl;
    cout <<"迭代版: " <<endl;
    cout << "先序遍历1.0:";
    preorder_1(a);
    cout <<endl;
    cout << "先序遍历2.0:";
    preorder_2(a);
    cout <<endl;
    cout << "中序遍历:";
    midorder_1(a);
    cout << endl;
    cout <<"层次遍历:" ;
    levelorder_1(a);
    cout << endl;
    return 0;
}
//%%%%%%%%%%%%%%%%%%%%%%%%%%%  递归版  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// 树的前序遍历
void preorder (TreeNode * p)
{
    if(p == NULL) return;
        //根左右
    cout<< p->val << " ";
    preorder(p->left);
    preorder(p->right);
}
//树的中序遍历
void midorder (TreeNode *p)
{
    if(p == NULL) return;
        //左根右
    midorder(p->left);
    cout<< p->val << " ";
    midorder(p->right);
}
// 树的后序遍历
void postorder(TreeNode *p)
{
    if(p == NULL) return;
        //左右根
    postorder(p->left);
    postorder(p->right);
    cout<< p->val << " ";
}
// %%%%%%%%%%%%%%%%%%%%%%%% 迭代版 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// 前序遍历1.0
void preorder_1 (TreeNode *p)
{
    stack<TreeNode *> s;//建立一个栈
    s.push(p);
    while(!s.empty())
    {
        TreeNode* tmp=s.top();
        s.pop();
        cout << tmp->val << " ";
        if(tmp->right != NULL) s.push(tmp->right);
        if(tmp->left != NULL) s.push(tmp->left);//后进先出，先右后左
    }
}
// 前序遍历2.0
void visitalongleft(TreeNode* p,stack<TreeNode*> &s)
{    
    while(p!=NULL)
    {
        s.push(p);
        cout << p->val << " ";
        p=p->left;
    }
}
void preorder_2 (TreeNode *p)
{
    stack<TreeNode*> s;
    while(true)
    {
        visitalongleft(p,s);
        if(s.empty()==true) break;
        TreeNode* tmp=s.top();
        s.pop();
        p=tmp->right;
    }
}
// 中序遍历迭代版
void leftalong(TreeNode* p,stack<TreeNode*> &s)
{
    while(p!=NULL) {s.push(p);p=p->left;}
}

void midorder_1(TreeNode* p)
{
    stack<TreeNode*> s;
    while(true)
    {
        leftalong(p,s);
        if(s.empty()==true) break;
        cout << s.top()->val << " ";
        p=s.top()->right;
        s.pop();
    }
}

void levelorder_1(TreeNode*p)
{
    queue<TreeNode *> q;
    if(p==NULL) return;
    q.push(p);
    while(!q.empty())
    {
        cout << q.front()->val <<" ";
        if(q.front()->left != NULL) q.push(q.front()->left);
        if(q.front()->right != NULL) q.push(q.front()->right);
        q.pop();
    }
}