二叉树的前序、中序、后序遍历（非递归）

#include <iostream>
#include <stack>
//定义树节点
typedef struct  TreeNode{
int key;
struct TreeNode *pLeft;
struct TreeNode *pRight;
}TreeNode;
//访问节点
void visit(TreeNode *root)
{
    if(NULL!=root)
        cout<<root->key;
    cout<<endl;
}

1. 二叉树前序遍历

void PreOrderTraverse(TreeNode *root)
{
    stack<TreeNode*>s;
    while((NULL!=root)||!s.empty())
    {
        if(NULL!=root)
        {
            visit(root);
            s.push(root);
            root=root->pLeft;
        }
        else
        {
            root=s.top();
            s.pop();
            root=root->pRight;
        }
    }
}

2. 二叉树中序遍历

void InOrderTraverse(TreeNode *root)
{
    stack<TreeNode *>s;
    while((NULL!=root)||!s.empty())
    {
        while(NULL!=root)//或者改为if(NULL!=root){} else{};但是不能用两个if(){} if(){}
        {
            s.push(root);
            root=root->pLeft;
        }
        if(!s.empty)
        {
            root=s.top();
            visit(root);
            s.pop();
            root=root->pRight;
        }
    }
}

3. 后序遍历
算法思路：
先找到最左边的节点，并将路上遇到的节点压栈，然后取栈顶元素（即最左边的节点），(1)检查它是否有右子树，(2)右子树是否被访问过，
如果没有右子树或者右子树已经被访问过，则访问当前节点，然后将pre指向当前节点，并将当前节点从栈中删除（当前节点出栈），
否则（有右子树且未被访问过），把右子树压栈。

void PostOrderTraverse(TreeNode *root)
{
    if(NULL==root)
        return;
    stack<TreeNode *>s;
    TreeNode *pre=NULL;
    while((NULL!=root)||!s.empty())//节点不空或栈不空
    {    
        while(NULL!=root)//找到最左节点
        {
            s.push(root);
            root=root->pLeft;
        }
        if(!s.empty())//栈不空
        {
            root=s.top();//获得栈顶元素
            if((NULL==root->pRight)||(root->pRight==pre))//如果当前节点没有右子树或者由子树已经访问过
            {
                visit(root);//访问当前节点
                s.pop();//当前节点出栈
                pre=root;//将当前节点赋给前继指针
                root=NULL;//将当前节点置空，防止再次入栈
            }
            else//当前节点有右子树且右子树没有被访问过
                root=root->pRight;
        }
    }    
}