[CODE]
/*以下程序在TC2.0编译！*/
/*程序默认的先序建树序列为：“abdg e c f ”*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char tree[30]; /*tree数组为先序建树序列*/
int ti=0;

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

/*先序建树函数！*/
void CreateBiTree(BiTree *T) {
char ch;
ch=tree[ti++];
if(ch==NULL) return;
if(ch==' ') *T=NULL;
else {
*T=(BiTree)malloc(sizeof(BiTNode));
(*T)->data=ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}

/*二叉树的后序遍历递归算法*/
void PostOrder(BiTree T) {
if(T) {
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%c ",T->data);
}
}

/*采用”标记栈法“的后序遍历非递归算法（while-while形式）*/
void PostOrder_zb(BiTree t) {
int tag[100],top=0; /*tag为标记栈*/
BiTree stack[100];
while(t||top) {
while(t) {
stack[++top]=t;
tag[top]=0; /*标记栈置为0：第一次访问*/
t=t->lchild;
}
if(top) {
if(tag[top]==1) {printf("%c ",stack[top]->data); --top;} /*如果这个结点访问了两次，输出之*/
else {
t=stack[top]; /*否则置栈顶为：第二次访问*/
tag[top]=1;
t=t->rchild;
}
}
}
}

/*采用”标记栈法“的后序遍历非递归算法（while-if形式）*/
void PostOrder_zb_if(BiTree t) {
int tag[100],top=0; /*tag为标记栈*/
BiTree stack[100];
while(t||top) {
if(t) {
stack[++top]=t;
tag[top]=0; /*标记栈置为0：第一次访问*/
t=t->lchild;
}
else {
if(tag[top]==1) {printf("%c ",stack[top]->data); --top;} /*如果这个结点访问了两次，输出之*/
else {
t=stack[top]; /*否则置栈顶为：第二次访问*/
tag[top]=1;
t=t->rchild;
}
}
}
}

main() {
BiTree T=NULL;
strcpy(tree,"abdg e c f ");/*该树的先序序列为:abdgecf*/
CreateBiTree(&T);
printf("\nPostOrder output:");
PostOrder(T);
printf("\nPostOrder_zb output:");
PostOrder_zb(T);
printf("\nPostOrder_zb_if output:");
PostOrder_zb_if(T);
getch();
}

[/CODE]