后序遍歷非遞歸算法
后序遍歷非遞歸算法
#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; //標(biāo)記為左子樹
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,表示右子樹訪問完畢,故訪問根結(jié)點(diǎn)
}
if (!StackEmpty(s))
{
s.Elem[s.top].tag =R; //遍歷右子樹
p=s.Elem[s.top].ptr->rchild;
}
}while (!StackEmpty(s));
}//PostOrderUnrec
【后序遍歷非遞歸算法】相關(guān)文章:
6.筆試題(算法類)