树的遍历

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

struct treenode
{
    char val;
    treenode* left;
    treenode* right;
    treenode():val(0),left(NULL),right(NULL){}
    treenode(char x):val(x),left(NULL),right(NULL){}
    treenode(char x,treenode *left,treenode *right):val(x),left(left),right(right){}
};
//先序遍历
//递归
void preorder(treenode *root)
{
    if(!root) return;
    cout<<root->val<<' ';
    preorder(root->left);
    preorder(root->right);
}
//非递归
void preorder2(treenode *root)
{
    stack<treenode*> s;
    s.push(root);

    while(!s.empty())
    {
        treenode *t=s.top();
        s.pop();

        cout<<t->val<<' ';
        if(t->right)s.push(t->right);
        if(t->left) s.push(t->left);
    }
}

//中序遍历
//递归
void inorder(treenode *root)
{
    if(!root) return;
    inorder(root->left);
    cout<<root->val<<" ";
    inorder(root->right);
}
//非递归
void inorder2(treenode *root)
{
    stack<treenode*> s;
    treenode *cur=root;

    while(cur||!s.empty())
    {
        while(cur)
        {
            s.push(cur);
            cur=cur->left;
        }

        cur=s.top();
        s.pop();

        cout<<cur->val<<" ";
        cur=cur->right;
    }
}

//后序遍历
//递归
void postorder(treenode *root)
{
    if(!root) return ;
    postorder(root->left);
    postorder(root->right);
    cout<<root->val<<" ";
}
//非递归
void postorder2(treenode *root)
{
    stack<treenode*> s;
    treenode* cur=root;
    treenode* preve=NULL;

    while(cur||!s.empty())
    {
        while(cur)
        {
            s.push(cur);
            s.push(cur->left);
        }

        cur=s.top();
        if(!cur->right||cur->right==preve)
        {
            s.pop();
            cout<<cur->val<<' ';

            preve=cur;
            cur=nullptr;
        }
        else
        {
            cur=cur->right;
        }
    }
}

//层次遍历
void levelorder(treenode *root)
{
    queue<treenode*> q;
    q.push(root);

    while(!q.empty())
    {
        treenode *t=q.front();
        q.pop();
        cout<<t->val<<' ';

        if(t->left)q.push(t->left);
        if(t->right)q.push(t->right);
    }
}

//层次遍历逆转
void levelorder2(treenode *root)
{
    queue<treenode*> q;
    stack<treenode*> s;
    q.push(root);

    while(!q.empty())
    {
        treenode *t=q.front();
        q.pop();

        s.push(t);
        if(t->left)q.push(t->left);
        if(t->right)q.push(t->right);
    }

    while(s.size())
    {
        cout<<s.top()->val<<" ";
        s.pop();
    }
}

int main()
{
    treenode *root=new treenode('A',new treenode('B',
    new treenode('D'),new treenode('E')),new treenode('C'));


    cout<<"     A  "<<endl;
    cout<<" B       C  "<<endl;
    cout<<"D E    "<<endl;

    cout<<"先序遍历："<<endl;
    preorder(root);
    cout<<endl;
    preorder2(root);
    cout<<endl;

    cout<<"中序遍历："<<endl;
    inorder(root);
    cout<<endl;
    inorder2(root);
    cout<<endl;

    cout<<"后序遍历："<<endl;
    postorder(root);
    cout<<endl;
    postorder2(root);
    cout<<endl;

    cout<<"层序遍历："<<endl;
    levelorder(root);
    cout<<endl;
    levelorder2(root);
    cout<<endl;

    return 0;
}