后序遍历非递归算法

#define maxsize 100

typedef enum{L,R} tagtype;

typedef struct

{

Bitree ptr;

tagtype tag;

}stacknode;

typedef struct

{

stacknode Elem[maxsize];

int top;

}SqStack;

//后序遍历

void PostOrderUnrec(Bitree t)

{

    SqStack s;

    stacknode x;

    StackInit(s);

    p=t;



    do

    {

        while (p!=null)       //遍历左子树

        {

            x.ptr = p;

            x.tag = L;        //标记为左子树

            push(s,x);

            p=p->lchild;

        }



        while (!StackEmpty(s) &&s.Elem[s.top].tag==R)

        {

            x = pop(s);

            p = x.ptr;

            visite(p->data);   //tag为R，表示右子树访问完毕，故访问根结点

        }



        if (!StackEmpty(s))

        {

            s.Elem[s.top].tag =R;    //遍历右子树

           p=s.Elem[s.top].ptr->rchild;

        }

    }while (!StackEmpty(s));

}//PostOrderUnrec