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

时间：2010-07-19 来源：jeyo

#include <stdio.h>
#include <stdlib.h>
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;
}