二叉樹先序、中序、後序三種周遊的非遞歸算法

本貼給出二叉樹先序、中序、後序三種周遊的非遞歸算法，此三個算法可視為标準算法。

1.先序周遊非遞歸算法

#define maxsize 100

typedef struct

{

    Bitree Elem[maxsize];

    int top;

}SqStack;

void PreOrderUnrec(Bitree t)

{

    SqStack s;

    StackInit(s);

    p=t;

    while (p!=null || !StackEmpty(s))

    {

        while (p!=null)             //周遊左子樹

        {

            visite(p->data);

            push(s,p);

            p=p->lchild;      

        }//endwhile

        if (!StackEmpty(s))         //通過下一次循環中的内嵌while實作右子樹周遊

        {

            p=pop(s);

            p=p->rchild;        

        }//endif

    }//endwhile

}//PreOrderUnrec

2.中序周遊非遞歸算法

#define maxsize 100

typedef struct

{

    Bitree Elem[maxsize];

    int top;

}SqStack;

void InOrderUnrec(Bitree t)

{

    SqStack s;

    StackInit(s);

    p=t;

    while (p!=null || !StackEmpty(s))

    {

        while (p!=null)             //周遊左子樹

        {

            push(s,p);

            p=p->lchild;

        }//endwhile

        if (!StackEmpty(s))

        {

            p=pop(s);

            visite(p->data);        //通路根結點

            p=p->rchild;            //通過下一次循環實作右子樹周遊

        }//endif   

    }//endwhile

}//InOrderUnrec

3.後序周遊非遞歸算法

#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