非递归遍历二叉树

/*******************************************************
 >非递归遍历二叉树（先序、中序、后序遍历）
 *****************************************************/


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

struct node{ //定义树节点
    char ch;
    node *left,*right;
};

node *creat();

void preorder( node *root );
void inorder( node* root );
void postorder( node *root );
int main()
{
    node *root = creat();

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

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

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

    return 0;
}

node *creat() //按先序遍历创建一棵树
{
    node *root = new node;
    char ch;
    cin >> ch;
    if( ch == '#' )
    {
        root = NULL;
    }
    else
    {
        root->ch = ch;
        root->left = creat();
        root->right = creat();
    }
    return root;
}

void preorder( node *root )//先序遍历
{
    if( root == NULL )
        return;
    node *p = root;
    stack<node *> s;
    while( !s.empty() || p )
    {
        if( p )
        {
            cout << p->ch << " ";//输出根节点
            s.push( p );
            p = p->left;//进入左
        }
        else//左子树空了 进入右子树
        {
            p = s.top();
            s.pop();
            p = p->right;//进入右
        }
    }
    cout << endl;
}

void inorder( node *root ) //中序遍历
{
    if( root == NULL )
    return ;
    //树非空
    node *p = root;
    stack<node *> s;
    while( !s.empty() || p )
    {
        if( p ) // 向左遍历到底
        {
            s.push( p );
            p = p->left;
        }
        else //进入右子树
        {
            p = s.top(); //取栈顶元素 这时p还是左孩子 将根节点赋给p
            s.pop();
            cout << p->ch << " ";
            p = p->right;
        }
    }
    cout << endl;
}

void postorder( node *root )//后序遍历 难点在于需要判断上一个访问的是左子树还是右子树，若是左需要跳过跟访问右
{
    if( root == NULL )
        return ;
    stack< node *> s;
    node *p1,*p2;//p1为当前访问节点，p2为上次访问节点
    p1 = root;
    while( p1 )
    {
        s.push( p1 );
        p1 = p1->left;
    }
    //此时p1为空，走到左子树底端
    while( !s.empty() )
    {
        p1 = s.top();
        s.pop();
        //能访问根节点的前提是它无右子树或右子树已经被访问过
        if( p1->right == NULL || p1->right == p2 )
        {
            cout << p1->ch << " ";
            p2 = p1;
        }
        else
        {
            //根节点再次入栈
            s.push( p1 );
            //进入右子树
            p1 = p1->right;
            while( p1 )
            {
                s.push( p1 );
                p1 = p1->left;
            }
        }
    }
    cout << endl;
}