二叉树先序、中序、后序三种遍历的非递归算法,此三个算法可视为

二叉树先序、中序、后序三种遍历的非递归算法,此三个算法可视为标准

#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

//ͨ¹ ÏÂÒ»´ÎÑ­»·Ö µÄÄÚǶ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; (!StackEmpty(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;

//ͨ¹ ÏÂÒ»´ÎÑ­»·ÊµÏÖÓÒ×ÓÊ÷±éÀú