非递归后序周游二叉树

• 主要思想：
  每遇到一个结点先把它压入栈中，再去周游其左子树，周游完他的左子树左子树后，
  应继续周游该结点的右子树；周游完它的右子树之后，才从栈顶弹出该结点并访问它

#include
#include
#include
#define OK 1
#define ERROR 0
#define MAXSIZE 20


typedef char TElemType;
typedef int Status;
enum Tags{Left,Right};
typedef struct BiTNode  //二叉树的链式存储结构
{
    TElemType data;
    struct BiTNode * lchild;
    struct BiTNode * rchild; 
    Tags tag;
}BiTnode,*BiTree;

typedef BiTree SElemType;
typedef struct      //顺序栈的储存结构
{
    SElemType data[MAXSIZE];
    int top;    //用于栈顶指针
}Sqstack;



//顺序栈的初始化
Status InitSqstack(Sqstack * S)
{
    S->top=-1;
    return OK;
}

//出栈操作
Status Pop(Sqstack * S,SElemType * e)
{
    if(S->top==-1)  //栈底
    {
        return ERROR;
    }
    *e=S->data[S->top];
    S->top--;
    return OK;
}


//进栈操作
Status Push(Sqstack * S,SElemType e)
{
    if(S->top==MAXSIZE-1)   //栈满
    {
        return ERROR;
    }
    S->top++;   //栈顶指针增加1
    S->data[S->top]=e;
    return OK;
}



void CreateBiTree(BiTree * T)   //二叉树的建立
{
    TElemType ch;
    scanf("%c",&ch);
    if(ch=='#')
    {
        *T=NULL;
    }
    else
    {
        (*T)=(BiTree)malloc(sizeof(BiTNode));
    }
    if(!(*T))
    {
        return ;
    }
    else
    {
        (*T)->data=ch;
        CreateBiTree(&(*T)->lchild);
 CreateBiTree(&(*T)->rchild);
 }
}
//非递归后序周游二叉树
void PostOrderWithoutRecursion(BiTree * T,Sqstack * S)
{
 if(!(*T))
 {
 printf("空树!\n");
 return ;
 }
 while((*T) || S->top!=-1)
 {
 while((*T))
 {
 (*T)->tag=Left;
            Push(S,(*T));
            (*T)=(*T)->lchild;
        }
        Pop(S,&(*T));
        if((*T)->tag==Left)
 {
 (*T)->tag=Right;
            Push(S,(*T));
            (*T)=(*T)->rchild;
        }
        else
        {
            printf("%c ",(*T)->data);
 (*T)=NULL;
 }
 }
 printf("\n");

}


int main()
{
 BiTree root;
 Sqstack S;
 InitSqstack(&S);
 printf("Enter the data :\n");
 CreateBiTree(&root);
 printf("PostOrderWithoutRecursion the data:\n");
 PostOrderWithoutRecursion(&root,&S);
 return 0;
}

“`