二叉树的先序 中序 后序非递归遍历

经常看到很多人要这方面的源程序。这个是我在wintc下编译通过的

现源程序如下：

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define MaxSize 100
#define null 0
typedef struct lnode
{
 char data;
 struct lnode *lchild;
 struct lnode *rchild;
 }lnode,*tree;             /*程序由 c来c去 编写 QQ:380537193*/

 tree creat() /*创建一个栈,此处也可在函数括号里写入tree b .但后边语句tree b要去掉*/
  {
    char ch;      /*输入数据为字符型*/
       tree b;          /*定义一个指向结构体的指针b,其类型属于tree*/
         scanf(“%c”,&ch);
       if(ch==’#')      /*这里用#表示子树为空的情况，即从键盘输入#时，判定为空*/
    b=null;        /*如果子树为空，则b为空。*/
 else
 {
    b=(tree)malloc(sizeof(lnode));   /*开辟一个新的结点 且把它赋给b*/
      b->data=ch;
        b->lchild=creat();
    b->rchild=creat();
 }
 return (b);
 }
 PreOrder(tree b)
  {
    tree p;
      struct
 {
   tree pt;
     int tag;
 }St[MaxSize];

   int top=-1;
     top++;
       St[top].pt=b;St[top].tag=1;
          while(top>-1)            /*栈不空时循环*/
 {
    if(St[top].tag==1)             /*不能直接访问的情况*/
  {
     p=St[top].pt;
       top–;
         if(p!=null)
  {
    top++;                        /*右孩子进栈*/
       St[top].pt=p->rchild;
         St[top].tag=1;
            top++;                 /*左孩子进栈*/
              St[top].pt=p->lchild;
            St[top].tag=1;
         top++;                        /*根结点进栈*/
      St[top].pt=p;
   St[top].tag=0;
 }
  }
   if(St[top].tag==0)
  {
     printf(“%3c”,St[top].pt->data);
       top–;
      }
    }
  }
  Inorder(tree b)
  {
    lnode * St[MaxSize],*p;
       int top=-1;
          if(b!=null)
  {
    p=b;
      while(top>-1||p!=null)
   {
      while(p!=null)
  {
    top++;
       St[top]=p;
          p=p->lchild;
  }
    if(top>-1)
    {
       p=St[top];
          top–;
            printf(“%3c”,p->data);
          p=p->rchild;
    }
  }
    printf(“\n”);
    }
  }
  Postorder(tree b)                  /*后序遍历*/
  {
    lnode *St[MaxSize];
       lnode *p;
         int flag,top=-1;            /*栈指针设初值*/
            if(b!=null)
  {
    do
    {
       while(b!=null)                /*将b的所有左结点入栈*/
      {
         top++;
            St[top]=b;
              b=b->lchild;
      }
        p=null;                      /*p指向当前结点的前一个已访问的结点*/
          flag=1;                    /*设置b的访问标记记为已访问过*/
            while(top!=-1&&flag)
       {
          b=St[top];                 /*取出当前的栈顶元素*/
            if(b->rchild==p)         /*右子树不存在或已被访问*/
        {
          printf(“%3c”,b->data);     /*访问*b的结点*/
            top–;
              p=b;                   /* *p指向刚被访问的结点*/
        }
         else
      {
         b=b->rchild;                /*b指向右子树*/
           flag=0;                   /*设置未被访问的标记*/
      }
    }
  }
   while(top!=-1);
      printf(“\n”);
      }
    }

   main()
  {
   int i;tree b;
   printf(“input the datas\n”);
   b=creat();
   printf(“****^O^***  select  ***^O^****\n”);
   printf(“\t1:PreOrder\n”);
   printf(“\t2:Inorder\n”);
   printf(“\t3:Postorder\n”);
   printf(“\t4:Exit\n”);
   printf(“****^O^** c lai c qu **^O^****\n”);
   printf(“input your select:”);
   scanf(“%d”,&i);
     switch(i){
     case 1: PreOrder(b); break;
     case 2: Inorder(b);  break;
     case 3: Postorder(b);break;
     case 4: exit(0);}
     getch();
     }