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

 　二叉树三种遍历的非递归算法(背诵版)

　　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