设二叉树以二叉链表为存储结构，编写一个后续遍历二叉树的非递归算法

#include
#include
#include

#define STACK_INT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2

typedef char TElemType;
typedef int Status;
typedef char SElemType;

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

typedef struct
{
BiTree *base;
BiTree *top;
int stacksize;
}SqStack;

typedef struct QNode
{
BiTree Queuedata;
struct QNode * next;
}QNode,* QueuePtr;

typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;

Status InitStack(SqStack &S)
{
S.base = (BiTree *) malloc(sizeof(BiTree));
if(!S.base) exit(OVERFLOW);
S.top = S.base;
S.stacksize = STACK_INT_SIZE;
return OK;
}

Status GetTop(SqStack &S, BiTree &e)
{
if(S.top == S.base) return ERROR;
e = *(S.top-1);
return OK;
}

Status Push(SqStack &S, BiTree e)
{
if(S.top - S.base >= S.stacksize)
{
S.base = (BiTree *) realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(BiTree));
if(!S.base) return ERROR;
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top = e;
S.top++;
return OK;
}

Status Pop(SqStack &S,BiTree &e)
{
if(S.base == S.top) return ERROR;
S.top--;
e = *S.top;
return OK;
}

Status StackEmpty(SqStack S)
{
if(S.top == S.base) return TRUE;
else return FALSE;
}

Status PreOrderCreateBiTree(BiTree &T)
{
char ch;
scanf("%c",&ch);
if(ch == '0') T = NULL;
else
{
if(!(T = (BiTNode* ) malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T->data = ch;
PreOrderCreateBiTree(T->lchild);
PreOrderCreateBiTree(T->rchild);
}
return OK;
}

void PreOrder ( BiTree bt )
{
if ( bt )
{
printf("%c",bt->data);
PreOrder ( bt->lchild );
PreOrder ( bt->rchild );
}
}

void Inorder ( BiTree bt )
{
if ( bt )
{
Inorder ( bt->lchild );
printf("%c",bt->data);
Inorder ( bt->rchild );
}
}

void LastOrder ( BiTree bt )
{
if ( bt )
{
LastOrder( bt->lchild );
LastOrder( bt->rchild );
printf("%c",bt->data);
}
}

Status PreOrderTraverse(BiTree T)
{
SqStack s;
BiTree P=T;
InitStack(s);
while ( P!=NULL || !StackEmpty(s))
{
if (P!=NULL)
{
printf("%c",P->data);
Push(s,P);
P=P->lchild;
}
else
{
Pop(s,P);
P=P->rchild;
}
}
return OK;
}

Status InOrderTraverse(BiTree T)
{
SqStack S;
InitStack(S);
BiTree p;
p = T;
while(p || !StackEmpty(S))
{
if(p)
{
Push(S,p);
p = p->lchild;
}
else
{
Pop(S,p);
printf("%c",p->data);
p = p->rchild;
}
}
return OK;
}

Status LastOrderTraverse(BiTree T)
{
SqStack s,tag;
BiTree f,m,n,P=T;
m=(BiTNode*)malloc(sizeof(BiTNode));
m->data=1;
m->lchild=NULL;
m->rchild=NULL;
n=(BiTNode*)malloc(sizeof(BiTNode));
n->data=2;
n->lchild=NULL;
n->rchild=NULL;
InitStack(s);
InitStack(tag);
while (P ||!StackEmpty(s))
{
if (P)
{
Push(s,P);
Push(tag,m);
P=P->lchild;
}
else
{
Pop(s,P);
Pop(tag,f);
if (f==m)
{
Push(s,P);
Push( tag, n);
P=P->rchild;
}
else
{
printf("%c",P->data);
P=NULL;

}
}
}
return OK;
}

Status InitQueue(LinkQueue &Q)
{
Q.front=(QNode*)malloc(sizeof(QNode));
if (!Q.front)
exit(OVERFLOW);
Q.rear=Q.front;
Q.front->next=NULL;
return OK;
}

Status EnQueue(LinkQueue &Q,BiTree e)
{
QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
if (!s)
exit(OVERFLOW);
s->Queuedata=e;
s->next=NULL;
Q.rear->next=s;
Q.rear=s;
return OK;
}

int DelQueue(LinkQueue &Q, BiTree &e)
{
char data1;
QueuePtr s;
s=Q.front->next;
e=s->Queuedata;
data1=e->data;
Q.front->next=s->next;
if(Q.rear==s)
Q.rear=Q.front;
free(s);
return TRUE;
}

Status QueueEmpty(LinkQueue Q)
{
if (Q.front->next==NULL)
return OK;
else return ERROR;
}

Status HierarchyBiTree(BiTree bt)
{
LinkQueue Q;
InitQueue(Q);
BiTree p = bt;
if (bt == NULL) return ERROR;
EnQueue(Q,p);
while (!QueueEmpty(Q))
{
DelQueue(Q, p);
printf("%C",p->data);
if (p->lchild)
EnQueue(Q, p->lchild);
if (p->rchild)
EnQueue(Q, p->rchild);
}
return OK;
}

int sum=0;
int SumLefts(BiTree bt)
{
if (bt!=NULL)
{
if (bt->lchild==NULL && bt->rchild==NULL)
{
sum++;
}
sum=SumLefts(bt->lchild);
sum=SumLefts(bt->rchild);
}
return(sum);
}

void main()
{
printf("请输入先序建立二叉树所需要的数据(空树用0表示)：\n\n");
BiTree t;
PreOrderCreateBiTree(t);
printf("\n\n");
printf("递归遍历输出为：\n");
printf("先序输出： ");
PreOrder(t);
printf("\n");
printf("中序输出： ");
Inorder(t);
printf("\n");
printf("后序输出： ");
LastOrder(t);
printf("\n\n\n");
printf("非递归遍历输出为：\n");
printf("先序输出： ");
PreOrderTraverse(t);
printf("\n");
printf("中序输出： ");
InOrderTraverse(t);
printf("\n");
printf("后序输出： ");
LastOrderTraverse(t);
printf("\n\n\n");
printf("按层次遍历输出为： ");
HierarchyBiTree(t);
printf("\n\n\n\n");
printf("二叉树中叶子节点个数为：");
int leaves=SumLefts(t);
printf("%d",leaves);
printf("\n");
}

我也不知道

等我作一下告诉你