2014年软考程序员常考知识点复习笔记第二章3

 　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