二叉树的基本操作(非递归(后序遍历))

#include
#include
#include

#define MAXSIZE 100

typedef enum{L,R} tagtype;

typedef struct BiTNode
{
        int data;
        struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

typedef struct stacknode
{
        BiTree ptr;
        tagtype tag;
}StackNode;

typedef struct stack
{
        StackNode data[MAXSIZE];
        int top;
}Stack;

void StackInit(Stack *S)
{
        S->top=-1;
}

int StackEmpty(Stack *S)
{
        return S->top==-1;
}

int StackFull(Stack *S)
{
        return S->top==MAXSIZE-1;
}

void push(Stack *S, StackNode value)
{
        if(StackFull(S))
        {
                printf("Stack is full!\n");
                exit(-1);
        }
        S->data[++S->top]=value;
}

void pop(Stack *S)
{
        if(StackEmpty(S))
        {
                printf("Stack is empty!\n");
                exit(-1);
        }
        S->top--;
}

StackNode top(Stack *S)
{
        if(StackEmpty(S))
        {
                printf("Stack is empty!\n");
                exit(-1);
        }
        return S->data[S->top];
}
void CreateBiTree(BiTree *T)
{
        int ch;
        scanf("%d",&ch);
        if(ch==-1)
        {
                *T=NULL;
        }
        else
        {
                *T=(BiTree)malloc(sizeof(BiTNode));
                if(!(*T))
                        printf("memory alloc error");
                (*T)->data=ch;
                CreateBiTree(&((*T)->lchild));
                CreateBiTree(&((*T)->rchild));
        }
}

void PostOrderTraverse(BiTree T)
{
        BiTree p=T;
        Stack *s=(Stack *)malloc(sizeof(Stack));
        StackNode x;
        StackInit(s);

        do
        {
                while(p!=NULL)
                {
                        x.ptr=p;
                        x.tag=L;
                        push(s,x);
                        p=p->lchild;
                }
                while(!StackEmpty(s) && (s->data[s->top]).tag==R)
                {
                        x=top(s);
                        pop(s);
                        p=x.ptr;
                        printf("%3d",p->data);
                }
                if(!StackEmpty(s))
                {
                        (s->data[s->top]).tag=R;
                        p=(s->data[s->top]).ptr->rchild;
                }
        }while(!StackEmpty(s));
}

int main(void)
{
        BiTree T;
        printf("请输入创建一棵二叉树的先序序列:\n");
        CreateBiTree(&T);
        printf("后序序列为:");
        PostOrderTraverse(T);
        printf("\n");

        return 0;
}