二叉树的非递归前序，中序，后序遍历算法

#include
#include
struct tree
{
     char data;
     struct tree *lchild;
     struct tree *rchild;
};
typedef struct tree * treptr;
treptr build(treptr t)//先序建树
{
     char c;
     c=getchar();
    if(c=='#')
    {
          t=NULL;
     }
     else
     {
          t=(treptr)malloc(sizeof(struct tree));
          t->data=c;
          t->lchild=build(t->lchild);
          t->rchild=build(t->rchild);
     }
     return t;
}
#if 0
void postdorder_b(treptr root)//这是前序遍历递归实现
{
     if (root!=NULL)
     {
          printf("%c",root->data);
          postdorder(root->lchild);
           postdorder(root->rchild);
      }

}

void postdorder_m(treptr root)//这是中序遍历递归实现
{
     if (root!=NULL)
     {
          postdorder(root->lchild);
          printf("%c",root->data);
          postdorder(root->rchild);
     }

}

void postdorder_l(treptr root)//这是后序遍历递归实现
{
     if (root!=NULL)
     {
          postdorder(root->lchild);
          postdorder(root->rchild);
         printf("%c",root->data);
     }

}
#endif

struct stack
{
 treptr *top,*base;
};
typedef struct stack *stackptr;
void init (stackptr s)//初始化栈
{
 s->base=(treptr*)malloc(sizeof(treptr)*100);
 s->top=s->base;
}
void push(stackptr s,treptr t)//入栈
{
 *(s->top++)=t;
}
treptr pop(stackptr s)//弹出栈顶元素
{
 treptr t;
 t=*(--(s->top));
 return t;
}
treptr gettop(stackptr s)//取栈顶元素
{
 treptr *l=s->top-1;
 return *(l);
}
void postorder_l(treptr t)//这是非递归后序实现
{
 stackptr s=(stackptr)malloc(sizeof(struct stack));
 treptr temp=t;
 treptr p;
 treptr lastvist=NULL;
 init(s);
 p=t;
 while(p||s->top!=s->base)
 {
  while(p)
  {
     push(s,p);
     p=p->lchild;
  }
  temp=gettop(s);
  if(temp->rchild==NULL||temp->rchild==lastvist)
  {
     putchar(temp->data);
     lastvist=pop(s);
  }
  else
    p=temp->rchild;
 }
}

void postorder_m(treptr t)//这是非递归中序实现
{
 stackptr s=(stackptr)malloc(sizeof(struct stack));
 treptr temp=t;
 treptr p;
 treptr lastvist=NULL;
 init(s);
 p=t;
 while(p||s->top!=s->base)
 {
  while(p)
  {
     push(s,p);
     p=p->lchild;
  }
  temp=pop(s);
  putchar(temp->data);
  p=temp->rchild;
 }
}

void postorder_b(treptr t)//这是非递归前序实现
{
 stackptr s=(stackptr)malloc(sizeof(struct stack));
 treptr temp=t;
 treptr p;
 treptr lastvist=NULL;
 init(s);
 p=t;
 while(p||s->top!=s->base)
 {
  while(p)
  {
    putchar(p->data);
    push(s,p);
    p=p->lchild;
  }
  temp=pop(s);
  p=temp->rchild;
 }
}

int main()
{
 treptr t=NULL;
 t=build(t);
 //postdorder(t);
 printf("\n非递归前序遍历\n");
 postorder_b(t);
 printf("\n非递归中序遍历\n");
 postorder_m(t);
 printf("\n非递归后序遍历\n");
 postorder_l(t);
 printf("\n");
 return 0;
}