二叉树的先序，中序，后序遍历的非递归实现

利用栈实现二叉树的先序，中序，后序遍历的非递归操作

#include
#include
#include
#include
#include
#include
using namespace std;
typedef struct BiTNode{
    char data;
    BiTNode *lchild, *rchild;
}BiTNode,*BiTree;

void CreateBiTree(BiTree &T)//建树，按先序顺序输入节点
{
    char ch;
    scanf("%c",&ch);
    if(ch==' ')
    {
        T=NULL;
        return;
    }
    else
    {
        T=(BiTree)malloc(sizeof(BiTNode));
        if(!T)
            exit(1);
        T->data=ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}
void InOrderTraverse(BiTree T)//非递归中序遍历
{

    stack Stack;
    if(!T)
    {
        printf("空树！\n");
        return;
    }

    while(T || !Stack.empty())
    {
        while(T)
        {
            Stack.push(T);
            T=T->lchild;
        }
        T=Stack.top();
        Stack.pop();
        printf("%c",T->data);
        T=T->rchild;
    }
}



void PreOrderTraverse(BiTree T)//非递归先序遍历
{

    stack Stack;
    if(!T)
    {
        printf("空树！\n");
        return;
    }
    while(T || !Stack.empty())
    {
        while(T)
        {
            Stack.push(T);
            printf("%c",T->data);
            T=T->lchild;
        }
        T=Stack.top();
        Stack.pop();
             T=T->rchild;
    }
}


void PostOrderTraverse(BiTree T)//非递归后序遍历,用一个标记标记右子树是否访问过
{
    int flag[20];
    stack Stack;
    if(!T)
    {
        printf("空树！\n");
        return;
    }
    while(T)
    {
        Stack.push(T);
        flag[Stack.size()]=0;
        T=T->lchild;
    }
    while(!Stack.empty())
    {
        T=Stack.top();
        while(T->rchild && flag[Stack.size()]==0)
        {
            flag[Stack.size()]=1;
            T=T->rchild;
            while(T)
            {
                Stack.push(T);
                flag[Stack.size()]=0;
                T=T->lchild;
            }
        }
        T=Stack.top();
        printf("%c",T->data);
        Stack.pop();
    }
}
void main()
{

    BiTree T;
    CreateBiTree(T);
    PreOrderTraverse(T);
    printf("\n");
         InOrderTraverse(T);
    printf("\n");
    PostOrderTraverse(T);
    printf("\n");
}